Constructing Even-Variable Symmetric Boolean Functions with High Algebraic Immunity

Yuan LI  Hui WANG  Haibin KAN  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E94-A   No.1   pp.362-366
Publication Date: 2011/01/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E94.A.362
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Cryptography and Information Security
Keyword: 
algebraic attacks,  algebraic immunity,  symmetric Boolean functions,  construction,  count,  

Full Text: PDF>>
Buy this Article




Summary: 
In this paper, we explicitly construct a large class of symmetric Boolean functions on 2k variables with algebraic immunity not less than d, where integer k is given arbitrarily and d is a given suffix of k in binary representation. If let d = k, our constructed functions achieve the maximum algebraic immunity. Remarkably, 2⌊ log2k ⌋ + 2 symmetric Boolean functions on 2k variables with maximum algebraic immunity are constructed, which are much more than the previous constructions. Based on our construction, a lower bound of symmetric Boolean functions with algebraic immunity not less than d is derived, which is 2⌊ log2d ⌋ + 2(k-d+1). As far as we know, this is the first lower bound of this kind.