On the construction of odd-variable boolean functions with optimal algebraic immunity

doi:10.1016/S1005-8885(13)60052-7

中国邮电高校学报(英文) ›› 2013, Vol. 20 ›› Issue (3): 73-77.doi: 10.1016/S1005-8885(13)60052-7

• Artificial Intelligence • 上一篇下一篇

On the construction of odd-variable boolean functions with optimal algebraic immunity

张劼

1. School of Science, Beijing University of Posts and Telecommunications, Beijing 100876, China 2. State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China

收稿日期:2012-11-03 修回日期:2013-02-03 出版日期:2013-06-30 发布日期:2013-06-26
通讯作者: 张劼 E-mail:jiezhang@bupt.edu.cn
基金资助:
This work was supported by the National Natural Science Foundation of China (61102093, 61170270, 61121061), The Fundamental Research for the Central Universities (BUPT 2012RC0710).

On the construction of odd-variable boolean functions with optimal algebraic immunity

1. School of Science, Beijing University of Posts and Telecommunications, Beijing 100876, China 2. State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China

Received:2012-11-03 Revised:2013-02-03 Online:2013-06-30 Published:2013-06-26
Supported by:
This work was supported by the National Natural Science Foundation of China (61102093, 61170270, 61121061), The Fundamental Research for the Central Universities (BUPT 2012RC0710).

摘要/Abstract

摘要：

Algebraic immunity is an important cryptographic property of Boolean functions. In this paper, odd-variable balanced Boolean functions with optimal algebraic immunity are obtained by m-sequence and consequently, we get bases with special constructions of vector space. Furthermore, through swapping some vectors of these two bases, we establish all kinds of odd-variable balanced Boolean functions with optimal algebraic immunity.

关键词:

algebraic immunity, Boolean functions, algebraic attacks, annihilators

Abstract:

Key words:

algebraic immunity, Boolean functions, algebraic attacks, annihilators

ZHANG Jie, WEN Qiao-yan. On the construction of odd-variable boolean functions with optimal algebraic immunity[J]. Acta Metallurgica Sinica(English letters), 2013, 20(3): 73-77.

参考文献

1. Armknecht F. Improving fast algebraic attacks. Proceedings of the 11th International Workshop on Fast Software Encryption (FSE’04), Feb 5-7, 2004, Delhi, India. LNCS 3017. Berlin, Germany: Springer-Verlag, 2004: 65-82

2. Courtois N, Meier W. Algebraic attacks on stream ciphers with linear feedback. Advances in Cryptology: Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’03), May 4-8, 2003, Warsaw, Poland. LNCS 2656. Berlin, Germany: Springer-Verlag, 2003: 345-359

3. Armknecht F, Krause M. Algebraic attacks on combiners with memory. Advances in Cryptology: proceedings of the 23rd Annual International Cryptology Conference (Crypto’03), Aug 17-21, 2003, Santa Barbara, CA, USA. LNCS 2729. Berlin, Germany: Springer-Verlag, 2003:162-176

4. Batten L M. Algebraic attacks over GF (q). Progress in Cryptology: Proceedings of the 5th International Conference on Cryptology in India (INDOCRYPT’04), Dec 20-22, 2004, Chennai, India. LNCS 3348. Berlin, Germany: Springer-Verlag, 2004: 84-91

5. Courtois N. Fast algebraic attacks on stream ciphers with linear feedback. Advances in Cryptology: Proceedings of the 23rd Annual International Cryptology Conference (Crypto’03), Aug 17-21, 2003, Santa Barbara, CA, USA. LNCS 2729. Berlin, Germany: Springer-Verlag, 2003: 176-194

6. MeierW, Pasalic E, Carlet C. Algebraic attacks and decomposition of Boolean functions. Advances in Cryptology: Proceedings of the 23rd International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’04), May 2-6, 2004, Interlaken, Switzerland. LNCS 3027.Berlin, Germany: Springer-Verlag, 2004: 474-491

7. Courtois N, Pieprzyk J. Cryptanalysis of block ciphers with overdefined systems of equations. Advances in Cryptology: Proceedings of the 8th International Conference on the Theory and Applications of Cryptology and Information Security (Asiacrypt’02), Dec 1-5, 2002. Queenstown, New Zealand. LNCS 2501. Berlin, Germany: Springer-Verlag, 2002: 267-287

8. Dalai D K, Maitra S, Sarkar S. Basic theory in construction Boolean functions with maximum possible annihilator immunity. Designs, Codes and Cryptography, 2006, 40(1): 41-58.

9. Li N, Qi W F. Symmetric Boolean functions depending on an odd number of variables with maximum algebraic immunity. IEEE Transactions on Information Theory, 2006, 52(5): 2271-2273

10. Qu L J, Li C, Feng K Q. A note on symmetric Boolean functions with maximum algebraic immunity in odd number of variables. IEEE Transactions on Information Theory, 2007, 53(8): 2908-2910

11. Qu L J, Li C. On the 2m-variable symmetric Boolean functions with maximum algebraic immunity. Science in China Series F: Information Sciences, 2008, 51(2):120-127

12. Qu L J, Feng K Q, Liu F, et al.Constructing symmetric Boolean functions with maximum algebraic immunity. IEEE Transactions on Information Theory, 2009, 55(5): 2406-2412

13. Carlet C. A method of construction of balanced Boolean functions with optimum algebraic immunity. Designs, Codes and Cryptography, 2009, 52(3): 303-338

14. Carlet C, Zeng X Y, Li C L, et al. Further properties of several classes of Boolean functions with optimum algebraic immunity. Designs, Codes and Cryptography, 2009, 52(3): 303-338

15. Fu S J, Li C, Matssuura K, et al. Construction of rotation symmetric Boolean functions with maximum algebraic immunity. Cryptology and Network Security: Proceedings of the 8th International Conference on Cryptology and Network Security (CANS’09), Dec 12-14, 2009, Kanazawa, Japan. LNCS 5888. Berlin, Germany: Springer-Verlag, 2009: 402-412

16. Li N, Qu L J, Qi W F, et al. On the construction of Boolean functions with optimal algebraic immunity. IEEE Transactions on Information Theory, 2008, 54(3): 1330-1334

17. Sarkar S, Maitra S. Construction of rotation symmetric Boolean functions with maximum algebraic immunity on odd number of variables. Proceedings of the 17th Applied Algebra, Algebraic Algorithms, and Error Correcting Codes Symposium (AAECC’07), Dec 16-20, 2007, Bangalore, India. LNCS 4851. Berlin, Germany: Springer-Verlag, 2007: 271-280

18. Li C L, Zeng X Y, Su W, et al. A class of rotation symmetric Boolean functions with optimum algebraic immunity. Wuhan University Journal of Natural Science, 2008, 13(6): 702-706

19. Liu M C, Pei D Y, Du Y S. Identification and construction of Boolean functions with maximum algebraic immunity. Science in China Series F: Information Sciences, 2010, 53(7): 1379-1396

20. Tu Z R, Deng Y P. A conjecture on binary string and its applications on constructing Boolean functions of optimum algebraic immunity. Designs, Codes and Cryptography, 2011, 60(1): 1-14

21. Armknecht F, Krause M. Constructing single- and multi-output Boolean functions with maximal algebraic immunity. Proceedings of the 33rd International Colloquium on Automata, Languages and Programming (ICALP’06), Jul 9-16, 2006,Venice, Italy. LNCS4052. Berlin, Germany: Springer-Verlag, 2006: 180-191

22. Feng K Q, Liao Q Y, Yang J. Maximal values of generalized algebraic immunity. Designs, Codes and Cryptography, 2009, 50(2): 243-252

23. Ars G, Faugere J C. Algebraic immunity of functions over finite fields. Proceedings of the 1st International Workshop on Boolean Functions: Cryptography and Applications (BFCA’05), Mar 7-8, 2005, Rouen, France. Berlin, Germany: Springer-Verlag, 2005: 21-38

24. Assmus E F, Key J D Jr. Designs and their codes. New York, NY, USA: Cambridge University Press, 1992

25. Wang Q C, Peng J, Kan H B, et al. Constructions of cryptographically significant Boolean functions using primitive polynomials. IEEE Transactions on Information Theory, 2010, 56(6): 3048-3053

26. Zhang J, Song S C, Du J, et al. On the construction of multi-output Boolean functions with optimal algebraic immunity. Science in China Series F: Information Sciences, 2012, 55(7): 1617-1623

27. Rueppel R A. Analysis and design of stream ciphers. Berlin, Germany: Springer-Verlag, 1986.

On the construction of odd-variable boolean functions with optimal algebraic immunity

On the construction of odd-variable boolean functions with optimal algebraic immunity

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

编辑推荐

Metrics

本文评价