A Note on “On the Construction of Boolean Functions with Optimal Algebraic Immunity”

Yuan LI  Haibin KAN  Kokichi FUTATSUGI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E94-A   No.9   pp.1877-1880
Publication Date: 2011/09/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E94.A.1877
Print ISSN: 0916-8508
Type of Manuscript: LETTER
Category: Cryptography and Information Security
Keyword: 
algebraic attacks,  algebraic degree,  algebraic immunity,  Boolean functions,  

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




Summary: 
In this note, we go further on the “basis exchange” idea presented in [2] by using Mobious inversion. We show that the matrix S1(f)S0(f)-1 has a nice form when f is chosen to be the majority function, where S1(f) is the matrix with row vectors υk(α) for all α ∈ 1f and S0(f)=S1(f ⊕ 1). And an exact counting for Boolean functions with maximum algebraic immunity by exchanging one point in on-set with one point in off-set of the majority function is given. Furthermore, we present a necessary condition according to weight distribution for Boolean functions to achieve algebraic immunity not less than a given number.