From cryptanalysis to cryptographic property of a~Boolean function

A. A. Gorodilova

Prikladnaâ diskretnaâ matematika, no. 3 (2016), pp. 16-44.

Résumé

The survey is devoted to description of basic, but not all, cryptographic properties of Boolean functions: algebraic degree, balancedness and perfect balancedness, avalanche characteristics, non-existence of linear structures, correlation immunity and resiliency, high nonlinearity, statistical independence, algebraic immunity, affinity level and $k$-normality, differential uniformity, threshold implementation, multiplicative complexity, high cardinality of linearization sets. The questions about these properties formation are studied based on the attacks on stream and block ciphers that exploit the vulnerabilities of Boolean functions used in ciphers as components. The ideas of such attacks are given. We briefly describe the basic theoretical results obtained for each of the properties and formulate open problems in this area.

Détail

Keywords: Boolean function, stream cipher, block cipher, algebraic degree, balancedness, perfect balancedness, avalanche characteristics, linear structure, correlation immunity, resiliency, nonlinearity, statistical independence, algebraic immunity, affinity level, $k$-normality, differential uniformity, threshold implementation, multiplicative complexity, linearization set, linear complexity, correlation attack, fast correlation attack, linear cryptanalysis, statistical analogue, differential cryptanalysis, side-channel attacks, linearization attack.

Bibliographie

[1] Agibalov G. P., Selected Theorems of Basic Cryptography Course, Tutorial, NTL Publ., Tomsk, 2005 (in Russian)

[2] Agibalov G. P., “Methods for solving systems of polynomial equations over a finite field”, Vestnik Tomskogo Gosudarstvennogo Universiteta. Prilozhenie, 2006, no. 17, 4–9 (in Russian)

[3] Agibalov G. P., “Logical equations in cryptanalysis of key stream generators”, Vestnik Tomskogo Gosudarstvennogo Universiteta. Prilozhenie, 2003, no. 6, 31–41 (in Russian)

[4] Agibalov G. P. and Pankratova I. A., “Statistical approximation theory for discrete functions with application in cryptanalysis of iterative block ciphers”, Prikladnaya Diskretnaya Matematika, 2010, no. 3, 51–68 (in Russian)

[5] Alferov A. P., Zubov A. Yu., Kuz'min A. S., Cheremushkin A. V., Basics of Cryptography, Gelios ARV Publ., Moscow, 2002 (in Russian)

[6] Buryakov M. L., Algebraic, Combinatorial, and Cryptographic properties of Parameters of Boolean Functions Affine Restrictions, PhD Thesis, Moscow, 2007 (in Russian)

[7] Glukhov M. M., “About perfectly and almost perfectly non-linear functions”, Matematicheskie Voprosy Kriptografii, 2016 (in Russian)

[8] Glukhov M. M., On planar maps and their generalisation to finite fields, Pres. conf. “Algebra and Logic, Theory and Applications” (Krasnoyarsk, 21–27 July, 2013)

[9] Gorodilova A. A., “Characteristics of almost perfectly non-linear functions by subfunctions”, Diskr. Mat., 27:3 (2015), 3–16 (in Russian) | DOI

[10] Lobanov M. S., “Exact relation between nonlinearity and algebraic immunity”, Diskr. Mat., 18:3 (2006), 152–159 (in Russian) | DOI | MR | Zbl

[11] Logachev O. A., Sal'nikov A. A., Smyshlyaev S. V., Yashchenko V. V., Boolean Functions in Coding Theory and Cryptology, MCCME Publ., Moscow, 2012 (in Russian)

[12] Logachev O. A., Sal'nikov A. A., Yashchenko V. V., “Correlation immunity and real privacy”, Proc. conf. “Mathematics and Security of Information Technologies”, MCCME Publ., Moscow, 2004, 165–171 (in Russian)

[13] Pankov K. N., “Asymptotic estimates for numbers of Boolean mappings with given cryptographic properties”, Mat. Vopr. Kriptogr., 5:4 (2014), 73–97 (in Russian)

[14] Pankratova I. A., Boolean Functions in Cryptography, Tutorial, TSU Publ., Tomsk, 2014 (in Russian)

[15] Sachkov V. N., “Combinatorial properties of differentially 2-uniform substitutions”, Mat. Vopr. Kriptogr., 6:1 (2015), 159–179 (in Russian)

[16] Selezneva S. N., “Multiplicative complexity of some Boolean functions”, Diskr. Mat., 26:4 (2014), 100–109 (in Russian) | DOI

[17] Smyshlyaev S. V., “On cryptographic weaknesses of some classes of binary sequence transformations”, Prikladnaya Diskretnaya Matematika, 2010, no. 1, 5–15 (in Russian)

[18] Sumarokov S. N., “Prohibitions of binary functions and reversibility for a class of encoders”, Obozrenie Prikladnoy i Promyshlennoy Matematiki, 1:1 (1994), 33–55 (in Russian) | Zbl

[19] Tarannikov Yu. V., “On correlation-immune and resilient Boolean functions”, Mat. Voprosy Kibernetiki, 11, 2002, 91–148 (in Russian) | MR | Zbl

[20] Tokareva N. N., Symmetric Cryptography. Short Course, Tutorial, NSU Publ., Novosibirsk, 2012 (in Russian)

[21] Bilgin B., Nikova S., Nikov V., et al., “Threshold implementations of small $S$-boxes”, Cryptography and Communications, 7:1 (2015), 3–33 | DOI | MR | Zbl

[22] Blondeau C., Nyberg K., “Perfect nonlinear functions and cryptography”, Finite Fields and their Applications, 32 (2015), 120–147 | DOI | MR | Zbl

[23] Braeken A., Cryptographic Properties of Boolean Functions and $S$-boxes, PhD Thesis, Katholieke Universiteit Leuven, 2006

[24] Carlet C., “Boolean functions for cryptography and error correcting codes”, Boolean Methods and Models in Mathematics, Computer Science, and Engineering, Monograph, Cambridge Univ. Press, 2010, Ch. 8, 257–397

[25] Carlet C., “Vectorial Boolean functions for cryptography”, Boolean Methods and Models in Mathematics, Computer Science, and Engineering, Monograph, Cambridge Univ. Press, 2010, Ch. 9, 398–472

[26] Carlet C., Charpin P., Zinoviev V., “Codes, bent functions and permutations suitable for DES-like cryptosystems”, Des. Codes Cryptogr., 15 (1998), 125–156 | DOI | MR | Zbl

[27] Charpin P., “Normal Boolean functions”, J. Complexity, 20 (2004), 245–265 | DOI | MR | Zbl

[28] Courtois N., Hulme D., Mourouzis T., Solving Circuit Optimisation Problems in Cryptography and Cryptanalysis, Cryptology ePrint Archive. Report 2011/475, 2011

[29] Courtois N., Meier W., “Algebraic attack on stream ciphers with linear feedback”, LNCS, 2656, 2003, 345–359 | MR | Zbl

[30] Cusick T. W., Stănică P., Cryptographic Boolean Functions and Applications, Acad. Press Elsevier, 2009, 245 pp. | MR | Zbl

[31] Dobbertin H., “Construction of bent functions and balanced Boolean functions with high nonlinearity”, FSE'95, LNCS, 1008, 1995, 61–74 | Zbl

[32] Evertse J. H., “Linear structures in block ciphers”, EUROCRYPT'87, LNCS, 304, 1988, 249–266 | Zbl

[33] Fon-Der-Flaass D. G., “A bound on correlation immunity”, Siberian Elektron. Mat. Iz., 4 (2007), 133–135 | MR | Zbl

[34] Golić J. Dj., “On the security of nonlinear filter generators”, FSE'96, LNCS, 1039, 1996, 173–188

[35] Gorodilova A., On a Remarkable Property of APN Gold Functions, Cryptology ePrint Archive. Report 2016/286, 2016

[36] Mihaljevic M., Gangopadhyay S., Paul G., Imai H., “An algorithm for the internal state recovery of Grain-v1”, Proc. CECC'2011 (Debrecen, Hungary, June 30 – July 2, 2011), 7–20

[37] Nikova S., Rechberger C., Rijmen V., “Threshold implementations against side-channel attacks and glitches”, LNCS, 4307, 2006, 529–545 | MR | Zbl

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

[39] Preneel B., Van Leekwijck W., Van Linden L., et al., “Propagation characteristics of Boolean functions”, Eurocrypt'90, LNCS, 473, 1991, 161–173 | MR | Zbl

[40] Siegenthaler T., “Correlation-immunity of nonlinear combining functions for cryptographic applications”, IEEE Trans. Inform. Theory, 30:5 (1984), 776–780 | DOI | MR | Zbl

[41] Tarannikov Y. V., “Generalized proper matrices and constructing of $m$-resilient Boolean functions with maximal nonlinearity for expanded range of parameters”, Siberian Elektron. Mat. Iz., 11 (2014), 229–245 | Zbl

[42] Tokareva N., Bent Functions: Results and Applications to Cryptography, Acad. Press Elsevier, 2015, 220 pp. | MR

[43] Webster A. F., Tavares S. E., “On the design of $S$-boxes”, Crypto'85, LNCS, 218, 1986, 523–534

[44] Zajac P., Jokay M., “Multiplicative complexity of bijective $4\times4$ $S$-boxes”, Cryptography and Communications, 6:3 (2014), 255–277 | DOI | MR | Zbl

[45] Zhang X.-M., Zheng Y., “GAC – the criterion for Global Avalanche Characteristics of cryptographic functions”, J. Universal Computer Science, 1:5 (1995), 320–337 | MR | Zbl