Abstract: Algebraic immunity is one of the most significant cryptographic properties for Boolean functions. In order to resist algebraic attack, high algebraic immunity is necessary for those Boolean functions used in stream ciphers. This paper constructed more than one even-variable rotation symmetric Boolean functions with optimum algebraic immunity by giving an even n. Based on majority function, some orbits of different hamming weights were chosen, then the values of functions on these orbits were changed. Given a sufficient condition of Boolean functions with optimum algebraic immunity, the new constructed Boolean functions were proved to satisfy the condition. Therefore, it shows the algebraic immunity of the functions is optimum. Thus, algebraic attacks can be resisted effectively.

Key words: stream cipher, algebraic attack, rotation symmetric Boolean functions, algebraic immunity, nonlinearity

摘要： 针对目前许多流密码算法无法抵抗代数攻击问题，提出了一种构造代数免疫度最优的偶数元旋转对称布尔函数的新方法。该方法在择多函数的基础上，通过巧妙选择汉明重量不一的若干轨道，并改变这些轨道上的函数值，从而构造出一类新的旋转对称布尔函数。给定布尔函数达到代数免疫度最优的一个充分条件，通过证明新构造的布尔函数满足该充分条件，从而表明该类函数代数免疫度最优，能够有效抵抗代数攻击。

关键词: 流密码, 代数攻击, 旋转对称布尔函数, 代数免疫度, 非线性度