A Note on the Algebraic Immunity of the Enhanced Boolean Functions

Deng TANG  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E103-A   No.1   pp.366-369
Publication Date: 2020/01/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.2019EAL2049
Type of Manuscript: LETTER
Category: Cryptography and Information Security
Keyword: 
stream cipher,  enhanced Boolean function,  balancedness,  algebraic immunity,  

Full Text: FreePDF(267.2KB)


Summary: 
In 2015, Carlet and Tang [Des. Codes Cryptogr. 76(3): 571-587, 2015] proposed a concept called enhanced Boolean functions and a class of such kind of functions on odd number of variables was constructed. They proved that the constructed functions in this class have optimal algebraic immunity if the numbers of variables are a power of 2 plus 1 and at least sub-optimal algebraic immunity otherwise. In addition, an open problem that if there are enhanced Boolean functions with optimal algebraic immunity and maximal algebraic degree n-1 on odd variables n≠2k+1 was proposed. In this letter, we give a negative answer to the open problem, that is, we prove that there is no enhanced Boolean function on odd n≠2k+1 variables with optimal algebraic immunity and maximal algebraic degree n-1.