Some results on the algebraic immunity of Boolean functions

doi:10.1016/S1005-8885(10)60051-9

中国邮电高校学报(英文) ›› 2011, Vol. 18 ›› Issue (2): 102-105.doi: 10.1016/S1005-8885(10)60051-9

• Artificial Intelligence • 上一篇下一篇

Some results on the algebraic immunity of Boolean functions

许丽卿,陈豪

华东师范大学

收稿日期:2010-06-17 修回日期:2010-11-07 出版日期:2011-04-30 发布日期:2011-04-15
通讯作者: 陈豪 E-mail: haochen@sei.ecnu.edu.cn
基金资助:
流密码代数攻击研究

Some results on the algebraic immunity of Boolean functions

Received:2010-06-17 Revised:2010-11-07 Online:2011-04-30 Published:2011-04-15

摘要/Abstract

摘要：

From the motivation of algebraic attacks on stream and block ciphers, the concept of algebraic immunity (AI) of a Boolean function was introduced and studied extensively. High algebraic immunity is a necessary condition for resisting algebraic attacks. In this paper, we give some lower bounds on the algebraic immunity of Boolean functions. The results are applied to give lower bounds on the AI of symmetric Boolean functions and rotation symmetric Boolean functions. Some balanced rotation symmetric Boolean functions with their AI near the maximum possible value ?n/2? are constructed.

关键词:

algebraic attack, Boolean function, AI, symmetric Boolean function, rotation symmetric Boolean function

Abstract:

Key words:

algebraic attack, Boolean function, AI, symmetric Boolean function, rotation symmetric Boolean function

中图分类号:

TN918.1

参考文献

1. Carlet C. Boolean functions for cryptography and error correcting codes. Cambridge, UK:Cambridge University Press, 2007

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

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

4. Canteaut A. Open problems related to algebraic attacks on stream ciphers. Proceedings of the International Workshop on Coding and Cryptography(WCC’05), Mar 14-18, 2005,Bergen, Norway: LNCS 3969. Berlin, Germany: Springer-Verlag, 2005: 120-134

5. Courtois N,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

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

7. Courtois N, Pieprzyk J. Cryptanalysis of block ciphers with overdetermined 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. Meier W,Pasalic C,Carlet C. Algebraic attacks and decomposition of Boolean functions. Advances in Cryptology: Proceedings of the 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

9. Armknecht F. On the existence of low-degree equations for algebraic attacks. Cryptology ePrint Archive, Report 2004/185

10. Carlet C,Dalai D K,Gupta K C, et al. Algebraic immunity for cryptographically significant Boolean functions analysis and construction. IEEE Transactions on Information Theory, 2006, 52(7): 3105-3121

11. Carlet C.On the higher order nonlinearities of algebraic immune functions. Advances in Crytography: Proceedings of the 26th Annual International Cryptology Conference (Crypto’06), Aug 20-24, 2005, Santa Barbara, CA, USA. LNCS 4117. Berlin, Germany: Springer-Verlag, 2006:584-601

12. Dalai D K,Gupta K C,Maitra S. Results on algebraic immunity of cryptographically significant Boolean functions. 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: 92-106

13. Golic J D. Vectorial Boolean functions and induced algebraic equations. IEEE Transactions on Information Theory, 2006, 52(2): 528-537

14. Gong G. On existence and invariant of algebraic attacks. Advances in Crytography:Proceedings of the 24th Annual International Cryptology Conference (Crypto’04), Aug 15-19, 2004,Santa Barbara, CA, USA. LNCS 3152. Berlin, Germany: Springer-Verlag, 2004

15. Armknecht F,Carlet C,Gaborit P, et al. Efficient computation of algebraic immunity for algebraic and fast algebraic attacks. Advances in Cryptology: Proceedings of the 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt’06), May 28-Jun 1, 2006, St Petersburg, Russia. LNCS 4004. Berlin, Germany: Springer-Verlag, 2006: 147-164

16. Braeken A,Preneel B. On the algebraic immunity of symmetric Boolean functions. Progress in Cryptology: Proceedings of the 6th International Conference on Cryptology in India(Indocrypt’05),Dec 10-12, 2005, Bangalore, India. LNCS 3797. Berlin, Germany: Springer-Verlag, 2005:35-48

17. Carlet C. A method of construction of balanced functions with optimum algebraic immunity. Cryptology ePrint Archive,Report, 2006

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

19. Canteaut A,Videau M. Symmetric Boolean functions. IEEE Transactions on Information Theory, 2005, 51(8): 2791-2811

20. Pieprzyk J, Qu C X. Fast hashing and rotation symmetric functions. Journal of Universal Computer Science, 1999,5(1): 20-31

[1]	谢佳高军涛岳曌李雪莲. Autocorrelation of two Legendre-Sidelnikov sequences[J]. Acta Metallurgica Sinica(English letters), 2014, 21(5): 83-88.
[2]	李富林, ZHU Shi-xin. Computing the k-error joint linear complexity of binary periodic multisequences [J]. Acta Metallurgica Sinica(English letters), 2013, 20(6): 96-101.
[3]	贾艳艳胡予濮赵勇斌高军涛. Correlation power analysis of DECIMv2[J]. Acta Metallurgica Sinica(English letters), 2011, 18(5): 118-123.
[4]	王艳, HU Yu-pu, LI Shun-bo, YANG Yang. Linear complexity of sequences produced by single cycle T-function[J]. Acta Metallurgica Sinica(English letters), 2011, 18(4): 123-128.
[5]	柯品惠张胜元. Constructions of vector output Boolean functions with high generalized nonlinearity[J]. Acta Metallurgica Sinica(English letters), 2008, 15(2): 77-81.
[6]	陈秀波;杜建忠;温巧燕;朱甫臣. Teleportation of an unknown two-particle entangled state via an asymmetric three-particle entanglement state[J]. Acta Metallurgica Sinica(English letters), 2008, 15(1): 102-105.

Some results on the algebraic immunity of Boolean functions

Some results on the algebraic immunity of Boolean functions

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 6

编辑推荐

Metrics

本文评价