This article is cited in 1 paper

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.

UDC: 519.7

DOI: 10.17223/2226308X/14/8