Abstract
In this paper, we study the construction of (2t+1)-variable Boolean functions with maximum algebraic immunity, and we also analyze some other cryptographic properties of this kind of functions, such as nonlinearity, resilience. We first identify several classes of this kind of functions. Further, some necessary conditions of this kind of functions which also have higher nonlinearity are obtained. In this way, a modified construction method is proposed to possibly obtain (2t+1)-variable Boolean functions which have maximum algebraic immunity and higher nonlinearity, and a class of such functions is also obtained. Finally, we present a sufficient and necessary condition of (2t+1)-variable Boolean functions with maximum algebraic immunity which are also 1-resilient.
This work was supported by National Nature Science Foundation of China under Grant number 60373092.
Chapter PDF
Similar content being viewed by others
References
Armknecht, F.: Improving fast algebraic attacks. In: Roy, B., Meier, W. (eds.) FSE 2004. LNCS, vol. 3017, pp. 65–82. Springer, Heidelberg (2004)
Armknecht, F., Krause, M.: Algebraic attacks on combiners with memory. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 162–175. Springer, Heidelberg (2003)
Braeken, A., Preneel, B.: On the Algebraic Immunity of Symmetric Boolean Functions. In: Maitra, S., Veni Madhavan, C.E., Venkatesan, R. (eds.) INDOCRYPT 2005. LNCS, vol. 3797, pp. 35–48. Springer, Heidelberg (2005)
Carlet, C.: A method of construction of balanced functions with optimum algebraic immunity (2006), Available at: http://eprint.iacr.org/2006/149
Courtois, N.: Fast algebraic attacks on stream ciphers with linear feedback. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 176–194. Springer, Heidelberg (2003)
Courtois, N., Meier, W.: Algebraic attacks on stream ciphers with linear feedback. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 345–359. Springer, Heidelberg (2003)
Dalai, D.K., Gupta, K.C., Maitra, S.: Results on Algebraic Immunity for Cryptographically Significant Boolean Functions. In: Canteaut, A., Viswanathan, K. (eds.) INDOCRYPT 2004. LNCS, vol. 3348, pp. 92–106. Springer, Heidelberg (2004)
Dalai, D.K., Gupta, K.C., Maitra, S.: Cryptographically Significant Boolean Functions: Construction and Analysis in Terms of Algebraic Immunity. In: Gilbert, H., Handschuh, H. (eds.) FSE 2005. LNCS, vol. 3557, pp. 98–111. Springer, Heidelberg (2005)
Dalai, D.K., Maitra, S., Sarkar, S.: Basic theory in construction of Boolean functions with maximum possible annihilator immunity. Designs, Codes and Cryptography 40, 41–58 (2006)
Dalai, D.K., Maitra, S.: Reducing the Number of Homogeneous Linear Equations in Finding Annihilators (2006), Available at: http://eprint.iacr.org/2006/032
Ding, C., Xiao, G., Shan, W.: The stability theory of stream ciphers. Springer, Heidelberg (1991)
Li, N., Qi, W.F.: Symmetric Boolean functions depending on an odd number of variables with maximum algebraic immunity. IEEE Transaction on Information Theory 52(5), 2271–2273 (2006)
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
Lobanov, M.: Tight bound between nonlinearity and algebraic immunity (2005), Available at: http://eprint.iacr.org/2005/441
MacWilliams, F.J., Sloane, N.J.A.: The theory of error-correcting codes. Elsevier, North-Holland (1977)
Meier, W., Pasalic, E., Carlet, C.: Algebraic Attacks and Decomposition of Boolean Functions. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 474–491. Springer, Heidelberg (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Li, N., Qi, WF. (2006). Construction and Analysis of Boolean Functions of 2t+1 Variables with Maximum Algebraic Immunity. In: Lai, X., Chen, K. (eds) Advances in Cryptology – ASIACRYPT 2006. ASIACRYPT 2006. Lecture Notes in Computer Science, vol 4284. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11935230_6
Download citation
DOI: https://doi.org/10.1007/11935230_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-49475-1
Online ISBN: 978-3-540-49476-8
eBook Packages: Computer ScienceComputer Science (R0)