Theoretical Backgrounds of Applied Discrete Mathematics
A lower bound for the distance between a bijunctive function and a function with the fixed algebraic immunity
A. V. Pokrovskiy Lomonosov Moscow State University, Moscow, Russia
Abstract:
Let
$f=f(x_1,\ldots,x_n)$ be a bijunctive Boolean function, that is, the multiplication of some disjunctions of two variables or their negations, $L_f=\{i_1,\ldots,i_{|L_f|}\}\subset\{1,\ldots,n\}$, and, for $\mathbf{y}=(y_1,\ldots,y_{|L_f|})\in\mathbb{F}_2^{|L_f|}$, the Boolean function
$f_{i_1,\ldots,i_{|L_f|}}^{y_1,\ldots,y_{|L_f|}}$ obtained by substitution of
$y_1,\ldots,y_{|L_f|}$ instead of
$x_{i_1},\ldots,x_{i_{|L_f|}}$ respectively into
$f(x_1,\ldots,x_n)$ is not const and is equivalent relatively the Jevons group to the function
$$
f_{d_{\mathbf{y}},m_{\mathbf{y}}}(\mathbf{x})=
\begin{cases}
(x_1\vee x_2)\cdot\ldots\cdot (x_{2d_{\mathbf{y}}-1}\vee x_{2d_{\mathbf{y}}})\cdot x_{2d_{\mathbf{y}}+1}\cdot\ldots\cdot x_{2d_{\mathbf{y}}+m_{\mathbf{y}}},\ \hbox{if}~1\leq d_{\mathbf{y}}\leq \lfloor n/2\rfloor,\\
\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad\ 1\leq m_{\mathbf{y}}\leq n-2d_{\mathbf{y}};\\
x_1\cdot\ldots\cdot x_m, \quad\hbox{if}~d_{\mathbf{y}}=0,1\leq m_{\mathbf{y}}\leq n; \\
(x_1\vee x_2)\cdot\ldots\cdot (x_{2d_{\mathbf{y}}-1}\vee x_{2d_{\mathbf{y}}}), \quad\hbox{if}~1\leq d_{\mathbf{y}}\leq \lfloor n/2\rfloor,m_{\mathbf{y}}=0.
\end{cases}
$$
Let
$f_0=f_0(x_1,\ldots,x_n)$ be a Boolean function with the algebraic immunity AI
$(f_0)$ satisfying the condition
$1<k=\text{AI}(f_0)-2|L_f|$, $C=|\{(y_1,\ldots,y_{|L_f|})\in\mathbb{F}_2^{|L_f|}:f_{i_1,\ldots,i_{|L_f|}}^{y_1,\ldots,y_{|L_f|}}=\mathrm{const}\}|$, and dist
$(f,f_0)$ is the Hamming distance between
$f$ and
$f_0$. Then
\begin{gather*}
C\textstyle\sum\limits_{i=0}^{\mathrm{AI}(f_0)-2|L_f|-1}\binom{n-|L_f|}{i}+\sum\limits_{\substack{\mathbf{y}\in\mathbb{F}_2^{|L_f|}:\\f_{i_1,\ldots,i_{|L_f|}}^{y_1,\ldots,y_{|L_f|}}\neq\mathrm{const}}}\left(\sum_{i=0}^{k-1}\binom{n-|L_f|}{i}+\right.\\
+\textstyle\sum\limits_{p=0}^{n-|L_f|-2d_{\mathbf{y}}-m_{\mathbf{y}}}\sum\limits_{j=2d_{\mathbf{y}}+m_{\mathbf{y}}+p-k+1}^{d_{\mathbf{y}}}\left(2^j\binom{d_{\mathbf{y}}}{j}\binom{n-|L_f|-2d_{\mathbf{y}}-m_{\mathbf{y}}}{p}\right)-\\
-\left.\textstyle\sum\limits_{p=0}^{n-|L_f|-2d_{\mathbf{y}}-m_{\mathbf{y}}}\sum\limits_{j=0}^{k-1-p}\left(2^j\binom{d_{\mathbf{y}}}{j}\binom{n-|L_f|-2d_{\mathbf{y}}-m_{\mathbf{y}}}{p}\right)\right)\leq\mathrm{dist}(f,f_0).
\end{gather*}
In cryptography, functions like
$f_0$ and
$f$ are widely used for solving systems of Boolean equations by respectively linearization and statistical approximation methods.
Keywords:
algebraic immunity, bijunctive functions, nonlinearity, annihilator, distance between functions.
UDC:
519.1,
519.7
DOI:
10.17223/20710410/34/3