Abstract
Thanks to a new upper bound, we study more precisely the nonlinearities of Maiorana-McFarland’s resilient functions. We characterize those functions with optimum nonlinearities and we give examples of functions with high nonlinearities. But these functions have a peculiarity which makes them potentially cryptographically weak. We study a natural super-class of Maiorana-McFarland’s class whose elements do not have the same drawback and we give examples of such functions achieving high nonlinearities.
Chapter PDF
Similar content being viewed by others
References
P. Camion, C. Carlet, P. Charpin, N. Sendrier, “On correlation-immune functions”, Advances in Cryptology-CRYPTO’91, Lecture Notes in Computer Science 576, pp. 86–100 (1991).
A. Canteaut, C. Carlet, P. Charpin et C. Fontaine. “On cryptographic properties of the cosets of R(1,m)”. IEEE Transactions on Information Theory Vol. 47, no 4, pp. 1494–1513 (2001)
A. Canteaut and M. Trabbia. “Improved fast correlation attacks using parity-check equations of weight 4 and 5”, Advanced in Cryptology-EUROCRYPT 2000. Lecture notes in computer science 1807, pp. 573–588 (2000).
A. Canteaut and M. Videau. “Degree of Composition of Highly Nonlinear Functions and Applications to Higher Order Diffierential Cryptanalysis”, Advances in Cryptology, EUROCRYPT2002, Lecture Notes in Computer Science 2332, Springer Verlag, pp. 518–533 (2002)
C. Carlet. “Partially-bent functions”, Designs Codes and Cryptography, 3, pp. 135–145 (1993) and Advances in Cryptology-CRYPTO’92 Lecture Notes in Computer Science 740, pp. 280-291 (1993).
C. Carlet. “More correlation-immune and resilient functions over Galois fields and Galois rings”. Advances in Cryptology, EUROCRYPT’ 97, Lecture Notes in Computer Science 1233, Springer Verlag, pp. 422–433 (1997).
C. Carlet. “On the coset weight divisibility and nonlinearity of resilient and correlation-immune functions”, Proceedings of SETA’01 (Sequences and their Applications 2001), Discrete Mathematics and Theoretical Computer Science, Springer, pp. 131–144 (2001).
C. Carlet and P. Sarkar. “Spectral Domain Analysis of Correlation Immune and Resilient Boolean Functions”. Finite fields and Applications 8, pp. 120–130 (2002).
S. Chee, S. Lee, K. Kim and D. Kim. “Correlation immune functions with controlable nonlinearity”. ETRI Journal, vol 19, no 4, pp. 389–401 (1997).
S._Chee, S. Lee, D. Lee and S. H. Sung. “On the correlation immune functions and their nonlinearity” proceedings of Asiacrypt’96, LNCS 1163, pp. 232–243 (1997).
T. W. Cusick. “On constructing balanced correlation immune functions”. Proceedings of SETA’98 (Sequences and their Applications 1998), Discrete Mathematics and Theoretical Computer Science, Springer, pp. 184–190 (1999).
J. F. Dillon. Elementary Hadamard Difference sets. Ph. D. Thesis, Univ. of Maryland (1974).
H. Dobbertin, “ Construction of bent functions and balanced Boolean functions with high nonlinearity”, Fast Software Encryption (Proceedings of the 1994 Leuven Workshop on Cryptographic Algorithms), Lecture Notes in Computer Science 1008, pp. 61–74 (1995).
Mac Williams, F. J. and N. J. Sloane (1977). The theory of error-correcting codes, Amsterdam, North Holland.
S. Maitra and P. Sarkar. “Modifications of Patterson-Wiedemann functions for cryptographic applications”. IEEE Trans. Inform. Theory, Vol. 48, pp. 278–284, 2002.
W. Meier and O. Stafielbach. “ Nonlinearity Criteria for Cryptographic Functions”, Advances in Cryptology, EUROCRYPT’ 89, Lecture Notes in Computer Science 434, Springer Verlag, pp. 549–562 (1990).
N.J. Patterson and D.H. Wiedemann. “ The covering radius of the [21], [16] Reed-Muller code is at least 16276”. IEEE Trans. Inform. Theory, IT-29, pp. 354–356 (1983).
N.J. Patterson and D.H. Wiedemann. “ Correction to [17]”. IEEE Trans. Inform. Theory, IT-36(2), pp. 443 (1990).
E. Pasalic, S. Maitra, T. Johansson and P. Sarkar. “New constructions of resilient functions and correlation immune Boolean functions achieving upper bound on nonlinearity”. Proceedings of the Workshop on Coding and Cryptography 2001, pp. 425–434 (2001).
O. S. Rothaus. “ On bent functions”, J. Comb. Theory, 20A, 300–305 (1976).
R. A. Rueppel Analysis and design of stream ciphers Com. and Contr. Eng. Series, Berlin, Heidelberg, NY, London, Paris, Tokyo 1986
P. Sarkar and S. Maitra. “Construction of nonlinear Boolean functions with important cryptographic properties”. Advances in Cryptology-EUROCRYPT 2000, number 1807 in Lecture Notes in Computer Science, Springer Verlag, pp. 485–506 (2000).
P. Sarkar and S. Maitra. “Nonlinearity Bounds and Constructions of Resilient Boolean Functions”. CRYPTO 2000, LNCSVol. 1880, ed. Mihir Bellare, pp. 515–532 (2000).
J. Seberry, X.M. Zhang and Y. Zheng. “On constructions and nonlinearity of correlation immune Boolean functions.” Advances in Cryptology-EUROCRYPT’93, LNCS 765, pp. 181–199 (1994).
J. Seberry, X.M. Zhang and Y. Zheng. “Nonlinearly balanced Boolean functions and their propagation characteristics.” Advances in Cryptology-CRYPTO’93, pp. 49–60 (1994).
T. Siegenthaler. “Correlation-immunity of nonlinear combining functions for cryptographic applications”. IEEE Transactions on Information theory, V. IT-30, No 5, pp. 776–780 (1984).
T. Siegenthaler. “Decrypting a Class of Stream Ciphers Using Ciphertext Only”. IEEE Transactions on Computer, V. C-34, No 1, pp. 81–85 (1985).
Y. V. Tarannikov. “ On resilient Boolean functions with maximum possible nonlinearity”. Proceedings of INDOCRYPT 2000, Lecture Notes in Computer Science 1977, pp. 19–30 (2000).
Y. V. Tarannikov. “New constructions of resilient Boolean functions with maximum nonlinearity”. Proceedings of FSE 2001, to appear in the Lecture Notes in Computer Science Series (2002).
Xiao Guo-Zhen and J. L. Massey. “A Spectral Characterization of Correlation-Immune Combining Functions”. IEEE Trans. Inf. Theory, Vol IT 34, n. 3, pp. 569–571 (1988).
Y. Zheng, X.-M. Zhang. “ Improved upper bound on the nonlinearity of high order correlation immune functions”. Proceedings of Selected Areas in Cryptography 2000, Lecture Notes in Computer Science 2012, pp. 262–274 (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
Carlet, C. (2002). A Larger Class of Cryptographic Boolean Functions via a Study of the Maiorana-McFarland Construction. In: Yung, M. (eds) Advances in Cryptology — CRYPTO 2002. CRYPTO 2002. Lecture Notes in Computer Science, vol 2442. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45708-9_35
Download citation
DOI: https://doi.org/10.1007/3-540-45708-9_35
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44050-5
Online ISBN: 978-3-540-45708-4
eBook Packages: Springer Book Archive