Abstract
A boolean function of n boolean variables is correlation-immune of order k if the function value is uncorrelated with the values of any k of the arguments. Such functions are of considerable interest due to their cryptographic properties, and are also related to the orthogonal arrays of statistics and the balanced hypercube colourings of combinatorics. The weight of a boolean function is the number of argument values that produce a function value of 1. If this is exactly half the argument values, that is, 2n − 1 values, a correlation-immune function is called resilient. An asymptotic estimate of the number N(n,k) of n-variable correlation-immune boolean functions of order k was obtained in 1992 by Denisov for constant k. Denisov repudiated that estimate in 2000, but we show that the repudiation was a mistake. The main contribution of this paper is an asymptotic estimate of N(n,k) which holds if k increases with n within generous limits and specialises to functions with a given weight, including the resilient functions. In the case of k = 1, our estimates are valid for all weights.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ahlfors, L.V.: Complex Analysis. An Introduction to the Theory of Analytic Functions of One Complex Variable, 3rd edn. McGraw-Hill, New York (1978)
Bach, E.: Improved asymptotic formulas for counting correlation-immune Boolean functions. SIAM J. Discrete Math. 23, 1525–1538 (2009)
Carlet, C.: Boolean functions for cryptography and error correcting codes. In: Crama, Y., Hammer, P. (eds.) Boolean Models and Methods in Mathematics, Computer Science, and Engineering. Cambridge University Press, Cambridge (2010, in press)
Carlet, C., Gouget, A.: An upper bound on the number of m-resilient Boolean functions, ASIACRYPT 2002. Lect. Notes Comput. Sci. 2501, 484–496 (2002)
Carlet, C., Klapper, A.: Upper bounds on the number of resilient functions and of bent functions. In: Proceedings of the 23rd Symposium on Information Theory in the Benelux, Louvain-La-Neuve, Belgium (2002)
Cusick, T.W., Stanica, P.: Cryptographic Boolean Functions and Applications. Elsevier, Amsterdam (2009)
Denisov, O.V.: An asymptotic formula for the number of correlation-immune of order q boolean functions. Discrete Math. Appl. 2, 279–288 (1992). Originally published in Diskretnaya Matematika 3, 25–46 (1990) (in Russian). Translated by A.V. Kolchin
Denisov, O.V.: A local limit theorem for the distribution of a part of the spectrum of a random binary function. Discrete Math. Appl. 10, 87–101 (2000). Originally published in Diskretnaya Matematika 12, 1 (2000) (in Russian). Translated by the author
Heydayat, A.S., Sloane, N.J.A., Stufken, J.: Orthogonal Arrays: Theory and Applications. Springer, New York (1999)
Maitra, S., Sarkar, P.: Enumeration of correlation immune boolean functions, ACSIP’99. Lect. Notes Comput. Sci. 1587, 12–25 (1999)
Maitra, S., Sarkar, P.: Hamming weights of correlation immune Boolean functions. Inf. Process. Lett. 71, 149–153 (1999)
Mitchell, C.: Enumerating Boolean functions of cryptographic significance. J. Cryptol. 2, 155–170 (1990)
Palmer, E.M., Read, R.C., Robinson, R.W.: Balancing the n-cube: a census of colorings. J. Algebr. Comb. 1, 257–273 (1992)
Park, S.M., Lee, S.J., Sung, S.H., Kim, K.J.: Improving bounds for the number of correlation immune Boolean functions. Inf. Process. Lett. 61, 209–212 (1997)
Roy, B.: A brief outline of research on correlation immune functions, ACISP 2002. Lect. Notes Comput. Sci. 2384, 379–394 (2002)
Sarkar, P.: A note on the spectral characterization of correlation immune Boolean functions. Inf. Process. Lett. 74, 191–195 (2000)
Schneider, M.: A note on the construction and upper bounds of correlation-immune functions. In: Proceedings of the conference cryptography and coding (Cirencester, 1997). Lect. Notes Comput. Sci. 1355, 295–306 (1997)
Tarannikov, Y.: On the structure and numbers of higher order correlation-immune functions. In: Proceedings of IEEE International Symposium on Information Theory, p. 185 (2000)
Tarannikov, Y., Kirienko, D.: Spectral analysis of high order correlation immune functions. In: Proceedings of 2001 IEEE International Symposium on Information Theory, p. 69 (2001)
Wong, R.: Asymptotic Approximations of Integrals. Academic, Boston (1989)
Xiao, G.-Z., Massey, J.L.: A spectral characterization of correlation-immune combining functions. IEEE Trans. Inf. Theory 34, 569–571 (1988)
Yang, Y.X., Guo, B.: Further enumerating Boolean functions of cryptographic significance. J. Cryptol. 8, 115–122 (1995)
Zhang, J.-Z., You, Z.-S., Li, Z.-L.: Enumeration of binary orthogonal arrays of strength 1. Discrete Math. 239, 191–198 (2001)
Author information
Authors and Affiliations
Corresponding author
Additional information
Research of E. Rodney Canfield supported by the NSA Mathematical Sciences Program.
Research of Brendan D. McKay supported by the Australian Research Council.
Research of Zhicheng Gao supported by NSERC.
Rights and permissions
About this article
Cite this article
Canfield, E.R., Gao, Z., Greenhill, C. et al. Asymptotic enumeration of correlation-immune boolean functions. Cryptogr. Commun. 2, 111–126 (2010). https://doi.org/10.1007/s12095-010-0019-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12095-010-0019-x