Improved estimates for the number of $(n, m, k)$-resilient and correlation-immune Boolean mappings

K. N. Pankov

Prikladnaya Diskretnaya Matematika. Supplement, no. 14 (2021), pp. 48-51.

Résumé

Improved lower and upper bounds for $\left| {K\left({n,m,k} \right)} \right|$ (the number of correlation-immune of order $k$ binary mappings) and $\left| {R\left({m,n,k} \right)} \right|$ (the number of $(n,m,k)$-resilient binary mappings) are obtained. By $M\left( {n,k} \right)$ we denote ${\sum\limits_{s=0}^k {\displaystyle{n \choose s}}}$, and by $T\left( {n,m,k} \right)$ — the expression $\left( {2^m-1} \right)\left(\dfrac{n-k}{2}\displaystyle{n \choose k}+M\left( {n,k} \right)\log _2\sqrt {\dfrac{\pi }{2}}\right) $. If $m\geq 5$ and $k\left( 5+2{{\log }_{2}}n \right)+6m\le n\left( {1}/{3}-\gamma \right)$ for fixed $0\gamma {1}/{3}$, then there is $n_0$ such that, for any $\varepsilon_1,\varepsilon_2$ and $n>n_0$, $$ \left( \frac{{{m^2} - m - 12}}{2} + 17 \right)M\left( {n,k} \right)- {\varepsilon _1} \le \log _2\left| {R\left({n,m,k} \right)} \right|-m2^n+T\left( {n,m,k} \right)\le $$ $$ \le \left( {\left( {16m - 47} \right){2^{m - 4}} - m + 3} \right)M\left( {n,k} \right)+{\varepsilon _2}. $$ If $m\geq 5$ and $k\left( 5+2{{\log }_{2}}n \right)+6m\le n\left( {5}/{18}-\gamma \right)$ for fixed $0\gamma {5}/{18}$, then there is $n_0$ such that, for any $\varepsilon_1,\varepsilon_2$ and $n>n_0$, $$ \left( \frac{{{m^2} - m - 12}}{2} + 17 \right)M\left( {n,k} \right)- {\varepsilon _1} \le \log _2\left| {K\left({n,m,k} \right)} \right|-m2^n+m2^{m-1}+T\left( {n,m,k} \right)- $$ $$ -{\left( {\frac{n+1+\log _2 \pi }{2}-k} \right)\left( {2^m-1} \right)}\le \left( {\left( {16m - 47} \right){2^{m - 4}} - m + 3} \right)M\left( {n,k} \right)+{\varepsilon _2}. $$

Détail

Keywords: distributed ledger, blockchain, information security, resilient vectorial Boolean function, correlation-immune function.

Bibliographie

[1] MR 26.4.001-2018 «Terminy i opredeleniya v oblasti tekhnologii tsepnoi zapisi dannykh (blokchein) i raspredelennykh reestrov», Tekhnicheskii komitet po standartizatsii «Kriptograficheskaya zaschita informatsii», M., 2018, 10 pp.

[2] Blokchein-revolyutsiya v bankakh i finansovykh institutakh, Otchet, MINDSMITH, M., 2020 https://mindsmith.io/blockchain-finance/

[3] Kolonka MINDSMITH: Blokchein v zenite leta, 6.08.2020 https://ict.moscow/news/blockchain-trends-mindsmith/

[4] Elistratov A., Marshalko G. B., Svetushkin V., “Podvodnye kamni sertifikatsii blokchein-reshenii”, Otkrytye sistemy. SUBD, 2019, no. 1, 19 pp. | Zbl

[5] Pankov K., “Enumeration of Boolean mapping with given cryptographic properties for personal data protection in Blockchain Data Storage”, Proc. 24th Conf. Open Innovations Assoc., FRUCT (Moscow, Russia, 2019), 300–306

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

[7] Denisov O. V., “Asimptoticheskaya formula dlya chisla korrelyatsionno-immunnykh poryadka $k$ bulevykh funktsii”, Diskretnaya matematika, 1991, no. 2, 25–46 | Zbl

[8] Denisov O. V., “Lokalnaya predelnaya teorema dlya raspredeleniya chasti spektra sluchainoi dvoichnoi funktsii”, Diskretnaya matematika, 2000, no. 1, 82–95

[9] Canfield E. R., Gao Z., Greenhill C., et al., “Asymptotic enumeration of correlation-immune Boolean functions”, Cryptogr. Commun., 2010, no. 1, 111–126 | DOI | MR | Zbl

[10] Potapov V. N., “A lower bound on the number of boolean functions with median correlation immunity”, 16th Int. Symp. “Problems of redundancy in information and control systems” (Moscow, Russia, 2019), 45–46

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

[12] Pankov K. N., “Utochnennye asimptoticheskie otsenki dlya chisla korrelyatsionno-immunnykh dvoichnykh funktsii i otobrazhenii”, Prikladnaya diskretnaya matematika. Prilozhenie, 2018, no. 11, 49–52

[13] Pankov K. N., “Rekurrentnye formuly dlya chisla $k$-elastichnykh i korrelyatsionno-immunnykh dvoichnykh otobrazhenii”, Prikladnaya diskretnaya matematika. Prilozhenie, 2019, no. 12, 62–66

[14] 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

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

[16] Pankov K. N., “Improved asymptotic estimates for the numbers of correlation-immune and $k$-resilient vectorial Boolean functions”, Discr. Math. Appl., 2019, no. 3, 195–213 | DOI | MR | Zbl

[17] Sachkov V. N., Kurs kombinatornogo analiza, NITs «Regulyarnaya i khaoticheskaya dinamika», Izhevsk, 2013, 336 pp.

[18] Pankov K. N., “Uluchshennye asimptoticheskie otsenki dlya chisla korrelyatsionno-immunnykh i $k$-elastichnykh dvoichnykh vektor-funktsii”, Diskretnaya matematika, 2018, no. 2, 73–98