Algebraic immunities of vector-valued functions over finite fields

中国邮电高校学报(英文) ›› 2015, Vol. 22 ›› Issue (5): 16-21.doi:

• Cyber Security • 上一篇下一篇

Algebraic immunities of vector-valued functions over finite fields

刘振华¹,张劼²,温巧燕³

1. Computer science department, China Women's University, Beijing 100101, China 2. School of Science, Beijing University of Posts and Telecommunications, Beijing 100876, China 3. State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China

收稿日期:2014-12-29 修回日期:2015-06-08 出版日期:2015-10-30 发布日期:2015-10-30
通讯作者: 张劼 E-mail:jiezhang@bupt.edu.cn
基金资助:
The work was supported by National Natural Science Foundation of China (60873191, 60903152, 61003286, 60821001).

Algebraic immunities of vector-valued functions over finite fields

1. Computer science department, China Women's University, Beijing 100101, China 2. School of Science, Beijing University of Posts and Telecommunications, Beijing 100876, China 3. State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China

Received:2014-12-29 Revised:2015-06-08 Online:2015-10-30 Published:2015-10-30
Supported by:
The work was supported by National Natural Science Foundation of China (60873191, 60903152, 61003286, 60821001).

摘要/Abstract

摘要：

Algebraic immunity is an important cryptographic property of Boolean functions. The notion of algebraic immunity of Boolean functions has been generalized in several ways to vector-valued functions over arbitrary finite fields. In this paper, the results of Ref. [25] are generalized to arbitrary finite fields. We obtain vector-valued functions over arbitrary finite fields such that their algebraic immunities can reach the upper bounds. Furthermore, all the component functions, together with their some nonzero linear combinations, of vector-valued Boolean functions achieved by this construction have optimal algebraic immunities simultaneously.

关键词:

cryptography, Boolean functions, algebraic immunity, algebraic attacks, annihilator

Abstract:

Key words:

cryptography, Boolean functions, algebraic immunity, algebraic attacks, annihilator

中图分类号:

TN918.2

参考文献

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

2. Courtois N T, Meier W. Algebraic attacks on stream ciphers with linear feedback. Advances in Cryptology: Proceedings of the 22nd 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. Meier W, 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 of Boolean functions with maximum possible annihilator immunity. Designs, Codes and Cryptography, Springer Netherlands, 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. Liao Q Y, Feng K Q, Liu F. On the 2m+1-variable symmetric Boolean functions with sub-maximum algebraic immunity 2m-1. Science in China Series A：Mathematics, 2009, 52(1):17-28

13. 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

14. Carlet C. A method of construction of balanced Boolean functions with optimum algebraic immunity. Proceedings of the 2007 International Workshop on Coding and Cryptology, Jun 11-15, 2007, Wuyi Mountain, China. 2007: 25-43

15. 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

16. Dong D S, Fu S J, Qu L J, et al. A new construction of Boolean functions with maximum algebraic immunity. Proceedings of the 12th International Conference on Information Security (ISC’09), Sept 7-9, 2009, Pisa, Italy. LNCS 5735. Berlin, Germany: Springer-Verlag, 2009: 177-185

17. 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 58888. Berlin, Germany: Springer-Verlag, 2009: 402-412

18. 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

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

20. 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

21. 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

22. 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. LNCS 4052. Berlin, Germany: Springer-Verlag, 2006:180-191

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

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

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

26. 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

Algebraic immunities of vector-valued functions over finite fields

Algebraic immunities of vector-valued functions over finite fields

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

编辑推荐

Metrics

本文评价