Construction of Boolean Function with Maximum Algebraic Immunity

Abstract:

To resist algebraic attacks, a high algebraic immunity is now an important criteria for Boolean functions used in stream ciphers. In recent years, several constructions of Boolean functions with maximum algebraic immunity (MAI) have been investigated. In this survey paper, we review the recent constructions of Boolean functions with MAI, and classify those into several different classes by the construction idea. Further, we also present some results and developments of these methods, including some results of the authors.

• Periodical: Advanced Materials Research (Volumes 546-547)
• Pages: 387-392
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.546-547.387
• Online since: July 2012
• Authors: Xiao Wen Xiong, Ai Guo Wei, Kai Yin
• Keywords: Algebraic Attacks, Algebraic Immunity, Boolean Function, Cryptography, Optimal Construction

References

[1] F. Armknecht, "Improving fast algebraic attacks," FSE 2004, LNCS 3017, 2004, pp.65-82.

[2] N. Courtois, W. Meier, "Algebraic attacks on stream ciphers with linear feedback," Cryptology-EUROCRYPT 2003, LNCS 2656, 2003, pp.345-359.

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

[3] N. Courtois, "Fast algebraic attacks on stream ciphers with linear feedback," Cryptology-CRYPTO 2003, LNCS 2729, 2003, pp.176-194.

DOI: 10.1007/978-3-540-45146-4_11

[4] L M. Batten, "Algebraic attacks over GF(q)," Cryptology-INDOCRYPT 2004, LNCS 3348, 2004, pp.84-91.

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

[5] W. Meier, E. Pasalic, C. Carlet, "Algebraic attacks and decomposition of Boolean functions," Cryptology-EUROCRYPT 2004, LNCS 3027, 2004, pp.474-491.

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

[6] D.K. Dalai, "Basic theory in construction of Boolean functions with maximum possible annihilator immunity," Designs, Codes and Cryptography, vol. 40, no. 1, 2006, pp.41-58.

DOI: 10.1007/s10623-005-6300-x

[7] L.J. Qu, C. Li, K.Q. Feng, "A note on symmetric Boolean functions with maximum algebraic immunity in odd number of variables," IEEE Transactions on Information Theory, vol. 53, no. 8, 2007, pp.2908-2910.

DOI: 10.1109/tit.2007.901189

[8] A. Bracken，B. Preneel B, "On the algebraic immunity of symmetric Boolean functions," INDOCRYPT 2005, LNCS 3797，2005, pp.35-48.

DOI: 10.1007/11596219_4

[9] L.J. Qu, K.Q. Feng, F. Liu and L. Wang, "Construction symmetric Boolean functions with maximum algebraic immunity," IEEE Transactions on Information Theory, vol.55, no. 5, 2009, pp.2406-2412.

DOI: 10.1109/tit.2009.2015999

[10] L.J. Qu, C. Li, "On the -variable Symmetric Boolean Functions with Maximum Algebraic Immunity," Science in China Series F-Information Sciences, vol.51, no.2, 2008, pp.120-127.

DOI: 10.1007/s11432-008-0010-8

[11] F. Liu, K.Q. Feng, "On the -variable symmetric Boolean functions with maximum algebraic immunity ," WCC 2007, 2007, pp.225-232.

[12] C. Carlet, "A method of construction of balanced functions with optimum algebraic immunity," the International Workshop on Coding and Cryptography, 2007, pp.25-43.

DOI: 10.1142/9789812832245_0003

[13] C. Carlet and X.Y. Zeng, "Further properties of several classes of Boolean functions with optimum AI," Design, Codes, Cryptography, vol. 52, no. 3, 2009, pp.303-338.

DOI: 10.1007/s10623-009-9284-0

[14] Y.J. Wang, S.Q. Fan, "New construction of Boolean function with optimum Algebraic Immunity," http://eprint.iacr.org/2008/176.pdf.

[15] S.J. Fu, C. Li, K. Matsuura, L.J. Qu, "Construction of Rotation Symmetric Boolean Functions with Maximum Algebraic Immunity," CANS 2009, LNCS 5888, 2009, pp.402-412.

DOI: 10.1007/978-3-642-10433-6_27

[16] X.W. Xiong, A.G. Wei, "Construction of Balanced Rotation Symmetric Boolean Functions with Good Cryptographic Properties," ACSA2011, in press.

[17] N. Li and L.J. Qu, "On the construction of Boolean functions with optimal algebraic immunity," IEEE Transactions on Information Theory, vol. 54, no. 3, 2008, pp.1330-1334.

DOI: 10.1109/tit.2007.915914

[18] N. Li, W.F. Qi, "Construction and Analysis of Boolean Functions of 2t+1 Variables with Maximum Algebraic Immunity," ASIACRYPT 2006, LNCS 4284, 2006, pp.82-98.

DOI: 10.1007/11935230_6

[19] S. Sarkar, S. Maitra, "Construction of Rotation Symmetric Boolean Functions on Odd Number of Variables with Maximum Algebraic Immunity," Algebra，Algebraic Algorithms and Error-Correcting Codes, LNCS 4851, 2007, pp.271-280.

DOI: 10.1007/978-3-540-77224-8_32

[20] C.L. Li, X.Y. Zeng, "A class of rotation symmetric Boolean functions with optimum Algebraic Immunity," Wuhan University Journal of Natural Sciences, vol.13, no.6, 2008, pp.702-706.

DOI: 10.1007/s11859-008-0613-3

[21] M.C. Liu, D.Y. Pei, "Identification and construction of Boolean functions with Maximum Algebraic Immunity," Science in China Series F-Information Sciences, vol. 53, no. 7, 2010, pp.1379-1396.

DOI: 10.1007/s11432-010-3106-x

[22] X.W. Xiong, C. Ma, X. Yang, "Some Results on the Number of Even-variable Boolean Functions with Maximum Algebraic Immunity," ICITIS2011, 2011, pp.281-285.

[23] C. Carlet and K.Q. Feng, "An infinite class of balanced functions with optimal algebraic immunity，good immunity to fast algebraic attacks and good nonlinearity," ASIACRYPT 2008, LNCS 5350, 2007, pp.425-440.

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

[24] Z.R. Tu, Y.P. Deng, "A conjecture on binary string and its applications on constructing Boolean v\ ���������������������������������������������������������������������������������������������������������������������������functions of optimum AI," Designs, Codes and Cryptography, vol. 60, no. 1, 2011, pp.1-14.

DOI: 10.1007/s10623-010-9413-9