Theoretical Foundations of Applied Discrete Mathematics

An improved upper bound for the number of plateaued binary mappings

K. N. Pankov


Abstract: This paper presents a refined formulation for the distribution of a part of the vector of spectral coefficients of linear combinations of coordinate functions of a random binary mapping. Using this result, a theorem is obtained that allows one to estimate from above the probability that a randomly selected binary mapping is plateaued for some values of the mapping parameters. Let for an arbitrary $0<\gamma < {1}/{3}$ for all sufficiently large $n$ be $k( {5+2\log _2 n})+6m\le n( {{1}/{3}-\gamma } )$, $k\log_2(ne) - (k-1/2)\log_2k < r < {n}/{2}$, $k < 2n\gamma/\ln n$, and the function $f:\{0,1\}^n\to\{0,1\}^m$ be chosen randomly and with equal probability. Let $\Pi(r)$ denote the set of all plateaued binary mappings of order $2r$. Then the following inequality is true:
\begin{gather*} \Pr\left[f(x) \in \Pi(r) \right] \le\\ \le \left(\exp(-0{,}1 \cdot 2^{n\gamma + m -\log_2n})\theta_4 + \theta_5\frac{\exp(-0{,}12 \cdot 2^{n\gamma+3k-\log_2n})} {\exp_2(T(n,m,k))}|\Re(m)|^{M(n,k)} \right)\times \\ \times 3^{M(n,k)(2^m - 1)} + \frac{\left( {1 + {\theta _6}{n^{ - 3/2}}{2^{ - 4m}}} \right)|\Re(m)|^{M(n,k)}}{\exp_2(T(n,m,k))}{\left( {1 + 2{e^{ - {2^{n - 2r - 1}}}}} \right)^{M(n,k)(2^m-1)}}, \end{gather*}
where
\begin{gather*} \Re (m)=\Bigr\{r =\left(r_J: \emptyset \ne J\subset \{1,\ldots,m\} \right) \in \left( \mathbb{Z}_{2^{m-1}} \right)^{2^{m}-1}:\\ \forall s\in \{1,\ldots,m\} \forall \delta \in V_m \textstyle\sum\limits_{J\subset \{1,\ldots,m\},s\in J} {(-1)^{(\delta ,\psi_m(J))}r_J } =0 \Bigr\}; \end{gather*}
$|\theta_1(a)|\le 1$; $|\theta_2(a)|\le 286{,}9$; $|\theta_3(a)|\le 1$. This theorem allows one to obtain upper bounds for the number of plateaued mappings, improving the results obtained by the author earlier.

Keywords: information security, cryptography, spectral coefficient, local limit theorem, plateaued binary mapping, upper bound.

UDC: 519.214

DOI: 10.17223/2226308X/18/8