Construction of even-variable rotation symmetric Boolean functions with maximum algebraic immunity

详细信息    查看全文

• 作者：ShaoJing Fu (1) (2)
  Chao Li (1) (3)
  Kanta Matsuura (2)
  LongJiang Qu (1)
  
• 关键词：Boolean function ; rotation symmetry ; algebraic immunity ; nonlinearity
• 刊名：SCIENCE CHINA Information Sciences
• 出版年：2013
• 出版时间：March 2013
• 年：2013
• 卷：56
• 期：3
• 页码：1-9
• 全文大小：193KB
• 参考文献：1. Stanica P, Maitra S. Rotation symmetric Boolean functions—count and cryptographic properties. Electron Notes Discrete Math, 2003, 15: 139-45 CrossRef
  2. Dalai D K, Maitra S, Sarkar S. Results on rotation symmetric bent functions. In: Proceedings of the 2nd International Workshop on Boolean Functions: Cryptography and Applications, Rouen, France, 2006. 137-56
  3. Maximov A, Hell M, Maitra S. Plateaued rotation symmetric Boolean functions on odd number of variables. In: Proceedings of the 1st Workshop on Boolean Functions: Cryptography and Applications, Rouen, France, 2005. 83-04
  4. Stanica P, Maitra S, Clark J. Results on rotation symmetric bent and correlation immune Boolean functions. In: Proceedings of Fast Software Encryption Workshop, Delhi, India, 2004. 161-77
  5. Pieprzyk J, Qu C X. Fast hashing and rotation-symmetric functions. J Univ Comput Sci, 1999, 5: 20-1
  6. Cusick T W, Stanica P. Fast evaluation, weights and nonlinearity of rotation-symmetric functions. Discrete Math, 2002, 258: 289-01 CrossRef
  7. Courtois N, Pieprzyk J. Cryptanalysis of block ciphers with overdefined systems of equations. In: Advances in Cryptology-ASIACRYPT, Queenstown, New Zealand, 2002. 267-87
  8. Courtois N, Meier W. Algebraic attacks on stream ciphers with linear feedback. In: Advances in Cryptology-EUROCRYPT, Warsaw, Poland, 2003. 345-59
  9. Dalai D K, Gupta K C, Maitra S. Results on algebraic immunity for cryptographically significant Boolean functions. In: Proceedings of the 5th International Conference on Cryptology, Chennai, India, 2004. 92-06
  10. Meier W, Pasalic E, Carlet C. Algebraic attacks and decomposition of Boolean functions. In: Advances in Cryptology-EUROCRYPT, Santa Barbara, USA, 2004. 474-91
  11. Carlet C, Zeng X Y, Li C L, et al. Further properties of several classes of Boolean functions with optimum algebraic immunity. Des Codes Cryptogr, 2009, 52: 303-38 CrossRef
  12. Carlet C, Dalai D K, Gupta K C, et al. Algebraic immunity for cryptographically significant Boolean functions: Analysis and construction. IEEE Trans Inf Theory, 2006, 52: 3105-121 CrossRef
  13. Dalai D K, Maitra S, Sarkar S. Basic theory in construction of Boolean functions with maximum possible annihilator immunity. Des Codes Cryptogr, 2006, 40: 41-8 CrossRef
  14. Qu L J, Li C, Feng K Q. A note on symmetric Boolean functions with maximum algebraic immunity in odd number of variables. IEEE Trans Inf Theory, 2007, 53: 2908-910 CrossRef
  15. Qu L J, Feng K Q, Liu F, et al. Constructing symmetric Boolean functions with maximum algebraic immunity. IEEE Trans Inf Theory, 2009, 55: 2406-412 CrossRef
  16. Sarkar S, Maitra S. Construction of rotation symmetric Boolean functions with maximum algebraic immunity on odd number of variables. In: Proceedings of International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting codes, Bangalore, India, 2007. 271-80
  17. Fu S J, Li C, Matsuura K, et al. Construction of rotation symmetric Boolean functions with maximum algebraic immunity. In: Proceedings of the 8th International Conference on Cryptology and Network Security, Kanazawa, Ishikawa, Japan, 2009. 402-12
  18. Sarkar S, Maitra S. Construction of rotation symmetric Boolean functions with optimal algebraic immunity. Comput Syst, 2009, 12: 267-84
  19. Carlet C. A method of construction of balanced functions with optimum algebraic immunity. In: Proceedings of the International Workshop on Coding and Cryptography, The Wuyi Mountain, Fujiang, China, 2007
  
• 作者单位：ShaoJing Fu (1) (2)
  Chao Li (1) (3)
  Kanta Matsuura (2)
  LongJiang Qu (1)
  
  1. Department of Mathematics and System Science, National University of Defense Technology, Changsha, 410073, China
  2. Institute of Industrial Science, University of Tokyo, Tokyo, 153-8505, Japan
  3. State Key Laboratory of Information Security, Graduate University of Chinese Academy of Sciences, Beijing, 100190, China
  
• ISSN：1869-1919

文摘

Rotation symmetric Boolean functions (RSBFs) have been used as components of different cryptosystems. In this paper, we investigate n-variable (n even and n ?12) RSBFs to achieve maximum algebraic immunity (AI), and provide a construction of RSBFs with maximum AI and nonlinearity. These functions have higher nonlinearity than the previously known nonlinearity of RSBFs with maximum AI. We also prove that our construction provides high algebraic degree in some case.