2018-04-30 | 编辑：文/信息技术部 冯秀涛

差分分析[1]和线性分析[2]是两种通用的强有力的密码分析方法，它们几乎可以应用到所有对称密码算法的安全性分析上。差分均匀性和非线性度，作为衡量一个密码函数抗差分分析和线性分析能力强弱的密码学指标，被提出来并得到了广泛研究。为了抵抗差分分析和线性分析，在对称密码设计中往往希望构造一些具有好的密码学性质的置换函数，譬如，低的差分均匀性、高的非线性度和高的代数次数等。2016年，在美密会上Perrin等人[3]通过逆向工程分析Dillon等人[4]给出的有限域上的APN置换(即偶特征有限域上具有最优差分均匀性的密码函数)时引入了一个称之为Butterfly的构造有限域上密码函数的结构，这里k为奇数，如图1所示。他们发现Dillon等人构造的APN置换可以通过该结构简单给出，并且利用这类结构构造的密码函数都具有非常好的密码学性质，例如差分均匀度不超过4，代数次数为k或者k+1。此外，对一些小的k，通过进一步的计算机实验，他们发现这些函数的非线性度也是最优的。于是他们猜想这个结论可能对一般的奇数k也是成立的，并作为公开问题提出来。

图1 Butterfly结构

在这个工作中，信息技术部的冯秀涛等进一步研究了上述结构，并将参数e由Perrin等人确定的数值3扩展到一般的2t(2i+1)，这里t和i为整数，且gcd(i,k)=1[5]。他们证明了推广后的Butterfly结构构造的密码函数的差分均匀性同样不超过4，其代数次数依然为k或者k+1。并且在这个一般结构中他们完全证明了它们的非线性度总是最优的，从而彻底解决了Perrin等人在2016美密会上提出的公开问题。相关结果已发表在国际对称密码顶级会议FSE 2018。

参考文献

[1]BIHAM E, SHAMIR A. Differential Cryptanalysis of DES-like Cryptosystems[J]. Journal of Cryptology, 1991, 4(1):3–72. http://dx.doi.org/10.1007/BF00630563.

[2]MATSUI M. Linear Cryptanalysis Method for DES Cipher[C]//Advances in Cryptology - EUROCRYPT’93, Workshop on the Theory and Application of of Cryptographic Techniques, Lofthus, Norway, May 23-27, 1993, Proceedings. 1993:386–397, http://dx.doi.org/10.1007/ 3-540-48285-7 33.

[3]PERRIN L, UDOVENKO A, BIRYUKOV A. Cryptanalysis of a Theorem: Decomposing the Only Known Solution to the Big APN Problem[C]//Advances in Cryptology - CRYPTO 2016 - 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part II. 2016:93–122, http://dx.doi.org/10.1007/978-3-662-53008-54. 

[4]BROWNING K, DILLON J, MCQUISTAN M, et al. 2010. An APN permutation in demension six[C]//Postproceedings of the 9th Intenational Conference on Finite Fields and Their Applications Fq’9. AMS, Contemporary Mathematics, vol. 518. 

[5]Shihui Fu, Xiutao Feng and Baofeng Wu: Differentially 4-Uniform Permutations with the Best Known Nonlinearity from Butterflies, IACR Transactions on Symmetric Cryptology, Vol. 2017, No.2, pp. 228–249, DOI: 10.13154/tosc.v2017.i2.228-249.