Abstract: Constructing a Boolean function on odd variables for the maximum algebraic immunity is equivalent to finding an invertible submatrix in a given matrix. However, how to find invertible submatrixes efficiently in the matrix remains a problem. In order to solve the problem, the matrix is further studied. The description of the matrix is simplified, and several constructions of Boolean functions on odd variables for the maximum algebraic immunity are introduced. With these constructions, more Boolean functions on odd variables with the maximum algebraic immunity can be efficiently constructed, since one only needs some operations on vectors of low dimension and avoids deciding the invertibility of submatrixes.

Key words: stream cipher, algebraic attack, Boolean function, algebraic immunity

摘要： 构造一个具有最大代数免疫度的奇数元布尔函数等价于在某一已知矩阵中寻找一个可逆子矩阵。如何在这一矩阵中有效地寻找可逆子矩阵仍然是一个难题。针对上述问题研究矩阵的性质，简化矩阵的刻画方式，给出构造最大代数免疫度的奇数元布尔函数的构造方法。构造时只需对低维数的向量进行操作，避免了子矩阵可逆性的判断，能够有效地构造具有最大代数免疫度的奇数元布尔函数。

关键词: 流密码, 代数攻击, 布尔函数, 代数免疫度

CLC Number: 

• TN918.1