密码意义的置换多项式的存在性及构造问题研究

The main subject of this research project is to study the existence and construction of cryptographically significant permutation polynomials over finite fields of character 2. These permutations can be used for substitution boxes(S-boxes) in symmetric cryptography algorithms. S-boxes play an important role in symmetric cryptography since they serve as the confusion part and in most cases are the only nonlinear part of round functions. Thus their security is essential for the security of the whole cryptography algorithm. For efficiency of implementations and resistance of differential attack and linear attack, an S-box is often designed as a permutation over GF(2^{2k}) with low differential uniformity and high nonlinearity in practice. On the other hand, only few S-boxes with excellent cryptography properties are known. Thus the problem of constructing excellent S-boxes is a main problem in cryptography. The research project is based on the former work of the applicant and to further study the construction of S-boxes and corresponding theory. Moreover, the project is devoted to study the problems of the existence of APN permutations over GF(2^{2k}), the construction of differentially 4-uniform permutations with the best known nonlinearity over GF(2^{2k}) and the construction of S-boxes suitable for lightweight cryptography and so on. More constructions of S-boxes with excellent cryptography properties will be given during the period of project, and a big progress will be made for both the theory of the construction of S-boxes and its application in practice.

项目主要目的是研究特征为2的有限域上具有密码学意义的置换多项式的存在性及构造等问题。有限域上的置换多项式可用于密码算法中的S盒。S盒是对称密码算法的重要组件，其安全强度对整个密码算法的安全性有重要影响。在实际应用中，为了算法的快速实现以及更好得抵抗差分攻击和线性攻击，S盒多采用有限域GF(2^{2k})上具有低差分均匀度和高非线性度的置换。但已知的具有良好密码学性质的S盒和构造方法较少，因此如何设计安全的S盒是密码学中一个重要的问题。 本项目建立在申请人已有的研究基础上，进一步系统地研究具有优良密码学性质的S盒的构造方法及相关理论。特别是研究GF(2^{2k})上APN置换的存在性和具有最佳非线性度的4差分均匀置换的构造，以及适用于轻量级密码算法的S盒的构造等兼具理论和实际应用意义的问题。力争在项目周期内，发展出更多的S盒构造方法，在S盒的构造理论以及实际应用方面取得较大进展。

项目主要目的是研究特征为 2 的有限域上具有密码学意义的置换多项式的存在性及构造等问题。有限域上的置换多项式可用于密码算法中的 S 盒。S 盒是对称密码算法的重要组件，其安全强度对整个密码算法的安全性有重要影响。在实际应用中，为了算法的快速实现以及更好得抵抗差分攻击和线性攻击，S盒多采用有限域GF(2^{2k})上具有低差分均 匀度和高非线性度的置换。但已知的具有良好密码学性质的 S 盒和构造方法较少，因此如何设计安全的 S 盒是密码学中一个重要的问题。..在项目资助的基础上，系统地研究具有优良密码学性质的S盒 的构造方法及相关理论。首先，基于轻量密码的快速发展，研究了具有已知最优密码学性质并且硬件实现代价低的S盒的构造方法。给出了利用三轮Feistel结构所构造的S盒的下界，并且利用3轮Feistel结构给出了一类GF(2^{2k})上具有最佳非线性度的4差分均匀置换。给出了利用非线性反馈移位寄存器构造S盒的方法，并利用相关方法给出了最优4比特S盒的构造。其次，研究了轻量扩散层的构造方法。MDS扩散层是对称密码算法的另一个主要部件，为算法提供最佳的扩散性。我们首次给出了循环对合MDS矩阵的构造，并且其实现代价比之前的对合MDS矩阵都低。循环对合MDS矩阵具有实现简单，并且其电路可同时用于加密和解密电路，可以为算法节省解密电路的开销。但在我们的结果之前，循环对合MDS矩阵被证明在有限域上不存在。上述关于轻量部件的构造可直接用于轻量密码算法的设计。最后，研究了APN函数的构造。利用二次函数的矩阵表示，给出了APN函数的一个矩阵刻画，并利用相关方法在GF(2^8)上给出了8180个新的二次APN函数，原有23类。从而在APN函数的构造方面取得的较大突破。