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.

Bibliographie

[1] Gorshkov S. P., “Application of the NP-complete Problems Theory for Estimating the Complexity of Solving Systems of Boolean Equations”, Obozrenie Prikladnoy i Promyshlennoy Matematiki, Ser. Diskr. Mat., 2:3 (1995), 325–398 (in Russian) | MR

[2] Tarasov A. V., “On the properties of functions representable in the form of a 2-CNF”, Diskr. Mat., 13:4 (2001), 99–115 (in Russian) | DOI | MR | Zbl

[3] Lobanov M. S., On the Relations between the Nonlinearity and Algebraic Immunity of Boolean Functions, PhD Thesis, MSU Publ., M., 2009 (in Russian)

[4] Meier W., Pasalic E., and Carlet C., “Algebraic attacks and decomposition of Boolean functions”, EUROCRYPT'04, LCNS, 3027, 2004, 474–491 | MR | Zbl

[5] Dalai D. K., On Some Necessary Conditions of Boolean Functions to Resist Algebraic Attacks, PhD Thesis, Kolkata, 2006, 139 pp.

[6] Buryakov M. L., Algebraic, Combinatorial, and Cryptographic Properties of Parameters of Boolean functions Affine Restrictions, PhD Thesis, MSU Publ., M., 2008 (in Russian)