Abstract
In this paper we develop a technique that allows to obtain new effective constructions of highly resilient Boolean functions with high nonlinearity. In particular, we prove that the upper bound 2n-1 - 2m+1 on nonlinearity of m-resilient n-variable Boolean functions is achieved for 0.6n - 1 - m - n-2.
Chapter PDF
Keywords
References
P. Camion, C. Carlet, P. Charpin, N. Sendrier, On correlation-immune functions, Advances in Cryptology: Crypto’ 91, Proceedings, Lecture Notes in Computer Science, V. 576, 1991, pp. 86–100.
Seongtaek Chee, Sangjin Lee, Daiki Lee and Soo Hak Sung, On the Correlation Immune Functions and their Nonlinearity, Advances in Cryptology — Asiacrypt’ 96, Lecture Notes in Computer Science, V. 1163, 1996, pp. 232–243.
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, V. 26, 1985, pp. 396–407.
T. W. Cusick, On constructing balanced correlation immune functions, in Sequences and Their Applications, Proceedings of SETA’ 98, Springer Discrete Mathematics and Theoretical Computer Science, 1999, pp. 184–190.
M. Fedorova, Yu. Tarannikov. On the constructing of highly nonlinear resilient Boolean functions by means of special matrices, Cryptology ePrint archive (http://eprint.iacr.org/), Report 2001/083, October 2001, 16 pp.
M. Fedorova, Yu. Tarannikov. On the constructing of highly nonlinear resilient Boolean functions by means of special matrices, Progress in Cryptology — Indocrypt 2001, Chennai, India, December 16-20, 2001, Proceedings, Lecture Notes in Computer Science, V. 2247, pp. 254–266, Springer-Verlag, 2001.
E. Filiol, C. Fontaine, Highly Nonlinear Balanced Boolean Functions with a Good Correlation Immunity, Advanced in Cryptology, Eurocrypt’ 98, Helsinki, Finland, Lecture Notes in Computer Sciences, Vol. 1403, 1998, pp. 475–488.
S. Maitra, P. Sarkar, Highly nonlinear resilient functions optimizing Siegenthaler’s Inequality, Crypto’ 99, Lecture Notes in Computer Science, Vol. 1666, 1999, pp. 198–215.
P. Sarkar, S. Maitra, Construction of nonlinear Boolean functions with important cryptographic properties, In Advanced in Cryptology: Eurocrypt 2000, Lecture Notes in Computer Science, V. 1807, 2000, pp. 485–506.
P. Sarkar, S. Maitra, Nonlinearity bounds and constructions of resilient Boolean functions, In Advanced in Cryptology: Crypto 2000, Proceedings, Lecture Notes in Computer Science, V. 1880, 2000, pp. 515–532.
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, Volume 6, Elsevier Science, 2001.
E. Pasalic, T. Johansson, Further results on the relation between nonlinearity and resiliency for Boolean functions, IMA Conference on Cryptography and Coding, Lecture Notes in Computer Science, Vol. 1746, 1999, pp. 35–44.
N. J. Patterson, D. H. Wiedemann, The covering radius of the [215,16] Reed-Muller code is at least 16276, IEEE Transactions on Information Theory, V. 29, No. 3, pp. 354–356, May 1983.
N. J. Patterson, D. H. Wiedemann, Correction to [13], IEEE Transactions on Information Theory, V. 36, No. 2, p. 443, March 1990.
O. S. Rothaus, On bent functions, Journal of Combinatorial Theory, Series A20, pp. 300–305.
J. Seberry, X. Zhang, Y. Zheng, On Constructions and Nonlinearity of Correlation Immune Functions, Advances in Cryptology, Eurocrypt’ 93, Proceedings, Lecture Notes in Computer Science, V. 765, 1993, pp. 181–199.
T. Siegenthaler, Correlation-immunity of nonlinear combining functions for cryptographic applications, IEEE Transactions on Information theory, V. IT-30, No 5, 1984, p. 776–780.
T. Siegenthaler, Decrypting a Class of Stream Ciphers Using Ciphertext Only, IEEE Transactions on Computer, V. C-34, No 1, Jan. 1985, pp. 81–85.
Yu. Tarannikov. On resilient Boolean functions with maximal possible nonlinearity, Cryptology ePrint archive (http://eprint.iacr.org/), Report 2000/005, March 2000, 18 pp.
Yu. Tarannikov. On resilient Boolean functions with maximal possible nonlinearity, Proceedings of Indocrypt 2000, Lecture Notes in Computer Science, V. 1977, pp. 19–30, Springer-Verlag, 2000.
Yu. Tarannikov. New constructions of resilient Boolean functions with maximal nonlinearity, 8th Fast Software Encryption Workshop, Preproceedings, Yokohama, Japan, April 2-4, 2001, pp. 70–81.
Yu. Tarannikov, P. Korolev, A. Botev. Autocorrelation coefficients and correlation immunity of Boolean functions, Proceedings of Asiacrypt 2001, Gold Coast, Australia, December 9-13, 2001, Lecture Notes in Computer Science, V. 2248, pp. 460–479, Springer-Verlag, 2001.
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, V. 2012, pp. 264–274, Springer-Verlag, 2001.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Tarannikov, Y. (2002). New Constructions of Resilient Boolean Functions with Maximal Nonlinearity. In: Matsui, M. (eds) Fast Software Encryption. FSE 2001. Lecture Notes in Computer Science, vol 2355. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45473-X_6
Download citation
DOI: https://doi.org/10.1007/3-540-45473-X_6
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43869-4
Online ISBN: 978-3-540-45473-1
eBook Packages: Springer Book Archive