×

zbMATH — the first resource for mathematics

From cryptanalysis to cryptographic property of a Boolean function. (Russian. English summary) Zbl 07310345
Summary: 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.
MSC:
94-XX Information and communication theory, circuits
68-XX Computer science
PDF BibTeX Cite
Full Text: DOI MNR
References:
[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)
[10] Lobanov M. S., “Exact relation between nonlinearity and algebraic immunity”, Diskr. Mat., 18:3 (2006), 152-159 (in Russian) · Zbl 1121.94020
[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) · Zbl 1317.06017
[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)
[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 0841.94042
[19] Tarannikov Yu. V., “On correlation-immune and resilient Boolean functions”, Mat. Voprosy Kibernetiki, 11, 2002, 91-148 (in Russian) · Zbl 1280.94128
[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 · Zbl 1365.94403
[22] Blondeau C., Nyberg K., “Perfect nonlinear functions and cryptography”, Finite Fields and their Applications, 32 (2015), 120-147 · Zbl 1372.94413
[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 · Zbl 1209.94035
[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 · Zbl 1209.94036
[26] Carlet C., Charpin P., Zinoviev V., “Codes, bent functions and permutations suitable for DES-like cryptosystems”, Des. Codes Cryptogr., 15 (1998), 125-156 · Zbl 0938.94011
[27] Charpin P., “Normal Boolean functions”, J. Complexity, 20 (2004), 245-265 · Zbl 1052.94015
[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 · Zbl 1038.94525
[30] Cusick T. W., Stănică P., Cryptographic Boolean Functions and Applications, Acad. Press Elsevier, 2009, 245 pp. · Zbl 1192.94093
[31] Dobbertin H., “Construction of bent functions and balanced Boolean functions with high nonlinearity”, FSE’95, LNCS, 1008, 1995, 61-74 · Zbl 0939.94563
[32] Evertse J. H., “Linear structures in block ciphers”, EUROCRYPT’87, LNCS, 304, 1988, 249-266 · Zbl 0659.94001
[33] Fon-Der-Flaass D. G., “A bound on correlation immunity”, Siberian Elektron. Mat. Iz., 4 (2007), 133-135 · Zbl 1132.05309
[34] Golić J. Dj., “On the security of nonlinear filter generators”, FSE’96, LNCS, 1039, 1996, 173-188 · Zbl 1373.94916
[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 · Zbl 1239.94058
[38] Nyberg K., “Differentially uniform mappings for cryptography”, Eurocrypt’93, LNCS, 765, 1994, 55-64 · Zbl 0951.94510
[39] Preneel B., Van Leekwijck W., Van Linden L., et al., “Propagation characteristics of Boolean functions”, Eurocrypt’90, LNCS, 473, 1991, 161-173 · Zbl 0764.94024
[40] Siegenthaler T., “Correlation-immunity of nonlinear combining functions for cryptographic applications”, IEEE Trans. Inform. Theory, 30:5 (1984), 776-780 · Zbl 0554.94010
[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 1398.94169
[42] Tokareva N., Bent Functions: Results and Applications to Cryptography, Acad. Press Elsevier, 2015, 220 pp. · Zbl 1372.94002
[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 · Zbl 1294.94087
[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 · Zbl 0960.68572
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.