Annihilators and Algebraic Immunity of Symmetric Boolean Functions

Jie PENG  Haibin KAN  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E94-A   No.6   pp.1434-1440
Publication Date: 2011/06/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E94.A.1434
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Cryptography and Information Security
stream cipher,  algebraic attack,  algebraic immunity,  correlation immune,  weight support,  symmetric Boolean function,  palindromic Boolean function,  

Full Text: PDF(283.7KB)>>
Buy this Article

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,). 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.