×

Distinguishing properties and applications of higher order derivatives of Boolean functions. (English) Zbl 1341.94020

Summary: Higher order differential cryptanalysis is based on a property of higher order derivatives of Boolean functions such that derivative of a Boolean function reduces its degree at least 1 and continuously taking derivatives eventually yields a zero function. A quicker degree reduction means a lower data complexity in cryptanalysis, which can be determined by fast point at which the derivative reduces the degree at least 2.In this paper, we show that the set of the fast points of a Boolean function constitutes a linear subspace and its dimension plus the degree of the function is at most the size of the function. We also show that non-zero fast point exists in every \(n\)-variable Boolean function of degree \(n-1\), every symmetric Boolean function of degree \( d\) where \(n\not\equiv d\,(\bmod\, 2)\) or every quadratic Boolean function of odd number variables, which help us distinguish a few block ciphers and propose a new design principle about degree for block cipher.

MSC:

94A60 Cryptography
06E30 Boolean functions

Software:

Square
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alperin, J.; Bell, R., Groups and Representations (1995), Springer Verlag · Zbl 0839.20001
[3] Biham, E.; Shamir, A., Differential cryptanalysis of DES-like cryptosystems, (Advances in Cryptology-CRYPTO’90. Advances in Cryptology-CRYPTO’90, Proceedings, LNCS, vol. 537 (1991), Springer-Verlag: Springer-Verlag Berlin), 2-21 · Zbl 0787.94014
[4] Boura, C.; Canteaut, A.; De Canniére, C., Higher-order differential properties of Keccak and Luffa, (Joux, A., FSE. Lecture Notes in Computer Science, vol. 6733 (2011), Springer), 252-269 · Zbl 1307.94040
[5] Canteaut, A., Cryptographic functions and design criteria for block ciphers, (Progress in Cryptology-INDOCRYPT 2001. Progress in Cryptology-INDOCRYPT 2001, LNCS, vol. 2247 (2001), Springer-Verlag), 1-16 · Zbl 1011.94545
[6] Canteaut, A.; Videau, M., Symmetric Boolean functions, IEEE Trans. Inform. Theor., 51, 8, 2791-2811 (2005) · Zbl 1264.94094
[7] Daemen, J.; Knudsen, L.; Rijmen, V., The block cipher square, (Fast Software Encryption (1997), Springer), 149-165 · Zbl 1385.94025
[8] Dinur, I.; Shamir, A., Cube attacks on tweakable black box polynomials, (Joux, Antoie, EUROCRYPT. EUROCRYPT, LNCS, vol. 5479 (2009), Springer), 278-299 · Zbl 1239.94045
[9] Duan, M.; Lai, X., Higher order differential cryptanalysis framework and its applications, (International Conference on Information Science and Technology 2011 (2011), Springer), 291-297
[10] Duan, M.; Lai, X., Improved zero-sum distinguisher for full round Keccak-f permutation, Chinese Sci. Bull., 57, 6, 694-697 (2012), (Science China Press)
[11] Evertse, J. H., Linear structures in blockciphers, (Advances in Cryptology-EUROCRYPT 1987 (1988), Springer), 249-266. · Zbl 0659.94001
[12] Jakobsen, T.; Knudsen, L., The interpolation attack on block ciphers. The interpolation attack on block ciphers, Fast Software Encryption (1997), Springer Verlag · Zbl 1385.94047
[13] Jianyu, W., On the character of linear structure Boolean function, Acta Scientiarum Naturalium Universitatis Nankaiensis, 4 (2005)
[14] Katz, J.; Lindell, Y., Introduction to Modern Cryptography (2007), Chapman & Hall/CRC Press: Chapman & Hall/CRC Press Boca Raton
[15] Knudsen, L., Truncated and higher order differentials, (Fast Software Encryption (1995), Springer), 196-211 · Zbl 0939.94556
[16] Knudsen, L.; Wagner, D., Integral cryptanalysis, (Fast Software Encryption (2002), Springer), 629-632
[18] Luby, M.; Rackoff, C., How to construct pseudorandom permutations from pseudorandom functions, SIAM J. Comput., 17, 2, 373-386 (1988) · Zbl 0644.94018
[19] Lucks, S., The saturation attack-a bait for Twofish, (Fast Software Encryption (2001), Springer), 187-205
[20] Luo, Y.; Lai, X., On the security of multivariate hash functions, (Journal of Shanghai Jiaotong University (Science) (2009), Springer), 219-222 · Zbl 1214.68153
[21] Moriai, S.; Shimoyama, T.; Kaneko, T., Higher order differential attack of a CAST cipher, (Fast Software Encryption (1998), Springer), 17-31 · Zbl 1385.94063
[22] Nyberg, K.; Knudsen, L., Provable security against a differential attack, J. Cryptol., 8, 1, 27-37 (1995), (Springer Verlag) · Zbl 0817.94016
[23] Shimoyama, T.; Moriai, S.; Kaneko, T., Improving the higher order differential attack and cryptanalysis of the KN cipher, (Information Security, First International Workshop, ISW’97. Information Security, First International Workshop, ISW’97, LNCS, vol. 1396 (1998), Springer-Verlag), 32-42 · Zbl 0930.94024
[24] Tsunoo, Y.; Saito, T.; Shigeri, M.; Kawabata, T., Higher order differential attacks on reduced-round MISTY1, (Information Security and Cryptology-ICISC 2008 (2009), Springer), 415-431
[25] Watanabe, D.; Hatano, Y.; Yamada, T.; Kaneko, T., Higher order differential attack on step-reduced variants of Luffa v1, (Fast Software Encryption - FSE 2010. Fast Software Encryption - FSE 2010, Lecture Notes in Computer Science (2010), Springer), 270C285 · Zbl 1279.94125
[27] Zhu, B.; Chen, K.; Lai, X., Bitwise higher order differential cryptanalysis, (The First International Conference on Trusted Systems 2009, vol. 6163 (2009), Springer), 250-262
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.