Abstract
Boolean functions on the space \(\mathbb{F}_{2}^{m}\) are not only important in the theory of error-correcting codes, but also in cryptography. In these two cases, the nonlinearity of these functions is a main concept. Carlet, Olejár and Stanek gave an asymptotic lower bound for the nonlinearity of most of them, and I gave an asymptotic upper bound which was strictly larger. In this article, I improve the bounds and get an exact limit for the nonlinearity of most of Boolean functions. This article is inspired by a paper of G. Halász about the related problem of real polynomials with random coefficients.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Carlet C (2002). On cryptographic complexity of Boolean functions, In: Mullen GL, Stichtenoth H and Tapia-Recillas H (eds), Proceedings of the Sixth Conference on Finite Fields with Applications to Coding Theory, Cryptography and Related Areas Springer, pp 53–69
C Carlet (2004) ArticleTitleOn the degree, nonlinearity, algebraic thickness and non-normality of Boolean functions, with developments on symmetric functions IEEE Trans Inform Theory 50 2178–2185 Occurrence Handle2097207 Occurrence Handle10.1109/TIT.2004.833361
G Cohen I Honkala S Litsyn A Lobstein (1997) Covering codes. North-Holland Mathematical Library, 54 North-Holland Publishing Co. Amsterdam
Fontaine C (1998). Contribution à la recherche de fonctions booléennes hautement non linéaires et au marquage d’images en vue de la protection des droits d’auteur, Thèse, Université Paris VI
G Halász (1973) ArticleTitleOn a result of Salem and Zygmund concerning random polynomials Studia Sci Math Hungar 8 369–377 Occurrence Handle367545
FJ MacWilliams NJA Sloane (1977) The theory of error-correcting codes North-Holland Amsterdam Occurrence Handle0369.94008
D Olejár M Stanek (1998) ArticleTitleOn cryptographic properties of random Boolean functions J.UCS 4 IssueID8 705–717 Occurrence Handle1654139 Occurrence Handle0967.68059
N Patterson D Wiedemann (1983) ArticleTitleThe covering radius of the (215, 16) Reed-Muller code is at least 16 276 IEEE Trans Inform Theory 29 IssueID3 354–356 Occurrence Handle712397 Occurrence Handle10.1109/TIT.1983.1056679 Occurrence Handle0505.94021
F Rodier (2004) ArticleTitleSur la non-linéarité des fonctions booléennes Acta Arithmetica 115 1–22 Occurrence Handle1115.94011 Occurrence Handle2102802 Occurrence Handle10.4064/aa115-1-1
Rodier F (2003). On the nonlinearity of Boolean functions, In: Augot D, Charpin P, Kabatianski G (eds), Proceedings of WCC2003, Workshop on coding and cryptography 2003 INRIA pp 397–405.
Chuan-Kun Wu (1998) ArticleTitleOn distribution of Boolean functions with nonlinearity ≤2n-2 Australas J Combin 17 51–59 Occurrence Handle0906.94015 Occurrence Handle1626267
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by J.D. Key
AMS Classification (2000) Primary: 11T71 · Secondary: 06E30 · 42A05 · 94C10
Rights and permissions
About this article
Cite this article
Rodier, F. Asymptotic Nonlinearity of Boolean Functions. Des Codes Crypt 40, 59–70 (2006). https://doi.org/10.1007/s10623-005-6363-8
Received:
Revised:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/s10623-005-6363-8