完全置换多项式专栏序言 (中英文)

曾祥勇

湖北大学数学与统计学学院应用数学湖北省重点实验室, 武汉430062

完全置换多项式专栏

置换多项式在分组密码算法设计中具有广泛的应用.一般情况下, 分组密码算法中明密文之间的关系就是密钥控制下的置换.另外, 密码算法的许多重要组成部分也是置换.例如, 具有良好密码学性质的置换常被用来设计对称密码算法中唯一的非线性部件S盒.

完全置换多项式是一类特殊的置换, 其概念是Mann 在上个世纪四十年代提出的, 早期的研究结果与正交拉丁方联系紧密.完全置换多项式具有优良的密码学性质.例如, 偶特征有限域上的完全置换多项式只有一个不动点.此外, 非线性完全置换具有良好的位独立性和雪崩特性, 使得基于完全置换的密码算法具备良好的扩散和混淆作用.因此, 完全置换多项式的研究具有重要的理论和实际意义.

完全置换多项式在密码学中的较早应用是由美国Teledyne 电子技术公司的Mittenthal 提出的.他分别在1995 年和1997 年发表的论文《Block substitutions using orthomorphic mapping》和专利《Nonlinear dynamic substitution devices and methods for block substitutions employing coset decompositions and direct geometric generation》中讨论了完全置换的构造和基本性质, 首次公开了如何使用完全置换多项式来设计密码算法以及非线性动力系统装置.这些成果为完全置换在密码学中的应用奠定了基础, 并使人们对完全置换多项式这一数学对象产生浓厚的兴趣.在随后的十年里, 国内外学者在这一研究方向上取得了一系列进展.在密码应用方面比较有代表性成果的是 Vaudenay 在1999 年证明了添加完全置换或几乎完全置换的Lai-Massey 结构具有更好的伪随机性.另外, 国内的标志性成果是 2006 年公布的基于完全置换的分组密码算法SMS4, 该算法被指定用于无线局域网WAPI 且被我国商用密码管理局确定为国家密码行业标准, 在密码行业中有着极为重要的作用.

2007 年之后的几年里, 完全置换多项式的研究进展非常缓慢, 主要原因是判断多项式的完全置换性质是一个十分困难的问题, 即使最简单的单项式的完全置换性质也不容易被刻画.直到 2014 年, Tu, Zeng和Hu 提出了用加法特征和极坐标表示的方法来将完全置换单项式的问题转化成有限域上特殊方程解的问题.受到其启发, 从2015 年开始国际学术界重新兴起了研究有限域上完全置换多项式的热潮.在最近五年, 涌现了一大批有代表性的成果, 例如基于例外多项式、AGW 准则或密码结构的完全置换.

完全置换多项式在流密码、Hash 函数、编码设计、校验位系统设计等领域也有一定的应用.虽然最近几年完全置换多项式的研究已经取得了一系列进展, 但是已有的完全置换多项式类依然十分稀少, 完全置换多项式的研究尚处于初级阶段, 还存在许多有待进一步研究的重要问题, 其中完全置换多项式的构造以及相关密码学性质分析是该方向的重点研究内容.

在本期 “完全置换多项式” 专栏中共收录三篇文章, 其中包含一篇综述论文和两篇研究论文, 希望对完全置换多项式的理论和应用研究起到促进作用.

第一篇是综述论文《完全置换多项式的研究进展》.该论文较全面地总结分析了近二十多年来有限域上完全置换多项式的相关理论研究成果, 从完全置换多项式的构造方法和多项式的形式出发给出了已有完全置换的分类, 阐述了完全置换多项式的存在性、代数次数、圈结构以及广义完全置换多项式的相关研究进展.此外, 还指出了一些值得进一步研究的问题.该论文是一篇较好的介绍完全置换多项式的综述, 对想了解完全置换多项式的研究者有很高的参考价值和很好的指导意义.

第二篇论文题目是《有限域上几类置换和完全置换》.因为判定一个多项式构成完全置换的条件是相当复杂的, 所以研究特殊类型的完全置换多项式具有重大的意义.该论文运用迹函数、线性置换和Dickson 置换构造了有限域上六类形如的置换多项式, 证明了其中三类为完全置换并分析了其余三类不构成完全置换的原因.另外, 在已知的置换判定法则基础上他们还研究了形如xh(xs)的二项式的完全置换性质, 得到了有限域上几类新的完全置换.

第三篇论文题目是《有限域上完全置换多项式的构造》.稀疏型完全置换多项式因其具有简洁的代数表达式以及便于硬件实现的特点而备受关注.该论文构造了特征2 有限域Fq2上形如xh(xq−1)q+1的两类完全置换多项式, 给出了这些多项式是完全置换多项式的充要条件或者充分条件.通过选取适当的函数,得到了几类完全置换三项式和完全置换七项式.

两篇研究论文均考虑完全置换多项式的构造问题, 研究成果丰富了已有完全置换多项式的构造, 具有重要的理论意义.

Permutation polynomials are widely used in the design of block cipher algorithms.In general, the relationship between plaintext and ciphertext in block cipher algorithms is a permutation under the control of keys.In addition, many important components of cryptographic algorithms are permutations.For example, permutations with good cryptographic properties are often used to designS-box which is the unique nonlinear component of symmetric cryptographic algorithms.

Complete permutation polynomials are a special class of permutation polynomials.The concept of complete permutation polynomials was proposed by Mann in the 1940s.Earlier research results are closely related to orthogonal Latin squares.Complete permutation polynomials have good cryptographic properties.For example, complete permutation polynomials over finite fields of even characteristic have a single fixed point.Moreover, nonlinear complete permutations have bit independence and avalanche characteristics, so the cryptographic algorithms based on complete permutations have good diffusion and confusion effects.Therefore, the research of complete permutation polynomials has important theoretical and practical significance.

The early application of complete permutation polynomials in cryptography was proposed by Mittenthal who comes from Teledyne Electronics Technology Company of the United States.He published the paper “Block substitutions using orthomorphic mapping” in 1995 and the patent “Nonlinear dynamic substitution devices and methods for block substitutions employing coset decompositions and direct geometric generation”in 1997, respectively.In this paper and this patent, the constructions and properties of complete permutations were discussed.In addition, he firstly presented how to use complete permutation polynomials to design cryptographic algorithms and nonlinear dynamic substitution devices.These achievements laid the foundation for the application of complete permutations in cryptography and aroused great interest in the mathematical object complete permutation polynomials.In the following ten years, scholars worldwide have made a series of achievements in this field.The representative achievement in cryptographic application is that Vaudenay proved that the Lai-Massey scheme with complete permutations or almost complete permutations has better pseudo-randomness in 1999.In addition, the landmark achievement in China is that the block cipher algorithm SMS4 was designed by use of complete permutations and published in 2006.This algorithm has been designated for WAPI in WLAN and has been designated as the national cryptographic industry standard by China’s Commercial Cryptographic Administration.It plays an extremely important role in the cryptographic industry.

In the years after 2007, the research on complete permutation polynomials has developed very slowly, since the problem of judging a polynomial to be a complete permutation is very difficult,even for the simplest monomials.In 2014, Tu, Zeng, and Hu proposed the method of using the additive characters of the underlying finite fields and the technique of polar coordinate representation to transform the problem of complete permutation monomials over finite fields into that of determining the number of the solutions to certain equations over finite fields.Inspired by their works,a new upsurge of studying complete permutation polynomials over finite fields has arisen in the international academic circles in 2015.In the past five years, a large number of representative achievements have emerged,such as complete permutations based on exceptional polynomials, the AGW criteria or cryptographic structures.

Complete permutation polynomials also have some applications in stream ciphers,Hash functions,coding design, check digit systems, and other fields.In recent years, a series of achievements have been obtained in the study of complete permutation polynomials, but the known classes of complete permutation polynomials are very rare.The research of complete permutation polynomials is still in primary stage, and there exist many important problems which need to be studied in the future.The construction of complete permutation polynomials and the analysis of cryptographic properties for these polynomials are the key research problems in this field.

The special column “Complete permutation polynomials” has collected three papers involving one review article and two research articles, hoping to promote the development of this field.

The first paper is review article “Overview on complete permutation polynomials”.This paper comprehensively summarizes and analyzes the related theoretical research results of complete permutation polynomials over finite fields in the past twenty years, and gives the classification of known complete permutation polynomials from the construction methods and the form of polynomials.The existence, algebraic degree, cycle structure of complete permutation polynomials and generalized complete permutation polynomials are also discussed.In addition, some problems worthy to study in the future are pointed out.This paper is a good summary of complete permutation polynomials.It is of a high reference value and a good guiding significance for researchers who intend to learn about complete permutation polynomials.

The second paper is “A few classes of permutations and complete permutations over finite fields”.To characterize the conditions of a polynomial to be a complete permutation is very difficult, so it is of great significance to study complete permutation polynomials with special forms.This paper constructs six classes of permutations with the formby using some trace functions,linear permutations,and Dickson permutations.Three of them are proved to be complete computations and they give the reasons why the other three types are not complete permutation polynomials.In addition, based on the known criteria of permutations, they study the permutation properties of binomials with the formxh(xs) and obtain a few new classes of complete permutation binomials over finite fields.

The third paper is “Construction of complete permutation polynomials over finite fields”.Sparse complete permutation polynomials have attracted much attention due to their concise algebraic expressions and features for easy implementation on hardware.This paper constructs two classes of complete permutation polynomials of the formxh(xq−1)q+1over Fq2with characteristic 2 and characterizes the necessary and sufficient conditions or sufficient conditions for these polynomials to be complete permutation polynomials.By choosing appropriate functions, several types of complete permutation trinomials and complete permutation with seven terms are obtained.

The construction of complete permutation polynomials is considered in both research articles.The research results enrich the existing constructions of complete permutation polynomials and have important theoretical significance.