Counting and characterising functions with “fast points” for differential attacks

详细信息    查看全文

• 作者：Ana Sălăgean ; Matei Mandache-Sălăgean
• 关键词：Higher order differential attacks ; Higher order derivative ; Cryptanalysis ; Polynomials over finite fields
• 刊名：Cryptography and Communications
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：9
• 期：2
• 页码：217-239
• 全文大小：509KB
• 刊物类别：Computer Science
• 刊物主题：Data Structures, Cryptology and Information Theory; Coding and Information Theory; Communications Engineering, Networks; Information and Communication, Circuits; Mathematics of Computing;
• 出版者：Springer US
• ISSN：1936-2455
• 卷排序：9

文摘

Higher order derivatives have been introduced by Lai in a cryptographic context. A number of attacks such as differential cryptanalysis, the cube and the AIDA attack have been reformulated using higher order derivatives. Duan and Lai have introduced the notion of “fast points” of a polynomial function f as being vectors a so that computing the derivative with respect to a decreases the total degree of f by more than one. This notion is motivated by the fact that most of the attacks become more efficient if they use fast points. Duan and Lai gave a characterisation of fast points and Duan et al. gave some results regarding the number of functions with fast points in some particular cases. We firstly give an alternative characterisation of fast points and secondly give an explicit formula for the number of functions with fast points for any given degree and number of variables, thus covering all the cases left open in Duan et al. Our main tool is an invertible linear change of coordinates which transforms the higher order derivative with respect to an arbitrary set of linearly independent vectors into the higher order derivative with respect to a set of vectors in the canonical basis. Finally we discuss the cryptographic significance of our results.