密码学中置换多项式的构造问题研究

The determination and construction of permutation polynomials (PPs) over finite fields is one of hot issues in cryptography. In recent years, the Akbary-Ghioca-Wang (AGW) criterion and the piecewise method are two of the main methods for constructing PPs over finite fields. However, constructing commutative diagrams with specific properties is a difficult problem in applying the AGW criterion, and finding efficient approaches to computing inverses of PPs is also a difficult problem. Based on our prior research work that we have found some characteristics of these two problems, we will make more in-depth study on them for obtaining more general results. This project will focus on the following issues: (1) We will study general methods for the construction of commutative diagrams in the AGW criterion, and then we can use the AGW criterion to construct new classes of PPs. (2) The piecewise method is employed to find inverses of some PPs over finite fields. (3) Combining the piecewise method and the Lagrange Interpolation Formula, we will study the new method for constructing inverses of PPs over finite fields. The results of this research project will provide valuable theoretical support for the design and analysis of core components of cryptography.

有限域上置换多项式的判定与构造是密码学的研究热点之一。近年来Akbary-Ghioca-Wang（AGW）准则和分段方法是构造有限域上置换多项式的两个主流方法。然而，构造满足特定条件的交换图是应用 AGW 准则时的困难问题，寻找有效算法计算置换多项式的逆置换多项式也是一个难题。针对这两个问题，申请人在前期研究工作中取得了一些初步研究成果，围绕这两个问题本项目展开更加深入的研究，以期获得更具有一般性的结果，具体研究内容包括：（1）研究 AGW 准则中交换图的一般性构造方法，进而利用该准则构造有限域上新类型的置换多项式；（2）利用分段方法构造某些置换多项式的逆置换多项式；（3）结合分段方法和拉格朗日插值公式，研究构造逆置换多项式的新方法。本项目的研究成果将为密码核心部件的设计和分析提供有价值的理论支撑。

密码学中加密和解密互为逆运算，从而有限域上置换及其逆置换在密码学中有重要应用价值。然而，构造有限域上新类型的置换、寻找有效算法计算已知置换的逆置换是两个困难问题。本项目主要针对这两个难题进行了深入研究，取得了一些成果，具体包括：（1）利用AGW准则和代数曲线理论构造了有限域上新类型的置换多项式；（2）利用二项式系数的同余式和Lucas定理以及拉格朗日插值公式推导出有限域上次数不超过6的所有标准形式的置换多项式的逆置换多项式；（3）利用分段方法和求低次数置换多项式的逆置换的技术构造了一类反转Dickson 置换多项式和三类广义割圆映射置换多项式的逆置换多项式；（4）通过求解有限域上的方程推导出一类置换多项式的逆置换多项式；（5）提出两类零差分平衡函数的构造方法，针对轻量级分组密码算法GIFT提出两种有效的差分故障攻击方法。本项目研究成果丰富了有限域上置换多项式的基础理论，为密码核心部件的设计和分析提供新的理论支撑。