Asymptotic enumeration of correlation-immune Boolean functions. (English) Zbl 1218.05016
Summary: 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 O. V. Denisov [Discrete Math. Appl. 2, No.4, 407–426 (1992); translation from Diskretn. Mat. 3, No.2, 25–46 (1991; Zbl 0735.94012)] for constant \(k\). Denisov repudiated that estimate in 2000 [O.V. Denisov, Discrete Math. Appl. 10, No.1, 87–101 (2000); translation from Diskret. Mat. 12, No.1, 22–95 (2000; Zbl 0968.60020)], 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.
MSC:
| 94D10 | Boolean functions |
| 94C11 | Switching theory, applications of Boolean algebras to circuits and networks |
| 05A16 | Asymptotic enumeration |
References:
| [1] | Ahlfors, L.V.: Complex Analysis. An Introduction to the Theory of Analytic Functions of One Complex Variable, 3rd edn. McGraw-Hill, New York (1978) |
| [2] | Bach, E.: Improved asymptotic formulas for counting correlation-immune Boolean functions. SIAM J. Discrete Math. 23, 1525–1538 (2009) · Zbl 1209.05013 · doi:10.1137/070705520 |
| [3] | 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) · Zbl 1209.94035 |
| [4] | 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) · Zbl 1065.94541 · doi:10.1007/3-540-36178-2_30 |
| [5] | 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) |
| [6] | Cusick, T.W., Stanica, P.: Cryptographic Boolean Functions and Applications. Elsevier, Amsterdam (2009) · Zbl 1359.94001 |
| [7] | 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 |
| [8] | 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 · Zbl 0968.60020 |
| [9] | Heydayat, A.S., Sloane, N.J.A., Stufken, J.: Orthogonal Arrays: Theory and Applications. Springer, New York (1999) · Zbl 0935.05001 |
| [10] | Maitra, S., Sarkar, P.: Enumeration of correlation immune boolean functions, ACSIP’99. Lect. Notes Comput. Sci. 1587, 12–25 (1999) · Zbl 0919.94016 · doi:10.1007/3-540-48970-3_2 |
| [11] | Maitra, S., Sarkar, P.: Hamming weights of correlation immune Boolean functions. Inf. Process. Lett. 71, 149–153 (1999) · Zbl 1005.94033 · doi:10.1016/S0020-0190(99)00091-5 |
| [12] | Mitchell, C.: Enumerating Boolean functions of cryptographic significance. J. Cryptol. 2, 155–170 (1990) · Zbl 0705.94010 · doi:10.1007/BF00190802 |
| [13] | Palmer, E.M., Read, R.C., Robinson, R.W.: Balancing the n-cube: a census of colorings. J. Algebr. Comb. 1, 257–273 (1992) · Zbl 0781.05005 · doi:10.1023/A:1022487918212 |
| [14] | 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) · Zbl 1336.94069 · doi:10.1016/S0020-0190(97)00010-0 |
| [15] | Roy, B.: A brief outline of research on correlation immune functions, ACISP 2002. Lect. Notes Comput. Sci. 2384, 379–394 (2002) · Zbl 1025.94508 · doi:10.1007/3-540-45450-0_29 |
| [16] | Sarkar, P.: A note on the spectral characterization of correlation immune Boolean functions. Inf. Process. Lett. 74, 191–195 (2000) · Zbl 1339.94063 · doi:10.1016/S0020-0190(00)00063-6 |
| [17] | 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) · Zbl 0904.94013 · doi:10.1007/BFb0024475 |
| [18] | 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) · Zbl 1063.94534 |
| [19] | 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) |
| [20] | Wong, R.: Asymptotic Approximations of Integrals. Academic, Boston (1989) · Zbl 0679.41001 |
| [21] | Xiao, G.-Z., Massey, J.L.: A spectral characterization of correlation-immune combining functions. IEEE Trans. Inf. Theory 34, 569–571 (1988) · Zbl 0653.94011 · doi:10.1109/18.6037 |
| [22] | Yang, Y.X., Guo, B.: Further enumerating Boolean functions of cryptographic significance. J. Cryptol. 8, 115–122 (1995) · Zbl 0853.94028 |
| [23] | Zhang, J.-Z., You, Z.-S., Li, Z.-L.: Enumeration of binary orthogonal arrays of strength 1. Discrete Math. 239, 191–198 (2001) · Zbl 0983.05007 · doi:10.1016/S0012-365X(01)00045-0 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
