×

A conjecture about binary strings and its applications on constructing Boolean functions with optimal algebraic immunity. (English) Zbl 1226.94013

Based on a combinatorial conjecture on binary strings, the authors establish two classes of Boolean functions with algebraic immunity. The functions in the first class are bent, and it can be concluded that the algebraic immunity of bent functions can take all possible values except one. The functions in the second class are balanced, and they have optimal algebraic degree.

MSC:

94A60 Cryptography
05B10 Combinatorial aspects of difference sets (number-theoretic, group-theoretic, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Armknecht F.: Improving fast algebraic attacks. In: 11th International Workshop on Fast Software Encryption, FSE 2004. Lecture Notes in Computer Science, vol. 3017, pp. 65–82 (2004). · Zbl 1079.68536
[2] 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 (2006). · Zbl 1129.94015
[3] Carlet C.: On a weakness of the Tu-Deng function and its repair. Cryptology ePrint Archive, Report 2009/606. http://eprint.iacr.org/2009/606 .
[4] Carlet C., Feng K.: An infinite class of balanced functions with optimal algebraic immunity, good immunity to fast algebraic attacks and good nonlinearity. In: Advances in Cryptology, Asiacrypt 2008. Lecture Notes in Computer Science, vol. 5350, pp. 425–440 (2008). · Zbl 1206.94060
[5] Carlet C., Zeng X., Li C., Hu L.: Further properties of several classes of Boolean functions with optimum algebraic immunity. Des. Codes Cryptogr. 52, 303–338 (2009) · Zbl 1174.94012 · doi:10.1007/s10623-009-9284-0
[6] Courtois N.T.: 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 (2003). · Zbl 1122.94365
[7] Courtois N.T., 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 (2003). · Zbl 1038.94525
[8] Cusick T.W., Li Y., Stănică P.: On a combinatoric conjecture. Cryptology ePrint Archive, Report 2009/554. http://eprint.iacr.org/2009/554 .
[9] Dalai D.K., Gupta K.C., Maitra S.: Results on algebraic immunity for cryptographically significant Boolean functions. In: Progress in Cryptology, Indocrypt 2004. Lecture Notes in Computer Science, vol. 3348, pp. 92–106 (2005). · Zbl 1115.94007
[10] Dalai D.K., Maitra S., Sarkar S.: Basic theory in construction of boolean functions with maximum possible annihilator immunity. Des. Codes Cryptogr. 40, 41–58 (2006) · Zbl 1202.94179 · doi:10.1007/s10623-005-6300-x
[11] Dillon J.F.: Elementary Hadamard Difference Sets. PhD thesis, University of Maryland (1974). · Zbl 0346.05003
[12] Gong G.: On existence and invariant of algebraic attacks. The Centre for Applied Cryptographic Research (CACR) at the University of Waterloo, Canada, Technical Report CORR 2004-17. http://www.cacr.math.uwaterloo.ca .
[13] Li N., Qi W.: 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 (2006). · Zbl 1172.94584
[14] Li N., Qu L., Qi W., Feng G., Li C., Xie D.: On the construction of Boolean functions with optimal algebraic immunity. IEEE Trans. Inform. Theory 54, 1330–1334 (2008) · Zbl 1306.94070 · doi:10.1109/TIT.2007.915914
[15] Lobanov M.: Exact relation between nonlinearity and algebraic immunity. Discrete Math. Appl. 16, 453–460 (2006) · Zbl 1121.94020 · doi:10.1515/156939206779238418
[16] MacWilliams F.J., Sloane N.J.A.: The Theory of Error-Correcting Codes. North-Holland, Amsterdam (1977) · Zbl 0369.94008
[17] 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 (2004). · Zbl 1122.94041
[18] Rothaus O.S.: On bent functions. J. Combin. Theory A 20, 300–305 (1976) · Zbl 0336.12012 · doi:10.1016/0097-3165(76)90024-8
[19] Stanley R.P.: Enumerative Combinatorics, vol. 1. Cambridge University Press, Cambridge (1997)
[20] Tu Z., Deng Y.: Boolean functions with algebraic immunity one (Submitted). · Zbl 1249.94040
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.