On the Number of Balanced Even-Variable Boolean Functions with Maximum Algebraic Immunity

Abstract:

Enumeration of Boolean functions with maximum algebraic immunity (MAI) is investigated in this paper. The even-variable Boolean functions with maximum AI were divided into 3 classes. First, we can obtain the number of the first two classes, and then we give a construction which provides large number of Boolean functions with maximum AI belong to the third classes. As a result, the lower bound on the number of balanced even-variable Boolean functions with maximum AI was improved.

• Periodical: Applied Mechanics and Materials (Volumes 58-60)
• Pages: 1647-1650
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.58-60.1647
• Online since: June 2011
• Authors: Hai Xin, Shao Jing Fu, Chao Li
• Keywords: Algebraic Attack, Algebraic Immunity, Boolean Function, Lower Bound, Stream Cipher

References

[1] Armknecht F.: Improving fast algebraic attacks, FSE 2004, LNCS 3017, Springer Verlag (2004), pp.65-82.

[2] Courtois N. Meier W.: Algebraic attacks on stream ciphers with linear feedback, Advances in Cryptology-EUROCRYPT 2003, LNCS 2656, Springer Verlag(2003), pp.345-359.

DOI: 10.1007/3-540-39200-9_21

[3] Meier W, Pasalic E, Carlet C.: Algebraic attacks and decomposition of Boolean functions, Advances in Cryptology-EUROCRYPT 2004，LNCS 3027, Springer Verlag(2004), pp.474-491.

DOI: 10.1007/978-3-540-24676-3_28

[4] Dalai D. K.: Basic theory in construction of Boolean functions with maximum possible annihilator immunity， Designs, Codes and Cryptography, Vol. 40(2006)，, pp.41-58.

DOI: 10.1007/s10623-005-6300-x

[5] Carlet C.: A method of construction of balanced functions with optimal algebraic immunity, Coding and Cryptography(2007), pp.25-43.

[6] Li N. and Qu L. J. etc.: On the Construction of Boolean Functions with Optimal Algebraic Immunity，IEEE Transactions on Information Theory，Vol. 53(2008), pp.1330-1334.

DOI: 10.1109/tit.2007.915914

[7] Carlet C. and Feng K. Q.: An infinite class of balanced functions with optimal algebraic immunity，good immunity to fast algebraic attacks and good nonlinearity, ASIACRYPT 2008, LNCS 5350，Springer Verlag(2008)，pp.425-440.

DOI: 10.1007/978-3-540-89255-7_26

[8] Dalai D. K.: Cryptographically significant Boolean functions; construction and analysis in terms of algebraic immunity, FSE 2005，LNCS 3557, Springer Verlag (2005), pp.98-111.

DOI: 10.1007/11502760_7

[9] Carlet C. ，Dalai D. K. ，Gupta K. C. and Maitra S.: Algebraic Immunity for Cryptographically Significant Boolean Functions：Analysis and Construction，IEEE Transactions on Information Theory，Vol. 52(2006), pp.3105-3121.

DOI: 10.1109/tit.2006.876253

[10] Qu L. J., Li C., and Feng K. Q.: A Note on Symmetric Boolean Functions with Maximum Algebraic Immunity in Odd Number of Variables, IEEE Transactions on Information Theory, Vol. 53(2007), pp.2908-2910.

DOI: 10.1109/tit.2007.901189

[11] Qu L. J., Feng K. Q. Liu F. and Wang L. Construction Symmetric Boolean Functions with Maximum Algebraic Immunity, IEEE Transactions on Information Theory, Vol. 55(2009), pp.2406-2412.

DOI: 10.1109/tit.2009.2015999

[12] Carlet C. and Zeng X. Y.: Further properties of several classes of Boolean functions with optimum AI，Design, Codes, Cryptography，Vol. 52(2009), pp.303-338.

DOI: 10.1007/s10623-009-9284-0

[13] Carlet C. : On the higher order nonlinearities of algebraic immune functions, In Advances in Cryptology - CRYPTO 2006, LNCS 4117, Springer-Verlag(2006), pp.584-601.

DOI: 10.1007/11818175_35

[14] Liu M. C., Du Y. S., Pei D. Y. and Lin D. D.: On Designated-weight Boolean Functions with Highest Algebraic immunity，2009, manuscript.

[15] Dalai D. K., Gupta K. C. and Maitra S.: Results on algebraic immunity for cryptographically significant Boolean functions, in Advances in Cryptography-INDOCRYPT 2004, LNCS 3348, Springer-Verlag, (2004), pp.92-106.

DOI: 10.1007/978-3-540-30556-9_9