Refined asymptotic estimates for the number of $(n,m,k)$-resilient Boolean mappings

K. N. Pankov

Prikladnaya Diskretnaya Matematika. Supplement, no. 10 (2017), pp. 46-49.

Résumé

For linear combinations of coordinate functions of a random Boolean mapping, a local limit theorem for the distribution of subsets of their spectral coefficients is improved. By means of this theorem, we obtain an asymptotic formula for the $R(m,n,k)|$ –the number of $(n,m,k)$-resilient functions as $n\to\infty$, $m\in\{1,2,3,4\}$ and $k\leq\frac{n(1-\varepsilon)}{5+2\log _2n}$ for any $0\varepsilon 1$, $k=\mathrm O(\frac n{\ln n})$: \begin{gather*} \log _2|R(m,n,k)|\sim m2^n-(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)\mathrm{Ind}\{m\neq1\}\sum_{s=0}^k{n\choose s}. \end{gather*} Also, we obtain upper and lower asymptotic estimates for the number $|R(m,n,k)|$ as $n\to\infty$, $k(5+2\log _2n)+5m\le n(1-\varepsilon)$ for any $0\varepsilon1$: \begin{gather*} -\varepsilon_1(m-1)\sum_{s=0}^k{n\choose s}\log _2|R(m,n,k)|-m2^n+(2^m-1)\left(\frac{n-k}2{n\choose k}+\log_2\sqrt\frac\pi2\sum_{s=0}^k{n\choose s}\right)\\ \varepsilon_2(m-2)(2^m-1)\sum_{s=0}^k{n\choose s}+\sum_{s=0}^k{n\choose s}\qquad\text{for any}\quad\varepsilon_1,\varepsilon_2\quad(0\varepsilon_1,\varepsilon_21). \end{gather*}

Détail

Keywords: random binary mapping, local limit theorem, resilient vector Boolean function.
Mots-clés : spectral coefficient

Bibliographie

[1] Pankov K. N., “Asimptoticheskie otsenki dlya chisel dvoichnykh otobrazhenii s zadannymi kriptograficheskimi svoistvami”, Matematicheskie voprosy kriptografii, 2014, no. 4, 73–97

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

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

[5] Slovar kriptograficheskikh terminov, MTsNMO, M., 2006

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

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

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