Cryptology ePrint Archive: Report 2005/449

On the Boolean functions With Maximum Possible Algebraic Immunity : Construction and A Lower Bound of the Count

Longjiang Qu and Guozhu Feng and Chao Li

Abstract: This paper gives a construction method which can get a large class of Boolean functions with maximum algebraic immunity(AI) from one such giving function. Our constructions get more functions than any previous construction. The cryptographic properties, such as balance, algebraic degree etc, of those functions are studied. It shows that we can construct Boolean functions with better cryptographic properties, which gives the guidance for the design of Boolean functions to resist algebraic attack, and helps to design good cryptographic primitives of cryptosystems. From these constructions, we show that the count of the Boolean functions with maximum AI is bigger than ${2^{2^{n-1}}}$ for $n$ odd, bigger than ${2^{2^{n-1}+\frac{1}{2}\binom{n}{\frac{n}{2}} }}$ for $n$ even, which confirms the computer simulation result that such boolean functions are numerous. As far as we know, this is the first bound about this count.

Category / Keywords: foundations / Algebraic Attack, Algebraic Degree, Algebraic Immunity, Annihilator, Balance, Boolean Functions

Date: received 25 Nov 2005, last revised 7 Apr 2006

Contact author: ljqu_happy at hotmail com

Available format(s): PDF | BibTeX Citation

Version: 20060408:023007 (All versions of this report)

Short URL: ia.cr/2005/449

Discussion forum: Show discussion | Start new discussion