曾祥勇

湖北大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)學(xué)院應(yīng)用數(shù)學(xué)湖北省重點(diǎn)實(shí)驗(yàn)室, 武漢430062

完全置換多項(xiàng)式專欄

置換多項(xiàng)式在分組密碼算法設(shè)計(jì)中具有廣泛的應(yīng)用.一般情況下, 分組密碼算法中明密文之間的關(guān)系就是密鑰控制下的置換.另外, 密碼算法的許多重要組成部分也是置換.例如, 具有良好密碼學(xué)性質(zhì)的置換常被用來設(shè)計(jì)對稱密碼算法中唯一的非線性部件S盒.

完全置換多項(xiàng)式是一類特殊的置換, 其概念是Mann 在上個(gè)世紀(jì)四十年代提出的, 早期的研究結(jié)果與正交拉丁方聯(lián)系緊密.完全置換多項(xiàng)式具有優(yōu)良的密碼學(xué)性質(zhì).例如, 偶特征有限域上的完全置換多項(xiàng)式只有一個(gè)不動(dòng)點(diǎn).此外, 非線性完全置換具有良好的位獨(dú)立性和雪崩特性, 使得基于完全置換的密碼算法具備良好的擴(kuò)散和混淆作用.因此, 完全置換多項(xiàng)式的研究具有重要的理論和實(shí)際意義.

完全置換多項(xiàng)式在密碼學(xué)中的較早應(yīng)用是由美國Teledyne 電子技術(shù)公司的Mittenthal 提出的.他分別在1995 年和1997 年發(fā)表的論文《Block substitutions using orthomorphic mapping》和專利《Nonlinear dynamic substitution devices and methods for block substitutions employing coset decompositions and direct geometric generation》中討論了完全置換的構(gòu)造和基本性質(zhì), 首次公開了如何使用完全置換多項(xiàng)式來設(shè)計(jì)密碼算法以及非線性動(dòng)力系統(tǒng)裝置.這些成果為完全置換在密碼學(xué)中的應(yīng)用奠定了基礎(chǔ), 并使人們對完全置換多項(xiàng)式這一數(shù)學(xué)對象產(chǎn)生濃厚的興趣.在隨后的十年里, 國內(nèi)外學(xué)者在這一研究方向上取得了一系列進(jìn)展.在密碼應(yīng)用方面比較有代表性成果的是 Vaudenay 在1999 年證明了添加完全置換或幾乎完全置換的Lai-Massey 結(jié)構(gòu)具有更好的偽隨機(jī)性.另外, 國內(nèi)的標(biāo)志性成果是 2006 年公布的基于完全置換的分組密碼算法SMS4, 該算法被指定用于無線局域網(wǎng)WAPI 且被我國商用密碼管理局確定為國家密碼行業(yè)標(biāo)準(zhǔn), 在密碼行業(yè)中有著極為重要的作用.

2007 年之后的幾年里, 完全置換多項(xiàng)式的研究進(jìn)展非常緩慢, 主要原因是判斷多項(xiàng)式的完全置換性質(zhì)是一個(gè)十分困難的問題, 即使最簡單的單項(xiàng)式的完全置換性質(zhì)也不容易被刻畫.直到 2014 年, Tu, Zeng和Hu 提出了用加法特征和極坐標(biāo)表示的方法來將完全置換單項(xiàng)式的問題轉(zhuǎn)化成有限域上特殊方程解的問題.受到其啟發(fā), 從2015 年開始國際學(xué)術(shù)界重新興起了研究有限域上完全置換多項(xiàng)式的熱潮.在最近五年, 涌現(xiàn)了一大批有代表性的成果, 例如基于例外多項(xiàng)式、AGW 準(zhǔn)則或密碼結(jié)構(gòu)的完全置換.

完全置換多項(xiàng)式在流密碼、Hash 函數(shù)、編碼設(shè)計(jì)、校驗(yàn)位系統(tǒng)設(shè)計(jì)等領(lǐng)域也有一定的應(yīng)用.雖然最近幾年完全置換多項(xiàng)式的研究已經(jīng)取得了一系列進(jìn)展, 但是已有的完全置換多項(xiàng)式類依然十分稀少, 完全置換多項(xiàng)式的研究尚處于初級(jí)階段, 還存在許多有待進(jìn)一步研究的重要問題, 其中完全置換多項(xiàng)式的構(gòu)造以及相關(guān)密碼學(xué)性質(zhì)分析是該方向的重點(diǎn)研究內(nèi)容.

在本期 “完全置換多項(xiàng)式” 專欄中共收錄三篇文章, 其中包含一篇綜述論文和兩篇研究論文, 希望對完全置換多項(xiàng)式的理論和應(yīng)用研究起到促進(jìn)作用.

第一篇是綜述論文《完全置換多項(xiàng)式的研究進(jìn)展》.該論文較全面地總結(jié)分析了近二十多年來有限域上完全置換多項(xiàng)式的相關(guān)理論研究成果, 從完全置換多項(xiàng)式的構(gòu)造方法和多項(xiàng)式的形式出發(fā)給出了已有完全置換的分類, 闡述了完全置換多項(xiàng)式的存在性、代數(shù)次數(shù)、圈結(jié)構(gòu)以及廣義完全置換多項(xiàng)式的相關(guān)研究進(jìn)展.此外, 還指出了一些值得進(jìn)一步研究的問題.該論文是一篇較好的介紹完全置換多項(xiàng)式的綜述, 對想了解完全置換多項(xiàng)式的研究者有很高的參考價(jià)值和很好的指導(dǎo)意義.

第二篇論文題目是《有限域上幾類置換和完全置換》.因?yàn)榕卸ㄒ粋€(gè)多項(xiàng)式構(gòu)成完全置換的條件是相當(dāng)復(fù)雜的, 所以研究特殊類型的完全置換多項(xiàng)式具有重大的意義.該論文運(yùn)用跡函數(shù)、線性置換和Dickson 置換構(gòu)造了有限域上六類形如的置換多項(xiàng)式, 證明了其中三類為完全置換并分析了其余三類不構(gòu)成完全置換的原因.另外, 在已知的置換判定法則基礎(chǔ)上他們還研究了形如xh(xs)的二項(xiàng)式的完全置換性質(zhì), 得到了有限域上幾類新的完全置換.

第三篇論文題目是《有限域上完全置換多項(xiàng)式的構(gòu)造》.稀疏型完全置換多項(xiàng)式因其具有簡潔的代數(shù)表達(dá)式以及便于硬件實(shí)現(xiàn)的特點(diǎn)而備受關(guān)注.該論文構(gòu)造了特征2 有限域Fq2上形如xh(xq?1)q+1的兩類完全置換多項(xiàng)式, 給出了這些多項(xiàng)式是完全置換多項(xiàng)式的充要條件或者充分條件.通過選取適當(dāng)?shù)暮瘮?shù),得到了幾類完全置換三項(xiàng)式和完全置換七項(xiàng)式.

兩篇研究論文均考慮完全置換多項(xiàng)式的構(gòu)造問題, 研究成果豐富了已有完全置換多項(xiàng)式的構(gòu)造, 具有重要的理論意義.

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.