Abstract
Based on a method proposed by the first author, several classes of balanced Boolean functions with optimum algebraic immunity are constructed, and they have nonlinearities significantly larger than the previously best known nonlinearity of functions with optimal algebraic immunity. By choosing suitable parameters, the constructed n-variable functions have nonlinearity \({2^{n-1}-{n-1\choose\frac{n}{2}-1}+2{n-2\choose\frac{n}{2}-2}\Big/(n-2)}\) for even \({n\geq 8\,{\rm and}\,2^{n-1}-{n-1\choose\frac{n-1}{2}}+\Delta(n)}\) for odd n, where Δ(n) is a function increasing rapidly with n. The algebraic degrees of some constructed functions are also discussed.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Armknecht F.: Improving fast algebraic attacks. In: Fast Software Encryption. Lecture Notes in Computer Science, vol. 3017, pp. 65–82. Springer, Berlin (2004).
Braeken A., Preneel B.: On the algebraic immunity of symmetric Boolean functions. In: Progress in Cryptology-INDOCRYPT 2004. Lecture Notes in Computer Science, vol. 3797, pp. 35–48. Springer, New York (2005).
Canteaut A.: Open problems related to algebraic attacks on stream ciphers. In: Coding and Cryptography. Lecture Notes in Computer Science, vol. 3969, pp. 120–134. Springer, Berlin (2006).
Canteaut A., Trabbia M.: Improved fast correlation attacks using parity-check equations of weight 4 and 5. In: Advances in Cryptology-EUROCRYPT 2000. Lecture Notes in Computer Science, vol. 1807, pp. 573–588. Springer, Berlin (2000).
Carlet C.: On the higher order nonlinearities of algebraic immune functions. In: Advances in Cryptology-CRYPTO 2006. Lecture Notes in Computer Science, vol. 4117, pp. 584–601. Springer, Berlin (2006).
Carlet C.: A method of construction of balanced functions with optimum algebraic immunity. In: Proceedings of the International Workshop on Coding and Cryptography, The Wuyi Mountain, Fujiang, China, 11–15 June 2007. Series of Coding and Cryptology, vol. 4. World Scientific Publishing Co., Singapore (2008).
Carlet C.: Boolean functions for cryptography and error correcting codes. In: Crama Y., Hammer P. (eds.) Boolean Methods and Models. Cambridge University Press, Cambridge (in press).
Carlet C., Dalai D.K., Gupta K.C., Maitra S.: Algebraic immunity for cryptographically significant Boolean functions: analysis and construction. IEEE Trans. Inform. Theory 52(7), 3105–3121 (2006)
Cho J.Y., Pieprzyk J.: Algebraic attacks on SOBER-t32 and SOBER-128. In: Fast Software Encryption. Lecture Notes in Computer Science, vol. 3017, pp. 49–64. Springer (2004).
Courtois N.: Fast algebraic attacks on stream ciphers with linear feedback. In: Advances in Cryptology-CRYPTO 2003. Lecture Notes in Computer Science, vol. 2729, pp. 176–194. Springer, Berlin (2003).
Courtois N., Meier W.: Algebraic attacks on stream ciphers with linear feedback. In: Advances in Cryptology-EUROCRYPT 2003. Lecture Notes in Computer Science, vol. 2656, pp. 345–359. Springer, Berlin (2003).
Courtois N., Pieprzyk J.: Cryptanalysis of block ciphers with overdefined systems of equations. In: Advances in Cryptology-ASIACRYPT 2002. Lecture Notes in Computer Science, vol. 2501, pp. 267–287. Springer, Berlin (2002).
Dalai D.K., Gupta K.C., Maitra S.: Cryptographically significant Boolean functions: construction and analysis in terms of algebraic immunity. In: Fast Software Encryption. Lecture Notes in Computer Science, vol. 3557, pp. 98–111. Springer, Berlin (2005).
Dalai D.K., Maitra S., Sarkar S.: Basic theory in construction of Boolean functions with maximum possible annihilator immunity. Des. Codes Cryptogr. 40(1), 41–58 (2006)
Ding C., Xiao G., Shan W.: The Stability Theory of Stream Ciphers. Lecture Notes in Computer Science, vol. 561. Springer, Berlin (1991).
Lee D.H., Kim J., Hong J., Han J.W., Moon D.: Algebraic attacks on summation generators. In: Fast Software Encryption. Lecture Notes in Computer Science, vol. 3017, pp. 34–48. Springer, Berlin (2004).
Li N., Qi W.F.: Construction and analysis of Boolean functions of 2t + 1 variables with maximum algebraic immunity. In: Advances in Cryptology-ASIACRYPT 2006. Lecture Notes in Computer Science, vol. 4284, pp. 84–98. Springer, Berlin (2006).
MacWilliams F.J., Sloane N.J.: The Theory of Error-Correcting Codes. North-Holland, Amsterdam, New York (1977).
Matsui M.: Linear cryptanalysis method for DES cipher. In: Advances in Cryptology-EUROCRYPT 1993. Lecture Notes in Computer Science, vol. 765, pp. 386–397. Springer, Berlin (1994).
Meier W., Pasalic E., Carlet C.: Algebraic attacks and decomposition of Boolean functions. In: Advances in Cryptology-EUROCRYPT 2004. Lecture Notes in Computer Science, vol. 3027, pp. 474–491. Springer, Heidelberg (2004).
Rønjom S., Helleseth T.: A new attack on the filter generator. IEEE Trans. Inform. Theory 53(5), 1752–1758 (2007)
Siegenthaler T.: Correlation-immunity of nonlinear combining functions for cryptographic applications. IEEE Trans. Inform. Theory 30(5), 776–780 (1984)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by P. Wild.
Rights and permissions
About this article
Cite this article
Carlet, C., Zeng, X., Li, C. et al. Further properties of several classes of Boolean functions with optimum algebraic immunity. Des. Codes Cryptogr. 52, 303–338 (2009). https://doi.org/10.1007/s10623-009-9284-0
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10623-009-9284-0