A systematic method of constructing Boolean functions with optimal algebraic immunity based on the generator matrix of the Reed–Muller code
详细信息 查看全文
- 作者：Sihong Su (1) (2)
Xiaohu Tang (1)
Xiangyong Zeng (3) - 关键词：Boolean functions ; Algebraic immunity ; Reed–Muller code ; Generator matrix ; Nonlinearity ; 94A60 ; 05B10
- 刊名：Designs, Codes and Cryptography
- 出版年：2014
- 出版时间：September 2014
- 年：2014
- 卷：72
- 期：3
- 页码：653-673
- 全文大小：
- 参考文献：1. Armknecht F.: Improving fast algebraic attacks. In: Fast Software Encryption 2004. Lecture Notes in Computer Science, vol. 3017. Springer, Berlin, pp. 65-2 (2004).
2. Canteaut A.: Open problems related to algebraic attacks on stream ciphers. In: Workshop on Coding and Cryptography 2005. Lecture Notes in Computer Science, vol. 3969. Springer, Berlin, pp. 120-34 (2006).
3. Carlet C.: A method of construction of balanced functions with optimum algebraic immunity. In: International Workshop on Coding and Cryptology, pp. 25-3, 2007.
4. Carlet C.: Constructing balanced functions with optimum algebraic immunity. In: IEEE International Symposium on Information Theory 2007, pp. 451-55.
5. 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. Springer, Berlin, pp. 425-40 (2008).
6. Carlet C., Gaborit P.: On the construction of balanced Boolean functions with a good algebraic immunity. In: Proceeding of IEEE International Symposium on Information Theory (ISIT) 2005, pp. 1101-105, 2005.
7. Carlet C., Dalai D., Gupta K., Maitra S.: Algebraic immunity for cryptographically significant Boolean functions: analysis and construction. IEEE Trans. Inf. Theory, 52, 3105-121 (2006).
8. 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-38 (2009).
9. Courtois N.: Fast algebraic attacks on stream ciphers with linear feedback. In: Advances in Cryptology-CRYPTO 2003. Lecture Notes in Computer Science, vol. 2729. Springer, Berlin, pp. 176-94 (2003).
10. Courtois N., Meier W.: Algebraic attacks on stream ciphers with linear feedback. In: EUROCRYPT 2003. Lecture Notes in Computer Science, vol. 2656. Springer, Berlin, pp. 345-59 (2003).
11. Dalai D., Maitra S.: Reducing the number of homogeneous linear equations in finding annihilators. In: Sequences and Their Applications 2006. Lecture Notes in Computer Science, vol. 4086. Springer, Berlin, pp. 376-90 (2006).
12. Dalai D., Gupta K., Maitra S.: Cryptographically significant Boolean functions: construction and analysis in terms of algebraic immunity. In: Workshop on Fast Software Encryption, FSE 2005. Lecture Notes in Computer Science, vol. 3557. Springer, Berlin, pp. 98-11 (2005).
13. Dalai D., Gupta K., Maitra S.: Notion of algebraic immunity and its evaluation related to fast algebraic attacks. In: Second International Workshop on Boolean Functions: Cryptography and Applications, BFCA 2006, Cryptology ePrint Archive, Report 2006/018. http://eprint.iacr.org/2006/018.pdf.
14. Dalai D., Maitra S., Sarkar S.: Basic theory in construction of Boolean functions with maximum possible annihilator immunity. Des. Codes Cryptogr. 40, 41-8 (2006).
15. Ding C., Xiao G., Shan W.: The Stability Theory of Stream Ciphers. Springer, Berlin (1991).
16. Dong D., Fu S., Qu L., Li C.: A new construction of Boolean functions with maximum algebraic immunity. In: ISC 2009. Lecture Notes in Computer Science, vol. 5735. Springer, Berlin, pp. 177-85 (2009).
17. Feng K., Liao Q., Yang J.: Maximal values of generalized algebraic immunity. Des. Codes Cryptogr. 50, 243-52 (2009).
18. Hawkes P., Rose G.: Rewriting variables: The complexity of fast algebraic attacks on stream ciphers. In: Advances in Cryptology-CRYPTO 2004. Lecture Notes in Computer Science, vol. 3152. Springer, Berlin, pp. 390-06 (2004).
19. Limniotis K., Kolokotronis N., Kalouptsidis N.: Constructing Boolean functions in odd number of variables with maximum algebraic immunity. In: Proceeding of IEEE International Symposium on Information Theory (ISIT) 2011, pp. 2662-666, 2011.
20. Lobanov M.: Tight bound between nonlinearity and algebraic immunity. In: Cryptology ePrint Archive, Report 2005/441. http://eprint.iacr.org/2005/441.pdf.
21. Meier W., Staffelbach O.: Fast correlation attacks on stream ciphers. In: Advances in Cryptology-EUROCRYPT 1988. Lecture Notes in Computer Science, vol. 330. Springer, Berlin, pp. 301-14 (1988).
22. 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. Springer, Berlin, pp. 474-91 (2004).
23. Muller D.: Application of Boolean algebra to switching circuit design and to error detection. IEEE Trans. Comput. 3, 6-2 (1954).
24. Peng J., Wu Q., Kan H.: On symmetric Boolean functions with high algebraic immunity on even number of variables. IEEE Trans. Inf. Theory, 57, 7205-220 (2011).
25. Qu L., Feng K., Liu F., Wang L.: Constructing symmetric Boolean functions with maximum algebraic immunity. IEEE Trans. Inf. Theory 55, 2406-412 (2009).
26. Reed S.: A class of multiple-error-correcting codes and the decoding scheme. IEEE Trans. Inf. Theory 4, 38-9 (1954).
27. Sarkar S., Maitra S.: Construction of rotation symmetric Boolean functions with maximun algebraic immunity on odd number of variables. In: AAECC 2007. Lecture Notes in Computer Science, vol. 4851. Springer, Berlin, pp. 271-80 (2007).
28. Tang D., Carlet C., Tang X.: Highly nonlinear Boolean functions with optimal algebraic immunity and good behavior against fast algebraic attacks. IEEE Trans. Inf. Theory, to be published (2012).
29. Zeng X., Carlet C., Shan J., Hu L.: More balanced Boolean functions with optimal algebraic immunity and good nonlinearity and resistance to fast algebraic attacks. IEEE Trans. Inf. Theory 57, 6310-320 (2011). - 作者单位：Sihong Su (1) (2)
Xiaohu Tang (1)
Xiangyong Zeng (3)
1. Information Security and National Computing Grid Laboratory, Southwest Jiaotong University, Chengdu, 610031, China
2. School of Mathematics and Information Sciences, Henan University, Kaifeng, 475004, China
3. Faculty of Mathematics and Computer Science, Hubei University, Wuhan, 430062, China - ISSN：1573-7586
文摘
Because of the recent algebraic attacks, optimal algebraic immunity is now an absolutely necessary (but not sufficient) property for Boolean functions used in stream ciphers. In this paper, we firstly determine the concrete coefficients in the linear expression of the column vectors with respect to a given basis of the generator matrix of Reed–Muller code, which is an important tool for constructing Boolean functions with optimal algebraic immunity. Secondly, as applications of the determined coefficients, we provide simpler and direct proofs for two known constructions. Further, we construct new Boolean functions on odd variables with optimal algebraic immunity based on the generator matrix of Reed–Muller code. Most notably, the new constructed functions possess the highest nonlinearity among all the constructions based on the generator matrix of Reed–Muller code, although which is not as good as the nonlinearity of Carlet–Feng function. Besides, the ability of the new constructed functions to resist fast algebraic attacks is also checked for the variable \(n=11,13\) and 15.