|
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.
Citation:
A. V. Pokrovskiy, “A lower bound for the distance between a bijunctive function and a function with the fixed algebraic immunity”, Prikl. Diskr. Mat., 2016, no. 4(34), 38–49
Linking options:
https://www.mathnet.ru/eng/pdm563 https://www.mathnet.ru/eng/pdm/y2016/i4/p38
|
Statistics & downloads: |
Abstract page: | 131 | Full-text PDF : | 69 | References: | 31 |
|