On the security of the Feng-Liao-Yang Boolean functions with optimal algebraic immunity against fast algebraic attacks (Q1960219)

Let \(\{b_1,\dots,b_n\}\) be a basis of \({\mathbb F}_{2^n}\). By identifying every element \(x = \sum_{i=1}^n x_ib_i\) of \({\mathbb F}_{2^n}\) with the \(n\)-tuple of its coordinates \((x_1,\dots,x_n)\), we define a natural correspondence between Boolean functions and polynomials functions from \( {\mathbb F}_{2^n}\) to \( {\mathbb F}_2\). Further, any nonzero polynomial function \(f : {\mathbb F}_{2^n} \rightarrow {\mathbb F}_2\) can be represented as \[ f(x) = \sum_{i=0}^{2^n-1} f_i x^i, \] where \(f_0,f_{2^n-1} \in {\mathbb F}_2\), and \(f_{2i}= f_i^2\in {\mathbb F}_{2^n}\) \((i=1,\dots,2^n-2)\). We denote by \(w_2(k)\) the number of nonzero coefficients in the binary representation of the positive integer \(k\). The algebraic degree of \(f\) is the largest integer \(w_2(k)\), where \(f_k \neq 0\). A Boolean function \(g\neq 0\) is called annihilator of the \(f\), if \(fg = 0\). The smallest degree of the annihilators of \(f\) and \(f+1\) is called algebraic immunity of \(f\). \textit{K. Feng, Q. Liao} and \textit{J. Yang} introduced an infinite class of Boolean functions with optimal algebraic immunity [Des. Codes Cryptography 50, No. 2, 243--252 (2008; Zbl 1237.94062)]. In [\textit{C. Carlet} and \textit{K. Feng}, Lect. Not. Comput. Sci. 5350, 425--440 (2008; Zbl 1206.94060)], it was proved that the functions of this class have optimum algebraic degree and much better nonlinearity than all the previously obtained infinite classes of Boolean functions with maximal algebraic immunity. In the paper under review the resistance of the Boolean functions of the above class against the so called fast algebraic attacks is investigated. For the purpose the author proposes an efficient method which uses the special characteristic of this family and it is based on the Berlekamp-Massey algorithm.