完全置換多項式專欄序言 (中英文)

曾祥勇

湖北大學數學與統計學學院應用數學湖北省重點實驗室, 武漢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.