SpringerLink - Journal Article

Boolean functions of an odd number of variables with maximum algebraic immunity

Li Na ¹ and Qi WenFeng ¹

(1)	Department of Applied Mathematics, Zhengzhou Information Engineering University, Zhengzhou, 450002, China

Received: 15 July 2006 Accepted: 15 March 2007

Abstract In this paper, we study Boolean functions of an odd number of variables with maximum algebraic immunity. We identify three classes of such functions, and give some necessary conditions of such functions, which help to examine whether a Boolean function of an odd number of variables has the maximum algebraic immunity. Further, some necessary conditions for such functions to have also higher nonlinearity are proposed, and a class of these functions are also obtained. Finally, we present a sufficient and necessary condition for Boolean functions of an odd number of variables to achieve maximum algebraic immunity and to be also 1-resilient.

Keywords algebraic attacks - algebraic immunity - nonlinearity - correlation immunity

Supported by the National Natural Science Foundation of China (Grant No. 60673081) and the “863” project (Grant No. 2006AA01Z417)

Li Na
Email: mylina_1980@yahoo.com.cn

References

1.	Courtois N, Meier W. Algebraic attacks on stream ciphers with linear feedback. In: Advances in Cryptology — EUROCRYPT 2003, LNCS 2656. Berlin, Heidelberg: Springer, 2003. 345–359

2.	Courtois N. Fast algebraic attacks on stream ciphers with linear feedback. In: Advances in Cryptology — CRYPTO 2003, LNCS 2729. Berlin, Heidelberg: Springer, 2003. 176–194

3.	Armknecht F, Krause M. Algebraic attacks on combiners with memory. In: Advances in Cryptology — CRYPTO 2003, LNCS 2729. Berlin, Heidelberg: Springer, 2003. 162–175

4.	Meier W, Pasalic E, Carlet C. Algebraic attacks and decomposition of Boolean functions. In: Advances in Cryptology — EUROCRYPT 2004, LNCS 3027. Berlin, Heidelberg: Springer, 2004. 474–491

5.	Dalai D K, Gupta K C, Maitra S. Results on algebraic immunity for cryptographically significant Boolean functions. In: Progress in Cryptology — INDOCRYPT 2004, LNCS 3348. Berlin, Heidelberg: Springer, 2004. 92–106

6.	Lobanov M. Tight bound between nonlinearity and algebraic immunity. Available at http://eprint.iacr.org/2005/441

7.	Braeken A, Preneel B. On the algebraic immunity of symmetric Boolean functions. In: Progress in Cryptology — INDOCRYPT 2005, LNCS 3797. Berlin, Heidelberg: Springer, 2005. 35–48

8.	Carlet C. A method of constructionof balanced functions with optimum algebraic immunity. Available at http://eprint.iacr.org/2006/149

9.	Dalai D K, Gupta K C, Maitra S. Cryptographically significant Boolean functions: construction and analysis in terms of algebraic immunity. In: FSE 2005, LNCS 3557. Berlin, Heidelberg: Springer, 2005. 98–111

10.	Dalai D K, Maitra S, Sarkar S. Basic theory in construction of Boolean functions with maximum possible annihilator immunity. In: Designs, Codes and Cryptography, Netherlands: Springer. 2006, 40(1): 41–58

11.	Li N, Qi W F. Construction and count of Boolean functions of an odd number of variables with maximum algebraic immunity. Available at http://arxiv.org/abs/cs.CR/0605139

12.	Qu L J, Feng G Z, Li C. On the Boolean functions with maximum possible algebraic immunity: construction and a lower bound of the count. http://eprint.iacr.org/2005/449

13.	Li N, Qi W F. Symmetric Boolean function with maximum algebraic immunity depending on an odd number of variables. IEEE Trans. Inf. Theory, 2006, 52(5): 2271–2273

14.	Qu L J, Li C, Feng K Q. A note on symmetric Boolean functions with maximum algebraic immunity in odd number of variables. Submitted

15.	Dalai D K, Maitra S. Reducing the number of homogeneous linear equations in finding annihilators. In: Sequences and Their Applications — SETA 2006, LNCS 4086, Berlin, Heidelberg: Springer, 2006. 376–390

16.	MacWilliams F J, Sloane N J A. The Theory of Error-Correcting Codes. North-Holland: Elsevier, 1977