Algorithms for computing cryptographic characteristics of vectorial Boolean functions

N. M. Kiseleva ; E. S. Lipatova ; I. A. Pankratova ; E. E. Trifonova

Prikladnaâ diskretnaâ matematika, no. 4 (2019), pp. 78-87.

Résumé

There are presented algorithms for calculating the cryptographic characteristics of vectorial Boolean functions, such as the order of correlation immunity, nonlinearity, component algebraic immunity, and differential uniformity order. In these algorithms, the components of a vectorial Boolean function are enumerated according to the Gray code. Experimental results are given for random vectorial Boolean functions, permutations, and two known classes $\mathcal{K}_{n}$ and $\mathcal{S}_{n,k}$ of invertible vectorial Boolean functions in $n$ variables with coordinates essentially depending on all variables and on $k$ variables, $k$, respectively. Some properties of differential uniformity are theoretically proved for functions in $\mathcal{K}_{n}$ and $\mathcal{S}_{n,k} $, namely, the differential uniformity order $\delta_F$ equals $2^n$ for any $F\in\mathcal{S}_{n,k}$, and the inequality $2^n-4(n-1)\leq\delta_F\leq 2^n-4$ holds for any $F\in\mathcal{K}_{n}$.

Détail

Keywords: vectorial Boolean function, nonlinearity, correlation immunity, component algebraic immunity, differential uniformity.

Bibliographie

[1] Ding J., Yang B. Y., “Multivariate public key cryptography”, Post-Quantum Cryptography, eds. D. J. Bernstein, J. Buchmann, E. Dahmen, Springer, Berlin–Heidelberg, 2009, 193–241 | DOI | MR | Zbl

[2] Agibalov G. P., “Substitution block ciphers with functional keys”, Prikladnaya Diskretnaya Matematika, 2017, no. 38, 57–65 | MR

[3] Agibalov G. P., Pankratova I. A., “Asymmetric cryptosystems on Boolean functions”, Prikladnaya Diskretnaya Matematika, 2018, no. 40, 23–33 | MR

[4] Agibalov G. P., “ElGamal cryptosystems on Boolean functions”, Prikladnaya Diskretnaya Matematika, 2018, no. 42, 57–65 | MR

[5] Carlet C., Vectorial Boolean Functions for Cryptography, Cambridge University Press, Cambridge, 2010, 93 pp. | Zbl

[6] Canteaut A., Lecture Notes on Cryptographic Boolean Functions, Inria, Paris, 2016, 48 pp.

[7] Nyberg K., “Differentially uniform mappings for cryptography”, LNCS, 765, 1994, 55–64 | MR | Zbl

[8] Logachev O. A., Sal'nikov A. A., Yashchenko V. V., Boolean Functions in Coding Theory and Cryptology, MCCME Publ., M., 2004, 472 pp. (in Russian)

[9] Agibalov G. P., “Some theoretical aspects of differential cryptanalysis of the iterated block ciphers with additive round key”, Prikladnaya Diskretnaya Matematika, 2008, no. 1 (1), 34–42 (in Russian)

[10] Meier W., Pasalic E., Carlet C., “Algebraic attacks and decomposition of Boolean functions”, LNCS, 3027, 2004, 474–491 | MR | Zbl

[11] Agibalov G. P., Lipskiy V. B., Pankratova I. A., “Cryptographic extension and its implementation for Russian programming language”, Prikladnaya Diskretnaya Matematika, 2013, no. 3(21), 93–104 (in Russian)

[12] Pankratova I. A., “Construction of invertible vectorial Boolean functions with coordinates depending on given number of variables”, Proc. CSIST'16, BSU Publ., Minsk, 2016, 519–521

[13] Pankratova I. A., “On the invertibility of vector Boolean functions”, Prikladnaya Diskretnaya Matematika. Prilozhenie, 2015, no. 8, 35–37 (in Russian)

[14] Pankratova I. A., “Properties of components for some classes of vectorial Boolean functions”, Prikladnaya Diskretnaya Matematika, 2019, no. 44, 5–11 (in Russian)

[15] Canteaut A., “Open problems related to algebraic attacks on stream ciphers”, Proc. WCC'2005 (Bergen, Norway, March 14–18, 2005), 120–134 | MR | Zbl