田詩(shī)竹

（1. 中國(guó)科學(xué)院信息工程研究所信息安全國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京100093；2. 中國(guó)科學(xué)院大學(xué)，北京 100049）

田詩(shī)竹1,2

（1. 中國(guó)科學(xué)院信息工程研究所信息安全國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京100093；2. 中國(guó)科學(xué)院大學(xué)，北京 100049）

APN函數(shù)是特征為2的有限域上達(dá)到最低差分均勻度的函數(shù)，其中最經(jīng)典的是APN冪函數(shù)。在F22n上的APN冪函數(shù)都是3-1函數(shù)。推廣了前人在奇特征有限域上由2-1函數(shù)構(gòu)造置換的思想，得到偶特征域上由3-1函數(shù)構(gòu)造置換的方法，并由F22n上的APN冪函數(shù)構(gòu)造置換。根據(jù)這種構(gòu)造，研究了此類(lèi)置換的差分性質(zhì)。

有限域；置換多項(xiàng)式；APN；冪函數(shù)

1 引言

有限域上的置換多項(xiàng)式廣泛應(yīng)用于密碼學(xué)、編碼理論和組合設(shè)計(jì)。一些分組密碼的設(shè)計(jì)在多個(gè)環(huán)節(jié)需要利用有限域上的置換多項(xiàng)式（如AES的S盒是上的4差分置換多項(xiàng)式）。

設(shè)Fq是含q個(gè)元素的有限域，其中q是一個(gè)素?cái)?shù)的次冪。若映射是由Fq到本身的置換，則稱(chēng)為Fq上的置換多項(xiàng)式。顯然，f( x)為Fq上的置換多項(xiàng)式的充要條件是對(duì)于任意，方程 f( x)=a有唯一解[1]。近年來(lái)，置換多項(xiàng)式是國(guó)內(nèi)外許多專(zhuān)家學(xué)者的研究熱點(diǎn)。侯向東在文獻(xiàn)[2]中總結(jié)了近年來(lái)國(guó)內(nèi)外關(guān)于置換多項(xiàng)式的主要研究成果。

在分組密碼的S盒設(shè)計(jì)中一般要求其具有抵抗差分攻擊的能力，1993年，Nyberg在文獻(xiàn)[3]中提出了差分均勻度的概念。差分均勻度反映了函數(shù)抵抗差分攻擊的能力。

定義1Fq是含q個(gè)元素的有限域，f( x)是由Fq到自身的映射。則f( x)的差分均勻度為

1) Gold函數(shù)[5]： 2i1 d= + ，gcd(i, n)=1，

2) Kasami函數(shù)[6]：

5) Inverse函數(shù)： 2n2 d= - ，n為奇數(shù)。

6) Dobbertin 函數(shù)[7]：

文獻(xiàn)[15]提出了將2-1的PN函數(shù)變?yōu)?-1函數(shù)的思想，構(gòu)造了特征為奇數(shù)的有限域上的低差分置換多項(xiàng)式。借鑒了文獻(xiàn)[15]的構(gòu)造思想并將它推廣到了一般的情況，由特征為偶數(shù)的有限域上的3-1的APN函數(shù)構(gòu)造置換多項(xiàng)式。本文第2節(jié)給出由3-1函數(shù)構(gòu)造置換的方法和證明。第3節(jié)研究具體由Gold函數(shù)得到的置換的差分性質(zhì)，在較小域上，通過(guò)程序計(jì)算了由 Gold函數(shù)、Kasami函數(shù)以及Dobbertin函數(shù)構(gòu)造的置換的差分均勻度。對(duì)于n較大的域上，給出了由Gold函數(shù)構(gòu)造的置換的差分均勻度的上界。

2 構(gòu)造置換

在文獻(xiàn)[15]中，提出了由奇特征域上的 2-1函數(shù)構(gòu)造置換的方法，并發(fā)現(xiàn)由PN型的2-1函數(shù)構(gòu)造的這種置換，在某些情形下有較好的差分性質(zhì)。其主要思想是分段函數(shù)，將有限域劃分為平方元與非平方元并將重合分支分別對(duì)應(yīng)到但實(shí)際應(yīng)用一般都在特征為偶數(shù)的有限域上的置換，而在偶特征域下1=-1，直接使用其方法并不可行。本節(jié)給出了在偶特征域下由3-1構(gòu)造置換的方法。

命題1若 ()df x=x是F2n上的APN函數(shù)，則對(duì)于任意有xd=1當(dāng)且僅當(dāng)x3=1，即當(dāng)n為奇數(shù)時(shí)，gcd(,2nd -1)=1；當(dāng)n為偶數(shù)時(shí)，則APN冪函數(shù)在n為奇數(shù)時(shí)是置換，n為偶數(shù)時(shí)是 3-1函數(shù)。

根據(jù)命題1的結(jié)論，只需討論n為偶數(shù)的情況。 在接下來(lái)的討論中設(shè)n是任意正整數(shù)，考慮在有限域上置換多項(xiàng)式的構(gòu)造。

2.1 構(gòu)造思路

圖1 構(gòu)造思路圖

下面給出有限域的2種劃分，分別對(duì)應(yīng)圖1的左右2個(gè)域。

定義 2α是的本原元，w是三次本原單位根，定義

定義3α是的本原元，定義

顯然，

2.2 構(gòu)造及證明

設(shè) ()df x=x是上的 APN冪函數(shù)，α是的本原元，如上面的定義，構(gòu)造G( x)如下。

定理 1設(shè)是上的APN冪函數(shù)，α是的本原元，如上面的定義，式(1)給出了函數(shù)G( x)是上的置換。

證明首先，當(dāng)且僅當(dāng)x=0，只需考慮G( x)≠0的情況。假設(shè)存在使不妨設(shè)

注：通過(guò)上面的分析和證明可知這種構(gòu)造可以做簡(jiǎn)單的拓展，將它推廣為

3 差分性質(zhì)

本節(jié)主要考查由 APN冪函數(shù)構(gòu)造的置換的差分性質(zhì)。在較小的域上（2n≤12）通過(guò)程序計(jì)算了這些函數(shù)的差分均勻度，并由表格給出。對(duì)于比較大的域，由于計(jì)算機(jī)計(jì)算能力的限制，從數(shù)學(xué)的角度給出了由 Gold函數(shù)構(gòu)造的置換的差分均勻度的一個(gè)上界。

3.1 由Gold函數(shù)構(gòu)造的置換

在文獻(xiàn)[15]中，在奇特征域上通過(guò)對(duì)最優(yōu)差分性質(zhì)的2-1函數(shù)的改造，在某些條件下可以得到差分性質(zhì)次優(yōu)的置換。Gold函數(shù)在偶特征的有限域上是APN函數(shù)，當(dāng)n為奇數(shù)時(shí)，其非線性度也達(dá)到最優(yōu)。但當(dāng)n為偶數(shù)且gcd(i, n)=1時(shí)，它不是置換。類(lèi)似于文獻(xiàn)[15]，希望通過(guò)第 2節(jié)中的方法將其改造為置換，同時(shí)差分性質(zhì)并不改變很多。首先通過(guò)程序驗(yàn)證小域上的情形，發(fā)現(xiàn)對(duì)Gold型的這一改造對(duì)其差分性質(zhì)有一定的影響。表 1給出具體域中此類(lèi)函數(shù)差分均勻度的程序運(yùn)行結(jié)果。

表1 由Gold函數(shù)構(gòu)造的置換的差分均勻度

觀察表 1，改造后的函數(shù)在具體域上的差分性質(zhì)跟域的大小顯示出一定的關(guān)系。目前，實(shí)際應(yīng)用都在較小的域中使用。在上改造后的函數(shù)差分均勻度最優(yōu)可以達(dá)到8，對(duì)比實(shí)際AES的S盒是上差分均勻度為4的置換，此改造后得到的置換有一定抵抗差分攻擊的能力。但隨著n的增大，其差分均勻度有上升的趨勢(shì)，下面為了研究n足夠大時(shí)其差分?jǐn)U大的程度，在數(shù)學(xué)的角度給出了一個(gè)上界。

研究函數(shù)差分性質(zhì)時(shí)主要需要分析有限域上一些方程的解數(shù)，以下文獻(xiàn)[10]中的結(jié)論對(duì)后面的分析有重要作用。

命題2設(shè)F是有限域，對(duì)于記Ni為使方程有i個(gè)解的的個(gè)數(shù)。若是偶數(shù)，則

推論1則方程在上至多有3個(gè)解。實(shí)際上，它或者無(wú)解或者有一個(gè)解或者有3個(gè)解。

考慮方程

推論2方程在上至多有3個(gè)解。

下面給出 Gold函數(shù)構(gòu)造的置換的差分均勻度的一個(gè)上界。

命題3是的本原元，如上面的定義，式(1)給出了函數(shù)G( x)在上的差分均勻度

證明固定任意考慮方程在上的解。首先，考慮的情形，對(duì)x進(jìn)行劃分。

由命題3和以上的分析知，由Gold函數(shù)構(gòu)造的置換在較小域上的差分性質(zhì)較優(yōu)但達(dá)不到 4，隨n增大，在較大域上的差分最大不會(huì)超過(guò)26。

3.2 由Kasami和Dobbertin函數(shù)構(gòu)造的置換

由引言知，已知的APN冪函數(shù)滿(mǎn)足構(gòu)造要求的僅剩Kasami和Dobbertin（部分滿(mǎn)足條件的n）。同樣，本文通過(guò)程序驗(yàn)證其在較小域上的差分性質(zhì)。表2給出具體域上其差分均勻度的結(jié)果。

觀察表2，由Kasami和Dobbertin函數(shù)構(gòu)造的置換在較小域上有較優(yōu)的差分性質(zhì)。在小域上的結(jié)果顯示，改造后的函數(shù)差分達(dá)不到 4。對(duì)于較大的n，由于計(jì)算能力限制無(wú)法給出具體的差分，直接從數(shù)學(xué)的角度研究涉及更復(fù)雜的方程在有限域上的解數(shù)，有較大的難度。

表2 由Kasami和Dobbertin函數(shù)構(gòu)造的置換的差分均勻度

綜上分析，由第2節(jié)中的方法構(gòu)造的置換都在一定程度上改變了原函數(shù)的差分性質(zhì)。通過(guò)程序?qū)嶒?yàn)結(jié)果未能得到4差分的置換，筆者猜想一般的情況下這種構(gòu)造得到的置換都得不到4差分置換。但這類(lèi)置換仍保有較優(yōu)的差分，但從應(yīng)用的角度，在較小域上的差分均勻度的結(jié)果有一定的密碼學(xué)意義。

4 結(jié)束語(yǔ)

置換多項(xiàng)式在密碼學(xué)和編碼理論中有重要應(yīng)用，本文主要將奇特征域上2-1函數(shù)構(gòu)造置換的方法推廣到了偶特征域上。利用APN冪函數(shù)構(gòu)造了新的置換多項(xiàng)式，結(jié)合實(shí)驗(yàn)和理論分析了所得置換的差分性質(zhì)。不同于原奇特征域上的情形，猜想在偶數(shù)的情形下通過(guò)此類(lèi)方法得到的置換不具備次優(yōu)的差分性質(zhì)（4差分）。本文在應(yīng)用的范圍內(nèi)，給出了此構(gòu)造得到的置換的差分均勻度的具體值。這類(lèi)置換差分性質(zhì)更精細(xì)的刻畫(huà)有待進(jìn)一步研究。

[1] LIDL R, NIEDERREITER H. Finite fields[M]. Massachusetts:Addison-Wesley Publishing Company, 1983.

[2] HOU X D. Determination of a type of permutation trinomials over finite fields[J]. Finite Fields and Their Applications, 2015(35): 16-35.

[3] NYBERG K. Differentially uniform mappings for cryptography[C]//The Workshop on the Theory and Application of of Cryptographic Techniques. 1993:55-64.

[4] CARLET C. Vectorial boolean functions for cryptography[M].Cambridge: Cambridge University Press, 2010.

[5] GOLD R. Maximal recursive sequences with 3-value recursive crosscorrelation functions[J]. IEEE Trans Inform Theory, 1968(14):154-156.

[6] KASAMI T. The weight enumerators for several classes of subcodes of the second order binary Reed-Muller codes[J]. Information and Control, 1971(18): 369-394.

[7] DOBBERTIN H. Almost perfect nonlinear power functions on GF(2n): a new case for n divisible by 5[J]. Proceedings of Finite Fields and Applications Fq5. 2000:113-121.

[8] BROWNING K, DILLON J, MCQUISTAN M, et al. An APN permutation in dimension six[J]. Contemporary Mathematics.2010(58): 33-42.

[9] QU L J, TAN Y, TAN C, et al. Constructing differentially 4-uniform permutations overvia theswitching method[J]. IEEE Trans Inf Theory, 2013, 59(7): 4675-4686.

[10] LI Y Q, WANG M S. Constructing differentially 4-uniform permutations over GF(2n) from quadraticAPN permutations over GF(22n+1)[J]. Designs Codes amp; Cryptography, 2014, 61(6):249-264.

[11] TANG D, CARLET C, TANG X H. Differentially 4-uniform bijections by permuting the inverse function[J]. Designs Codes amp; Cryptography, 2015, 77(1): 117-141.

[12] PERRIN L, UDOVENKO A, BIRYUKOV A. Cryptanalysis of a theorem: Decomposing the only known solution to the big APN problem[C]//The 36th Annual International Cryptology Conference.2016:93-122.

[13] CANTEAUT A, DUVAL S, PERRIN L. A generalisation of Dillon’s APN permutation with the best known differential and nonlinear propertiesfor all fields of size 24k+2[J]. IEEE Transactions on Information Theory, 2016, (99):1-1.

[14] FU S H, FENG X T. Further results of the cryptographic properties onthe butterfly structure[J]. Computer Science—Information Theory, 2016(7)

[15] JIA W J, ZENG X Y, LI C L, et al. Permutation polynomials with low differential uniformity over finite fields of odd charateristic[J].Science China Mathematics, 2013(56): 1429-1440.

[16] BLUHER A B. On xq+1+ax+b[J]. Finite Fields and their Applications, 2004(10): 285-305.

Permutations from APN power functions over

TIAN Shi-zhu1,2

(1. The State Key Lab of Information Security, Institute of Information Engineering, Chinese Academy of Science, Beijing 100093, China;2. University of Chinese Academy of Sciences, Beijing 100049, China)

APN functions have the lowest differential uniform over finite fields with characteristic 2 and the APN power functions are the most classical ones. APN power functions are all 3-1 functions over F22n. By generalizing the idea of changing 2-1 functions to 1-1 functions over finite fields with odd characteristics, methods to change 3-1 functions over finite fields with even characteristics into permutations were obtained and permutations from APN power functions over F22n were constructed. According to the construction, the differential properties of permutations obtained by this method were discussed.

finite fields, permutation polynomials, APN, power functions

The National Natural Science Foundation of China (No.61379142)

TP393

A

10.11959/j.issn.2096-109x.2017.00203

2017-06-06；

2017-09-10。

田詩(shī)竹，tianshizhu@iie.ac.cn

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61379142）

田詩(shī)竹（1991-），女，湖北黃岡人，中國(guó)科學(xué)院信息工程研究所博士生，主要研究方向?yàn)樾畔踩?、密碼學(xué)。