On the Lower Block Triangular Nature of the Incidence Matrices to Compute the Algebraic Immunity of Boolean Functions

详细信息    查看全文

• 关键词：Cryptography ; Boolean function ; Power function ; Algebraic immunity
• 刊名：Lecture Notes in Computer Science
• 出版年：2015
• 出版时间：2015
• 年：2015
• 卷：9270
• 期：1
• 页码：79-89
• 全文大小：229 KB
• 参考文献：1. Courtois, N., Meier, W.: Algebraic attacks on stream ciphers with linear feedback. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 345–359. Springer, Heidelberg (2003)
  2.Dalai, D.K.: Computing the rank of incidence matrix and algebraic immunity of boolean functions. IACR Cryptology ePrint Archive, p. 273 (2013)
  3. Dalai, D.K., Gupta, K.C., Maitra, S.: Results on algebraic immunity for cryptographically significant boolean functions. In: Canteaut, A., Viswanathan, K. (eds.) INDOCRYPT 2004. LNCS, vol. 3348, pp. 92–106. Springer, Heidelberg (2004)
  4. Dalai, D.K., Maitra, S.: Reducing the number of homogeneous linear equations in finding annihilators. In: Gong, G., Helleseth, T., Song, H.-Y., Yang, K. (eds.) SETA 2006. LNCS, vol. 4086, pp. 376–390. Springer, Heidelberg (2006)
  5. Didier, F.: Using Wiedemann’s algorithm to compute the immunity against algebraic and fast algebraic attacks. In: Barua, R., Lange, T. (eds.) INDOCRYPT 2006. LNCS, vol. 4329, pp. 236–250. Springer, Heidelberg (2006)
  6.Feng, X., Gong, G.: On algebraic immunity of trace inverse functions over finite fields with characteristic two. Cryptology ePrint Archive, Report 2013/585 (2013). http://​eprint.​iacr.​org/​
  7. Meier, W., Pasalic, E., Carlet, C.: Algebraic attacks and decomposition of boolean functions. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 474–491. Springer, Heidelberg (2004)
  8. Nawaz, Y., Gong, G., Gupta, K.C.: Upper bounds on algebraic immunity of boolean power functions. In: Robshaw, M. (ed.) FSE 2006. LNCS, vol. 4047, pp. 375–389. Springer, Heidelberg (2006)
  
• 作者单位：Deepak Kumar Dalai (14)
  
  14. School of Mathematical Sciences, NISER, Bhubaneswar, 751005, India
  
• 丛书名：Algebraic Informatics
• ISBN：978-3-319-23021-4
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

The incidence matrix between two sets of vectors in \({\mathbb F}_2\) has a great importance in different areas of mathematics and sciences. The rank of these matrices are very useful while computing the algebraic immunity(\(\mathsf{AI}\)) of Boolean functions in cryptography literature [3, 7]. With a proper ordering of monomial (exponent) vectors and support vectors, some interesting algebraic structures in the incidence matrices can be observed. We have exploited the lower-block triangular structure of these matrices to find their rank. This structure is used for faster computation of the \(\mathsf{AI}\) and the low degree annihilators of an n-variable Boolean functions than the known algorithms. On the basis of experiments on at least 20 variable Boolean functions, we conjecture about the characterization of power functions of algebraic immunity 1, could verify the result on the \(\mathsf{AI}\) of n-variable inverse S-box presented in [6](i.e., \(\lceil 2\sqrt{n}\rceil -2\)), and presented some results on the \(\mathsf{AI}\) of some important power S-boxes.