Cryptographic Properties of Several Classes of Rotation Symmetric Boolean Functions
Affiliation:

  • Article
  • | |
  • Metrics
  • |
  • Reference [31]
  • |
  • Related [20]
  • |
  • Cited by
  • | |
  • Comments
    Abstract:

    Sumanta Sarkar, et al. give a class of rotation symmetric Boolean functions with maximum algebraic immunity, but only consider the nonlinearity of the functions and did not study other cryptographic properties. In this paper, other cryptographic properties of the class of Boolean functions are studied, such as, algebraic degree, linear structure, propagation, correlation immunity etc. The results, unfortunately, show that their other cryptographic properties are not good even though their algebraic immunity is optimum. Hence, the class of Boolean functions cannot be applied in cryptography.

    Reference
    [1] Armknecht F. Improving fast algebraic attacks. In: Roy B, Meier W, eds. Proc. of the Fast Software Encryption (FSE 2004). LNCS 3017, Berlin: Springer-Verlag, 2004. 65?82.
    [2] Batten LM. Algebraic attacks over GF(q). In: Canteaut A, Viswanathan K, eds. Proc. of the Progress in Cryptology-Indocrypt 2004. LNCS 3348, Berlin: Springer- Verlag, 2004. 84?91.
    [3] Braeken A, Praneel B. Probabilistic algebraic attacks. In: Smart NP, ed. Proc. of the 10th IMA Int’l Conf. on Cryptography and Coding. LNCS 3796, Berlin: Springer-Verlag, 2005. 290?303.
    [4] Cheon J, Lee D. Resistance of S-boxes against algebraic attacks. In: Roy B, Meier W, eds. Proc. of the Fast Software Encryption (FSE 2004). LNCS 3017, Berlin: Springer-Verlag, 2004. 83?94.
    [5] Cho J, Pieprzyk J. Algebraic attacks on SOBER-t32 and SOBER-128. In: Roy B, Meier W, eds. Proc. of the Fast Software Encryption (FSE 2004). LNCS 3017, Berlin: Springer-Verlag, 2004. 49?64.
    [6] Courtois N, Pieprzyk J. Cryptanalysis of block ciphers with overdefined systems of equations. In: Advances in Cryptology- Asiacrypt 2002. LNCS 2501, Berlin: Springer-Verlag, 2002. 267?287. http://eprint.iacr.org/2002/044/
    [7] Courtois N, Meier W. Algebraic attacks on stream ciphers with linear feedback. In: Advances in Cryptology-Eurocrypt 2003. LNCS 2656, Berlin: Springer-Verlag, 2003. 345?359.
    [8] Courtois N. Fast algebraic attacks on stream ciphers with linear feedback. In: Advances in Cryptology-Crypto 2003. LNCS 2729, Berlin: Springer-Verlag, 2003. 176?194.
    [9] Lee D, Kim J, Hong J, Han J, Moon D. Algebraic attacks on summation generators. In: Roy B, Meier W, eds. Proc. of the Fast Software Encryption (FSE 2004). LNCS 3017, Berlin: Springer-Verlag, 2004. 34?48.
    [10] Didier F, Tillich J. Computing the algebraic immunity efficiently. http://www.iacr.org/archive/fse2006/40470362/40470362.pdf
    [11] Courtois N, Debraize B, Garrido E. On exact algebraic [non-]immunity of S-boxes based on power functions. In: Proc. of the Australasian Conf. on Information Security and Privacy (ACISP 2006). LNCS 4058, Berlin: Springer-Verlag, 2006. 76?86. http://eprint.iacr.org/2005/203
    [12] Meier W, Pasalic E, Carlet C. Algebraic attacks and decomposition of Boolean functions. In: Advances in Cryptology-Eurocrypt 2004. LNCS 3027, Berlin: Springer-Verlag, 2004. 474?491. http://www.iacr.org/archive/eurocrypt2004/30270469/finaleurocr.pdf
    [13] Sarkar S, Maitra S. Construction of rotation symmetric Boolean functions with maximum algebraic immunity on odd number of variables. In: Proc. of the Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (AAECC 2007). LNCS 4851, Berlin: Spring-Berlin 2007. 271?280. http://eprint.iacr.org/2007/290.pdf
    [14] Dalai D, Gupta K, Maitra S. Cryptographically significant Boolean functions: Construction and analysis in terms of algebraic immunity. In: Proc. of the Fast Software Encryption (FSE 2005). LNCS 3557, Berlin: Springer-Verlag, 2005. 98?111.
    [15] Dalai D, Maitra S, Sarkar S. Basic theory in construction of Boolean functions with maximum possible annihilator immunity. Design, Codes and Cryptography, 2006,40(1):41?58. http://eprint.iacr.org/2005/229
    [16] Carlet C. A method of construction of balanced functions with optimum algebraic immunity. In: Proc. of the Wuyi Workshop on Coding and Cryptology, Published by World Scientific Publishing Co. in its Series of Coding and Cryptology. 2006. http://eprint.iacr.org/2006/149
    [17] Carlet C, Feng K. An infinite class of balanced functions with optimal algebraic immunity, good immunity to fast algebraic attacks and good nonlinearity. In: Advances in Cryptology-ASIACRYPT 2008. LNCS 5350, Berlin: Springer-Verlag, 2008. 425?440.
    [18] Zhang WY, Wu CK, Liu XZ. Construction and enumeration of Boolean functions with maximum algebraic immunity. Science in China Series F: Information Sciences, 2009,52(1):32?40.
    [19] St?nic? P, Maitra S. Rotation symmetric Boolean functions-count and cryptographic properties. Discrete Applied Mathematics, 2008,156(10):1567?1580.
    [20] St?nic? P, Maitra S, Clark J. Results on rotation symmetric bent and correlation immune Boolean functions. In: Roy B, Meier W, eds. Proc. of the Fast Software Encryption (FSE 2004). LNCS 3017, Berlin: Springer-Verlag, 2004. 161?177.
    [21] Dalai D, Maitra S, St?nic? P. Results on rotation symmetric bent functions. Discrete Mathematics, 2009,309:2398?2409. http://iacr.org/2005/118.ps.gz
    [22] Kavut S, Maitra S, Sarkar S, Yuecel M. Enumeration of 9-variable rotation symmetric Boolean functions having nonlinearity>240. In: Barua R, Lange T, eds. Proc. of the Int’l Conf. on Cryptology in India (INDOCRYPT 2006). LNCS 4329, Berlin: Springer-Verlag, 2006. 266?279.
    [23] St?nic? P, Maitra S. A constructive count of rotation symmetric functions. Information Processing Letters, 2003,88:299?304.
    [24] St?nic? P, Maitra S. Rotation symmetric Boolean functions-count and cryptographic properties. Discrete Applied Mathematics, 2008,156(10):1567?1580.
    [25] Pieprzyk J, Qu C. Fast hashing and rotation-symmetric functions. Journal of Universal Computer Science, 1999,5(1):20?31.
    [26] Evertse J. Linear structures in block ciphers. In: Advances in Cryptology-EUROCRYPT’87. LNCS 304, Berlin: Springer-Verlag, 1988. 249?266.
    [27] Chaum D, Evertse J. Cryptanalysis of DES with a reduced number of rounds sequences of linear factors in block cipher. In: Advances in Cryptology-CRYPTO’85. LNCS 218, Berlin: Springer-Verlag, 1986. 192?211.
    [28] Dunne P, Leng P, Nwana G. On the complexity of Boolean functions computed by lazy oracles. IEEE Trans. on Computers, 1995, 44(4):495?502.
    [29] Schnorr G. The network complexity and the turing machine complexity of finite functions. Acta Informatica, 1976,7:95?107.
    [30] Stockmeyer L. On the combinational complexity of certain symmetric Boolean functions. Mathematical Systems Theory, 1977,10: 323?336.
    [31] Siegenthaler T. Correlation-Immunity of nonlinear combining functions for cryptographic applications. IEEE Trans. on Information Theory, 1984,30(5):776?780.
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

孙光洪,武传坤.几类旋转对称布尔函数的密码学性质.软件学报,2010,21(12):3165-3174

Copy
Share
Article Metrics
  • Abstract:4484
  • PDF: 6584
  • HTML: 0
  • Cited by: 0
History
  • Revised:July 07,2009
You are the first2034066Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063