|
Discrete Functions
Improved estimates for the number of $(n, m, k)$-resilient and correlation-immune Boolean mappings
K. N. Pankov Moscow Technical University of Communications and Informatics
Abstract:
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}. $$
Keywords:
distributed ledger, blockchain, information security, resilient vectorial Boolean function, correlation-immune function.
Citation:
K. N. Pankov, “Improved estimates for the number of $(n, m, k)$-resilient and correlation-immune Boolean mappings”, Prikl. Diskr. Mat. Suppl., 2021, no. 14, 48–51
Linking options:
https://www.mathnet.ru/eng/pdma528 https://www.mathnet.ru/eng/pdma/y2021/i14/p48
|
Statistics & downloads: |
Abstract page: | 116 | Full-text PDF : | 43 | References: | 23 |
|