Paper 2009/460

Asymptotic enumeration of correlation-immune boolean functions

E. Rodney Canfield, Zhicheng Gao, Catherine Greenhill, Brendan D. McKay, and Robert W. Robinson

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, 2^{n-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 will 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. ~

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Keywords
boolean functions
Contact author(s)
csg @ unsw edu au
History
2009-09-20: received
Short URL
https://ia.cr/2009/460
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/460,
      author = {E.  Rodney Canfield and Zhicheng Gao and Catherine Greenhill and Brendan D.  McKay and Robert W.  Robinson},
      title = {Asymptotic enumeration of correlation-immune boolean functions},
      howpublished = {Cryptology ePrint Archive, Paper 2009/460},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/460}},
      url = {https://eprint.iacr.org/2009/460}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.