A lower bound for the distance between a bijunctive function and a function with the fixed algebraic immunity

A. V. Pokrovskiy

Prikladnaâ diskretnaâ matematika, no. 4 (2016), pp. 38-49

Résumé

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$, $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.

Détail

Keywords: algebraic immunity, bijunctive functions, nonlinearity, annihilator, distance between functions.