Generalized proper matrices and constructing of $m$-resilient Boolean functions with maximal nonlinearity for expanded range of parameters

Y. V. Tarannikov

Sibirskie èlektronnye matematičeskie izvestiâ, Tome 11 (2014), pp. 229-245.

Résumé

Nonlinearity and resiliency are well known as some of the most important cryptographic parameters of Boolean functions, it is actual the problem of the constructing of functions that have high non-linearity and resiliency simultaneously. In 2000 three groups of authors obtained independently the upper bound $2^{n-1}-2^{m+1}$ for the nonlinearity of an $m$-resilient function of $n$ variables. It was shown that if this bound is achieved then $(n-3)/2\le m\le n-2$. Simultaneously in 2000 Tarannikov constructed functions that achieve this bound for $(2n-7)/3\le m\le n-2$. In 2001 Tarannikov constructed such functions for $0.6n-1\le m$ introducing for this aim so called proper matrices; later in 2001 Fedorova and Tarannikov constructed by means of proper matrices the functions that achieve the bound $2^{n-1}-2^{m+1}$ for $m\ge cn(1+o(1))$ where $c=1/\log_2(\sqrt{5}+1)=0.5902...$ but proved simultaneously that by means of proper matrices it is impossible to improve this result. During the period since 2001 it was not any further progress in the problem on the achievability of the bound $2^{n-1}-2^{m+1}$ in spite of this problem was well known and actual except the constructing in 2006–2007 by three groups of authors by means of a computer search concrete functions for $n=9$, $m=3$. In this paper we find the new approach that uses the generalization of the concept of proper matrices. We formulate combinatorial problems solutions of which allow to construct generalized proper matrices with parameters impossible for old proper matrices. As a result we obtain the constructions of $m$-resilient functions of $n$ variables with maximal nonlinearity for $m\ge cn(1+o(1))$ where $c=0.5789...$, and also we demonstrate how further advance in combinatorial problems follows an additional decrease of the constant $c$.

Détail

Keywords: Boolean functions, symmetric-key cryptography, nonlinearity, resiliency, maximal possible nonlinearity, bounds, plateaued functions, implementation complexity.
Mots-clés : constructions

Bibliographie

[1] S. Chee, S. Lee, D. Lee, S.–H. Sung, “On the correlation immune functions and their nonlinearity”, Advances in Cryptology, Asiacrypt'96, Lecture Notes in Computer Science, 1163, 1996, 232–243 | DOI | MR | Zbl

[2] B. Chor, O. Goldreich, J. Hastad, J. Friedman, S. Rudich, R. Smolensky, “The bit extraction problem or $t$-resilient functions”, IEEE Symposium on Foundations of Computer Science, 26 (1985), 396–407

[3] M. Fedorova, Y. Tarannikov, “On the constructing of highly nonlinear resilient Boolean functions by means of special matrices”, Progress in Cryptology, Indocrypt 2001, Proceedings (Chennai, India, December 16–20, 2001), Lecture Notes in Computer Science, 2247, Springer-Verlag, 2001, 254–266 ; M. Fedorova, Y. Tarannikov, On the constructing of highly nonlinear resilient Boolean functions by means of special matrices, Cryptology ePrint archive, Report 2001/083, , October 2001, 16 pp. http://eprint.iacr.org/ | DOI | MR | Zbl

[4] S. Fu, B. Sun, C. Li, L. Qu, “Construction of odd-variable resilient Boolean functions with optimal degree”, Journal of information science and engineering, 27 (2011), 1931–1942 | MR | Zbl

[5] S. Gao, W. Ma, Y. Zhao, Z. Zhuo, “Walsh Spectrum of Cryptographically Concatenating Functions and Its Applications in Constructing Resilient Boolean Functions”, Journal of Computational Information Systems, 7:4 (2011), 1074–1081

[6] S. Kavut, M. Yusel, S. Maitra, “Construction of resilient functions by the concatenation of Boolean functions having nonintersecting Walsh spectra”, Third International Workshop of Boolean functions, BFCA 07 (May 2–3, 2007, Paris, France)

[7] A. Khalyavin, “Constructing Boolean functions with extremal properties”, Proceedings of the NATO advanced study institute on Boolean functions in cryptology and information security (Zvenigorod, 8–18 September 2007), NATO science for peace and security series D: Informationand communication security, 18, eds. B. Preenel, O. A. Logachev, 2008, 289–295 ; A. Khalyavin, The constructing of $3$-resilient Boolean functions of $9$ variables with nonlinearity $240$, Cryptology ePrint Archive, Report 2007/212, , 2007, 7 pp. http://eprint.iacr.org/ | MR | Zbl

[8] H. Minc, Nonnegative matrices, John Wiley and Sons, New York, 1988 | MR

[9] E. Pasalic, S. Maitra, T. Johansson, P. Sarkar, “New constructions of resilient and correlation immune Boolean functions achieving upper bounds on nonlinearity”, WCC2001 International Workshop on Coding and Cryptography (Paris, January 8–12, 2001), Electronic Notes in Discrete Mathematics, 6, Elsevier Science, 2001 | DOI | MR | Zbl

[10] Z. Saber, M. Faisal Uddin, A. Youssef, “On the existence of $(9,3,5,240)$ resilient functions”, IEEE Transactions on Information Theory, 52:5 (2006), 2269–2270 | DOI | MR

[11] P. Sarkar, S. Maitra, “Nonlinearity bounds and constructions of resilient Boolean functions”, Advanced in Cryptology, Crypto 2000, Proceedings, Lecture Notes in Computer Science, 1880, 2000, 515–532 | DOI | MR | Zbl

[12] J. Seberry, X.–M. Zhang, Y. Zheng, “On constructions and nonlinearity of correlation immune functions”, Advances in Cryptology, Eurocrypt'93, Lecture Notes in Computer Science, 765, 1994, 181–199 | DOI | Zbl

[13] T. Siegenthaler, “Correlation-immunity of nonlinear combining functions for cryptographic applications”, IEEE Transactions on Information theory, 30:5 (1984), 776–780 | DOI | MR | Zbl

[14] D. Singh, “Construction of highly nonlinear plateaued resilient functions with disjoint spectra”, Mathematical Modelling and Scientific Computation, Communications in Computer and Information Science, 283, 2012, 522–529 | DOI

[15] Y. Tarannikov, “On resilient Boolean functions with maximal possible nonlinearity”, Proceedings of Indocrypt 2000, Lecture Notes in Computer Science, 1977, Springer-Verlag, 2000, 19–30 | DOI | MR | Zbl

[16] Y. Tarannikov, “New constructions of resilient Boolean functions with maximal nonlinearity”, Fast Software Encryption, 8th International Workshop, FSE 2001 (Yokohama, Japan, April 2–4, 2001), Lecture Notes in Computer Science, 2355, 2002, 66–77 | DOI | Zbl

[17] T. Wang, M. Liu, D. Lin, “Construction of resilient and nonlinear Boolean functions with almost perfect immunity to algebraic and fast algebraic attacks”, Information Security and Cryptology, Lecture Notes in Computer Science, 7763, 2013, 276–293 | DOI | Zbl

[18] G.-Z. Xiao, J. Massey, “A spectral characterization of correlation-immune combining functions”, IEEE Transactions on Information Theory, 34:3 (1988), 569–571 | DOI | MR | Zbl

[19] F. Zhang, C. Carlet, Y. Hu, W. Zhang, Secondary constructions of bent functions and highly nonlinear resilient functions, November 20, 2012, arXiv: 1211.4191 | MR

[20] Y. Zheng, X.-M. Zhang, “Improved upper bound on the nonlinearity of high order correlation immune functions”, Selected Areas in Cryptography, 7th Annual International Workshop, SAC2000, Lecture Notes in Computer Science, 2012, Springer-Verlag, 2001, 264–274 | MR

[21] A. Khalyavin, On constructions and estimations of characteristics of correlation-immune Boolean functions and related combinatorial objects, Ph. D. Thesis, M., 2011 (in Russian)

[22] A. Khalyavin, “The bound for the nonlinearity of correlation-immune Boolean functions”, Applied discrete mathematics, 11:1 (2011), 34–69 (in Russian) http://www.lib.tsu.ru/mminfo/000349342/11/image/11-034.pdf

[23] A. Khalyavin, “Constructing of $4$-correlation-immune Boolean functions of $9$ variables with nonlinearity $240$”, Discrete mathematics and its applications, Proceeding of X International seminar (Moscow, MSU, February 1–6, 2010), Mech. Math. Department of MSU, M., 2010, 534–537 (in Russian)