Improved asymptotic estimates for the number of correlation-immune Boolean functions and mappings

K. N. Pankov

Prikladnaya Diskretnaya Matematika. Supplement, no. 11 (2018), pp. 49-52.

Résumé

For linear combinations of coordinate functions of a random Boolean mapping from the vectorspace $V_n$ of all binary vectors of length $n$ to the vectorspace $V_m$, the local limit theorem for the joint distribution of weights of some their subfunctions is improved. By means of this theorem, we have obtained an asymptotic formula for $|K(m,n,k)|$ that is the number of correlation-immune of order $k$ functions as $n\to\infty$, $m\in\{2,3,4\}$ and $k(5+2\log_2n)+6m\le n(\frac5{18}-\gamma')$ for any $0\gamma'5/18$, $k=\mathrm O(n/\ln n)$: \begin{gather*} \log _2|K(m,n,k)|\sim m2^n+\left(\frac{n+1+\log_2\pi}2-k\right)(2^m-1)-m2^{m-1}-\\ -(2^m-1)\left(\frac{n-k}2{n\choose k}+\log_2\sqrt\frac\pi2\sum_{s=0}^k{n\choose s}\right)+(2\cdot3^{m-2}-1)\sum_{s=0}^k{n\choose s}. \end{gather*} Also, we have obtained improved asymptotic estimates for the number $|K(n,1,k)|$ as $n\to\infty$, $k\frac n{\ln n}\left(\frac{\ln2}4-\varepsilon\right)$ for any $0\varepsilon\ln2/4$: \begin{gather*} \log_2|K[n,1,k]|\sim2^n-\frac12\left((n-k){n\choose k}-n\right)-k-\\ -\left(\frac{n-k}2{n\choose k}+\sum_{s=0}^k{n\choose s}\log_2\sqrt\frac\pi2-1\right)\log_2\sqrt{\pi/2}. \end{gather*}

Détail

Keywords: random binary mapping, local limit theorem, weights of subfunctions, correlation-immune function.

Bibliographie

[1] Razvitie tekhnologii raspredelennykh reestrov, Doklad dlya obschestvennykh konsultatsii, , Tsentralnyi bank Rossiiskoi Federatsii, M., 2017 http://www.cbr.ru/Content/Document/File36007/reestr_survey.pdf

[2] Logachev O. A., Salnikov A. A., Smyshlyaev S. V., Yaschenko V. V., Bulevy funktsii v teorii kodirovaniya i kriptologii, MTsNMO, M., 2012

[3] Carlet C., “Vectorial Boolean functions for cryptography”, Boolean Models and Methods in Mathematics, Computer Science, and Engineering, Encyclopedia of Mathematics and its Applications, 134, Cambridge University Press, N.Y., 2010, 398–472

[4] Pankov K. N., “Otsenki skorosti skhodimosti v predelnykh teoremakh dlya sovmestnykh raspredelenii chasti kharakteristik sluchainykh dvoichnykh otobrazhenii”, Prikladnaya diskretnaya matematika, 2012, no. 4(18), 14–30

[5] Sachkov V. N., Kurs kombinatornogo analiza, NITs “Regulyarnaya i khaoticheskaya dinamika”, Izhevsk, 2013

[6] Denisov O. V., “Lokalnaya predelnaya teorema dlya raspredeleniya chasti spektra sluchainoi dvoichnoi funktsii”, Diskretnaya matematika, 12:1 (2000), 82–95 | DOI | MR | Zbl

[7] Pankov K. N., “Asimptoticheskie otsenki dlya chisel dvoichnykh otobrazhenii s zadannymi kriptograficheskimi svoistvami”, Matematicheskie voprosy kriptografii, 5:4 (2014), 73–97 | DOI

[8] Pankov K. N., “Lokalnaya predelnaya teorema dlya raspredeleniya chasti vektora vesov podfunktsii komponent sluchainogo dvoichnogo otobrazheniya”, Matematicheskie voprosy kriptografii, 5:3 (2014), 49–80 | DOI

[9] Canfield E. R., Gao Z., Greenhill C., et al., “Asymptotic enumeration of correlation-immune Boolean functions”, Cryptography and Communications, 2:1 (2010), 111–126 | DOI | MR | Zbl

[10] Pankov K. N., “Utochnënnye asimptoticheskie otsenki dlya chisla $(n,m,k)$-ustoichivykh dvoichnykh otobrazhenii”, Prikladnaya diskretnaya matematika. Prilozhenie, 2017, no. 10, 46–49