Annihilators and Algebraic Immunity of Symmetric Boolean Functions

作者：Peng Jie^*; Kan Haibin

来源：IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences, 2011, E94A(6): 1434-1440.

DOI：10.1587/transfun.E94.A.1434

• stream cipher
• algebraic attack
• algebraic immunity
• correlation immune
• weight support
• symmetric Boolean function
• palindromic Boolean function

In this paper, we deal with the algebraic immunity of the symmetric Boolean functions. The algebraic immunity is a property which measures the resistance against the algebraic attacks on symmetric ciphers. It is well known that the algebraic immunity of the symmetric Boolean functions is completely determined by a narrow class of annihilators with low degree which is denoted by G(n, inverted right perpendicularn/2inverted left perpendicular). We study and determine the weight support of part of these functions. Basing on this, we obtain some relations between the algebraic immunity of a symmetric Boolean function and its simplified value vector. For applications, we put forward an upper bound on the number of the symmetric Boolean functions with algebraic immunity at least d and prove that the algebraic immunity of the symmetric palindromic functions is not high.

• 出版日期2011-6
• 单位复旦大学