有限域上低差分函數(shù)研究進(jìn)展

屈龍江 陳 璽 牛泰霖 李 超

(國(guó)防科技大學(xué)文理學(xué)院 長(zhǎng)沙 410073) (ljqu_happy@hotmail.com)

密碼學(xué)是網(wǎng)絡(luò)空間安全和信息安全的核心，作為一門(mén)綜合性學(xué)科，其發(fā)展與國(guó)家安全息息相關(guān)，也與政治、軍事、外交等國(guó)家事務(wù)密不可分.對(duì)稱(chēng)密碼學(xué)是密碼學(xué)的重要分支，主要研究對(duì)象包括分組密碼、流密碼、Hash函數(shù)等.對(duì)稱(chēng)密碼算法是各國(guó)政府、軍事和銀行等重要部門(mén)保護(hù)核心敏感信息的主要算法.密碼函數(shù)包含布爾函數(shù)與向量函數(shù)(S -盒)兩大類(lèi)，是構(gòu)成序列密碼、分組密碼和Hash函數(shù)等對(duì)稱(chēng)密碼算法的核心組件，而且往往是唯一的非線性組件，其密碼學(xué)性質(zhì)的好壞對(duì)基于該組件設(shè)計(jì)的密碼算法的安全性有著至關(guān)重要的影響[1-9],相應(yīng)的密碼算法對(duì)于各種已知攻擊的抵抗性可以由它所使用密碼函數(shù)的相應(yīng)密碼學(xué)指標(biāo)來(lái)衡量.

差分攻擊是攻擊迭代分組密碼最有效的方法之一.差分攻擊的基本思想是通過(guò)分析明文對(duì)差值對(duì)密文對(duì)差值的影響來(lái)恢復(fù)某些密鑰比特.一個(gè)密碼算法抵抗差分攻擊的能力與其采用的密碼函數(shù)抵抗差分攻擊的能力密切相關(guān)，而后者可以用差分均勻度來(lái)衡量.一個(gè)密碼函數(shù)的差分均勻度越小，其抵抗差分攻擊的能力就越強(qiáng).有限域Fq上的低差分函數(shù)主要包括完全非線性函數(shù)(perfect nonlinear func-tion, PN函數(shù))、幾乎完全非線性函數(shù)(almost perfect nonlinear function, APN函數(shù))和差分均勻度為4的函數(shù)(4-uniform function, 4差分函數(shù))等.當(dāng)有限域的特征為奇數(shù)時(shí)，PN函數(shù)、APN函數(shù)分別達(dá)到最優(yōu)、次優(yōu)的差分均勻度；而在偶特征的有限域上，差分均勻度必然為偶數(shù)，此時(shí)APN函數(shù)、4差分函數(shù)分別達(dá)到最優(yōu)、次優(yōu)的差分均勻度.由于絕大多數(shù)密碼算法用的密碼函數(shù)是定義在偶特征有限域上的，所以在密碼研究中，APN函數(shù)、4差分函數(shù)受到了更多關(guān)注.但是需要注意的是，PN函數(shù)、APN函數(shù)和4差分函數(shù)等低差分函數(shù)之間有著十分緊密的聯(lián)系，很多構(gòu)造是相互啟發(fā)的.

為了抵抗差分攻擊、線性攻擊和插值攻擊等分析方法，一個(gè)理想的S -盒通常應(yīng)同時(shí)具有低差分均勻度，高非線性度和高代數(shù)次數(shù)等多種良好密碼學(xué)性質(zhì).由于在代替置換網(wǎng)絡(luò)(substitution-permutation-network, SPN)結(jié)構(gòu)分組密碼S -盒的設(shè)計(jì)中，為了避免熵泄露，一般要求分組密碼中使用的向量函數(shù)是置換；而為了軟硬件實(shí)現(xiàn)時(shí)具有較高的效率，又希望其定義在二元域的偶數(shù)維擴(kuò)域上，因此相比一般的4差分函數(shù)，偶擴(kuò)張上的4差分置換的構(gòu)造與分析近年來(lái)受到了更多研究和關(guān)注.另外，由于具有對(duì)合性質(zhì)的函數(shù)可以提高硬件實(shí)現(xiàn)的效率,這一性質(zhì)在研究中也受到了較多關(guān)注.因此，本文主要總結(jié)了PN函數(shù)、APN函數(shù)和偶擴(kuò)張上的4差分置換方面的研究進(jìn)展.最后，需要說(shuō)明的是，低差分函數(shù)在編碼和通信領(lǐng)域中也有廣泛應(yīng)用，比如滿足特定性質(zhì)的密碼函數(shù)可以用來(lái)構(gòu)造性能優(yōu)良的糾錯(cuò)碼和跳頻碼[10]，并且所構(gòu)造的碼參數(shù)與原有密碼函數(shù)的非線性度等安全性指標(biāo)密切相關(guān).

1 基本概念和知識(shí)

1.1 基本概念

設(shè)Fq為q=pn元有限域，其中素?cái)?shù)p為其特征,則Fq可以看作Fp上的n維向量空間.事實(shí)上，設(shè)f(x)∈Fp[x]是一個(gè)n次不可約多項(xiàng)式，α為其在分裂域中的一個(gè)根，則:

Fpn={a0+a1α+…+an-1αn-1|a0,a1,…,an-1∈Fp},

如果F為有限域Fpn到其自身的映射，則它可以表示為Fpn上的單變?cè)囗?xiàng)式：

定義1.代數(shù)次數(shù).設(shè)F為有限域Fpn到其自身的映射，其單變?cè)硎緸?/p>

那么F的代數(shù)次數(shù)定義為

degF=max{wp(j)|j=0,1,…,pn-1,δj≠0}.

需要指出的是，這個(gè)概念和常見(jiàn)的“多項(xiàng)式次數(shù)”的概念有所不同，比如F2n上的單項(xiàng)式F(x)=x3的多項(xiàng)式次數(shù)為3，但它的代數(shù)次數(shù)為2(因?yàn)?=2+1=(11)2).如果一個(gè)函數(shù)的代數(shù)次數(shù)不超過(guò)1，則稱(chēng)其為仿射函數(shù).不含常數(shù)項(xiàng)的仿射函數(shù)，稱(chēng)為線性函數(shù)或者線性化多項(xiàng)式.

設(shè)F為有限域Fpn到其自身的映射.若Fpn中的每一個(gè)元素在其像集中都恰好出現(xiàn)一次，則稱(chēng)F為Fpn上的置換.若函數(shù)G滿足G(F(x))=x，則稱(chēng)G為置換F的逆.若置換F的逆恰為其自身，即有F(F(x))=x，則稱(chēng)F是對(duì)合函數(shù).

δF(a,b)=#{x∈Fq|F(x+a)-F(x)=b}.

(1)

稱(chēng)F的差分均勻度為ΔF或稱(chēng)F為ΔF-差分(一致性)函數(shù).

一個(gè)密碼函數(shù)的差分均勻度越小，其抵抗差分攻擊的能力就越強(qiáng).特別地，若ΔF=1，則稱(chēng)其為完全非線性函數(shù)(PN函數(shù))；若ΔF=2，則稱(chēng)其為幾乎完全非線性函數(shù)(APN函數(shù)).當(dāng)有限域的特征為偶數(shù)時(shí)，注意到若x0是式(1)的解，則x0+a必然也是式(1)的解，這表明式(1)的解必然成對(duì)出現(xiàn)，因此差分均勻度必然為偶數(shù).這表明在偶特征的有限域上，APN函數(shù)、4差分函數(shù)分別達(dá)到最優(yōu)、次優(yōu)的差分均勻度.事實(shí)上，若q為偶數(shù)，則Fq上的一個(gè)函數(shù)的差分均勻度可以取從2到q的所有可能的偶數(shù)；若q為奇數(shù)，則Fq上的一個(gè)函數(shù)的差分均勻度可以取除q-1外，從1到q的其他任一整數(shù)[11].另外，需要說(shuō)明的是，差分均勻度和完全非線性函數(shù)均可以推廣定義到一般的交換群上，相關(guān)工作這里不再贅述，感興趣的讀者可以參閱文獻(xiàn)[12].

F的非線性度定義為

當(dāng)n為奇數(shù)時(shí)，非線性度NL(F)的上界為2n-1-2(n-1)2，達(dá)到該最大值的函數(shù)稱(chēng)為幾乎Bent函數(shù)(almost Bent function, AB函數(shù))；當(dāng)n為偶數(shù)時(shí)，人們猜想非線性度NL(F)的上界為2n-1-2n2.若能達(dá)到該值，則稱(chēng)之為達(dá)到已知最優(yōu)非線性度的函數(shù).

1.2 CCZ等價(jià)與EA等價(jià)

新的低差分函數(shù)的構(gòu)造是密碼函數(shù)研究中的重要問(wèn)題，它涉及到這些函數(shù)之間的等價(jià)性問(wèn)題.最主要的等價(jià)性有2個(gè)：CCZ等價(jià)和EA等價(jià).

定義4.擴(kuò)展仿射等價(jià).設(shè)F,G為2個(gè)Fq到自身的函數(shù)，若存在仿射置換函數(shù)l1,l2和仿射函數(shù)l3,使得F=l1°G°l2+l3，則稱(chēng)F和G擴(kuò)展仿射等價(jià)(extended affine equivalent, EA等價(jià)).特別地，若l3=0，則稱(chēng)F和G仿射等價(jià).

定義5.CCZ等價(jià).Fq上函數(shù)F的圖定義為{(x,F(x)):x∈Fq}，若2個(gè)函數(shù)的圖仿射等價(jià)，則稱(chēng)這2個(gè)函數(shù)CCZ等價(jià)(Carlet-Charpin-Zinoviev equivalent, CCZ等價(jià)).

容易驗(yàn)證EA等價(jià)意味著CCZ等價(jià)；但是反之不然.CCZ等價(jià)保持函數(shù)的差分均勻度和非線性度(更準(zhǔn)確地說(shuō)，是保持函數(shù)的擴(kuò)展Walsh譜)，而EA等價(jià)還保持代數(shù)次數(shù)(如果函數(shù)的代數(shù)次數(shù)≥2).一般而言，在理論上證明2個(gè)無(wú)限函數(shù)類(lèi)是否CCZ等價(jià)是一個(gè)非常困難的問(wèn)題，而判斷EA等價(jià)則要簡(jiǎn)單許多.

由于在理論上分析不同函數(shù)之間的CCZ等價(jià)性非常困難，實(shí)踐上人們一般通過(guò)計(jì)算機(jī)計(jì)算一些CCZ等價(jià)不變量，比如差分均勻度、擴(kuò)展Walsh譜、Γ-秩、Δ-秩和各種形式的自同構(gòu)群等.如果2個(gè)函數(shù)有不同的CCZ等價(jià)不變量，則它們一定不等價(jià)；反之則不能判斷.另外，一個(gè)無(wú)限函數(shù)類(lèi)的差分均勻度、擴(kuò)展Walsh譜等CCZ等價(jià)不變量的有效計(jì)算研究在理論上和應(yīng)用上都是很有意義的，特別是擴(kuò)展Walsh譜的計(jì)算.這不僅是因?yàn)橛蓴U(kuò)展Walsh譜可以決定出非線性度，還因?yàn)椋河葾PN函數(shù)可以構(gòu)造性能優(yōu)良的線性碼，并且APN函數(shù)的擴(kuò)展Walsh譜對(duì)應(yīng)于該線性碼的重量分布，而線性碼的重量分布是線性碼的一個(gè)重要參數(shù)，利用其可以有效計(jì)算譯碼算法的錯(cuò)誤概率.

2 PN函數(shù)

2.1 性質(zhì)與判定

PN函數(shù)有一些等價(jià)判別準(zhǔn)則.

定理1.設(shè)F:Fpn→Fpn，則3個(gè)條件等價(jià)：

1)F為PN函數(shù)，即對(duì)任意a,b∈Fpn,a≠0,方程F(x+a)-F(x)=b至多有1個(gè)解；

2) 對(duì)任意的0≠a∈Fpn，函數(shù)DaF為Fpn上的置換多項(xiàng)式，其中DaF=F(x+a)-F(x)；

3)D={(x,F(x))|x∈Fpn}為Fpn×Fpn中的(pn,pn,pn,1)-相對(duì)差集.

除此之外，有限域上的PN函數(shù)還可以用來(lái)構(gòu)造達(dá)到Welch界的最優(yōu)碼本(codebook)，量子測(cè)量、量子計(jì)算中有重要作用的最優(yōu)互無(wú)偏基(mutually unbiased base，MUB)以及壓縮感知中的最優(yōu)相干矩陣(coherence matrix)等.由于本文主要是從密碼學(xué)的角度論述，這些聯(lián)系就不再贅述了，感興趣的讀者可以參閱文獻(xiàn)[13-15].

特別地，對(duì)于二次PN函數(shù)，也稱(chēng)為Demobowski-Ostrom(DO)型函數(shù)，有等價(jià)判定準(zhǔn)則：

定理2.設(shè)F:Fpn→Fpn且為二次函數(shù)，則2個(gè)條件等價(jià)：

1)F為PN函數(shù)，即對(duì)任意0≠a∈Fpn，函數(shù)DaF=F(x+a)-F(x)為Fpn上的線性化置換多項(xiàng)式；

2) (Fpn,+,*)為有限交換預(yù)半域，其中“*”為Fpn上定義的乘法：

x*y=(F(x+y)-F(x)-F(y))2.

預(yù)半域與域相比，可能失去結(jié)合律且可能不含單位元.

2008年Kyureghyan和Pott證明了2個(gè)PN函數(shù)CCZ等價(jià)當(dāng)且僅當(dāng)它們EA等價(jià)[16].因此相比于一般函數(shù)的CCZ等價(jià)性判斷，PN函數(shù)CCZ等價(jià)性判斷的難度略小一些，但仍很困難.

2012年翁國(guó)標(biāo)和曾祥勇刻畫(huà)了DO型PN函數(shù)的映射性質(zhì)[17].

定理3[17].設(shè)F為Fpn[x]中的DO型多項(xiàng)式,則F為PN函數(shù)當(dāng)且僅當(dāng)其像集中的每一個(gè)非零元均有2個(gè)原像，即F是2到1的映射.

2.2 已有構(gòu)造

2005年以前，有限域Fpn上PN函數(shù)的研究主要集中于冪函數(shù)(單項(xiàng)式)，包括2類(lèi)(不等價(jià)的)PN冪函數(shù)：

1) Demobowski-Ostrom冪函數(shù)[18]：

π1(x)=xpt+1,

其中,整數(shù)t≥0，ngcd(n,t)為奇數(shù)；

2) Coulter-Mattews冪函數(shù)[19]：

其中,整數(shù)p=3，k為奇數(shù)且n和k的最大公約數(shù)gcd(n,k)=1；

2006年以后，人們陸續(xù)發(fā)現(xiàn)了一些多項(xiàng)式形式的二次PN函數(shù).目前Fpn上已知的多項(xiàng)式PN函數(shù)有：

1) Ding-Yuan多項(xiàng)式[19-20]：

π3(x)=x10-μx6-μ2x2,

2) Zha-Kyureghyan-Wang多項(xiàng)式[21]：

π4(x)=xps+1-μpkxplk+p-lk+s,

其中,整數(shù)n=3k,(3,k)=1,kgcd(k,s)為奇數(shù)，s≡±kmod 3且μ為中本原元；

3) Budaghyan-Helleseth第1類(lèi)多項(xiàng)式[22]：

4) Budaghyan-Helleseth第2類(lèi)多項(xiàng)式[22]：

π6(x)=bxps+1+(bxps+1)pk+cxpk+1+

5) Bierbrauer多項(xiàng)式[23]：

π7(x)=xpt+1-αxp2s+ps+t,

其中,n=3s，q=ps，q′=pt，s′=sgcd(s,t)，t′=tgcd(s,t)，s′為奇數(shù)，a∈Fq3且其階為q2+q+1，s+s′≡0 mod 3或q≡q′ mod 3.

如定理2所述，上述二次PN函數(shù)還等價(jià)于交換預(yù)半域.人們還構(gòu)造了一些其他的半域，其對(duì)應(yīng)的多項(xiàng)式較復(fù)雜，下面列出這些半域，感興趣的讀者可以自行推導(dǎo)其對(duì)應(yīng)PN函數(shù)的多項(xiàng)式表達(dá)式：

1) Dickson半域[24]：定義在Fq2k上，其乘法定義為

(a,b)*(c,d)=(ac+αbqdq,ad+bc),

其中,α∈Fqk為一個(gè)非平方元；

2) Ganley半域[25]：定義在F32k上，其中k≥3為奇數(shù)，其乘法定義為

(a,b)*(c,d)=(ac-b9d-bd9,ad+bc+b3d3)

3) Cohen-Ganley半域[26]：定義在F3n上，其中n≥2，其乘法定義為

(a,b)*(c,d)=(ac+βbd+β3(bd)9,

ad+bc+β(bd)3),

其中,β∈F3n為一個(gè)非平方元；

4) Zhou-Pott半域[27]：設(shè)n=2m,k為正整數(shù)，且mgcd(m,k)為奇數(shù)，定義x°ky=xpky+ypkx,設(shè)(a,b)*(c,d)∈Fp2m,乘法定義為

(a,b)*(c,d)=(a°kc+α(b°kd)δ,ad+bc)

其中,α∈Fpm為一個(gè)非平方元；δ為Fpm上的一個(gè)自同構(gòu).

除此之外，人們還在F35,F38,F55中發(fā)現(xiàn)了一些零散半域[28-30].目前還不能把它們推廣到無(wú)限類(lèi).

從上面論述可以看出，除了Coulter-Mattews函數(shù)外，其他所有已知PN函數(shù)都是二次的，因此都對(duì)應(yīng)于交換(預(yù))半域.二次PN函數(shù)的CCZ等價(jià)性與其對(duì)應(yīng)半域的同痕(isotopy)是一致的.半域同痕的不變量包括核(nucleus)、中心(center)、對(duì)應(yīng)平面的自同構(gòu)群等.關(guān)于上述半域同痕性的討論，請(qǐng)參閱文獻(xiàn)[31]及其引用的參考文獻(xiàn).

定義6.非凡完全非線性函數(shù)(exceptional perfect nonlinear function).設(shè)F:Fq→Fq, 若F在Fq的無(wú)窮多個(gè)擴(kuò)域上為完全非線性函數(shù)，則稱(chēng)F為非凡完全非線性函數(shù).若F(x)=xd，則稱(chēng)d為非凡完全非線性指數(shù).

利用代數(shù)幾何的方法，2015年Zieve[32]證明了：

定理4.設(shè)p為奇素?cái)?shù)，d為正整數(shù)，單項(xiàng)式F(x)=xd為Fpn上的完全非線性函數(shù)對(duì)無(wú)窮多個(gè)整數(shù)n成立當(dāng)且僅當(dāng)d為下列情形之一：

1)d=pi+pj,i≥j≥0；

2)d=(3i+3j)2,p=3,i≥j≥0且i-j為奇數(shù).

除了上述2個(gè)非凡完全非線性函數(shù)外，容易看出Ding-Yuan多項(xiàng)式π3(x)=x10-μx6-μ2x2也是一個(gè)非凡完全非線性函數(shù).

本節(jié)的最后，介紹一下偶特征上的平面函數(shù)，也稱(chēng)為偽平面函數(shù)(pseudo-planar function)或修改的平面函數(shù)(modified planar function).PN函數(shù)僅在奇特征有限域上存在，APN函數(shù)在某種意義上可以視為PN函數(shù)在偶特征有限域上的推廣，但APN函數(shù)與射影平面、碼本等并沒(méi)有聯(lián)系.2013年周悅引入偽平面函數(shù)[33]的定義：

定義7.偽平面函數(shù).設(shè)F:F2n→F2n，若對(duì)任意0≠a∈F2n，函數(shù)

DaF=F(x+a)+F(x)+ax

均為F2n上的線性化置換多項(xiàng)式，則稱(chēng)F為偽平面函數(shù).

與PN函數(shù)類(lèi)似，偽平面函數(shù)與射影平面、交換半域等數(shù)學(xué)對(duì)象有著深刻的內(nèi)在聯(lián)系，在壓縮感知矩陣設(shè)計(jì)、最優(yōu)碼本設(shè)計(jì)等領(lǐng)域中有著豐富的應(yīng)用.目前所有已知偽平面函數(shù)都是二次函數(shù)，都對(duì)應(yīng)著F2n上的交換半域.周悅在文獻(xiàn)[33]中給出了2類(lèi)偽平面函數(shù)，分別對(duì)應(yīng)著有限域和Kantor半域.隨后Schmidt、周悅[34]和Scherr,Zieve[35]研究了單項(xiàng)式偽平面函數(shù)，給出了三類(lèi)構(gòu)造.2015胡思煌等人[36]構(gòu)造了三類(lèi)二項(xiàng)式偽平面函數(shù).2016年屈龍江[37]將一大類(lèi)二次函數(shù)為偽平面函數(shù)的判定問(wèn)題轉(zhuǎn)化為一個(gè)對(duì)應(yīng)含參Dickson行列式是否非零的判定問(wèn)題，大大降低了判定時(shí)間復(fù)雜度；利用該Dickson行列式系數(shù)的特殊性質(zhì)能夠進(jìn)一步簡(jiǎn)化計(jì)算證明.該方法不僅構(gòu)造了5類(lèi)新的多項(xiàng)式偽平面函數(shù)，而且將所有已知函數(shù)都統(tǒng)一歸納到了一個(gè)大類(lèi)中.

3 APN函數(shù)

由于密碼學(xué)應(yīng)用主要使用(向量)布爾函數(shù)，所以本節(jié)主要討論偶特征域上的APN函數(shù).對(duì)于奇特征域上APN函數(shù)感興趣的，請(qǐng)參閱文獻(xiàn)[38-40].

3.1 性質(zhì)與判定

APN函數(shù)有一些等價(jià)判別準(zhǔn)則：

定理5.設(shè)F:F2n→F2n，則6個(gè)條件等價(jià)：

1)F為APN函數(shù)，即對(duì)任意a,b∈F2n,a≠0，方程F(x+a)+F(x)=b至多有2個(gè)解；

2) 對(duì)任意使得x+y+z+t=0的兩兩互異的x,y,z,t∈F2n，有F(x)+F(y)+F(z)+F(t)≠0；

3) 對(duì)任意非零a∈F2n，均有|Da(F)|=2n-1，其中Da(F)={F(x+a)+F(x)|x∈F2n}；

4)wt(γF)=22n-1-2n-1，其中γF為由F定義的2n元布爾函數(shù):γF(a,b)=1當(dāng)且僅當(dāng)a≠0，且方程F(x+a)+F(x)=b有解[10]；

5) 對(duì)任意非零a∈F2n，均有:

其中,fλ表示F的組件函數(shù)，F(xiàn)W(g)表示布爾函數(shù)g在x=0處的Walsh譜[41]；

2017年Carlet以Walsh變換為工具刻畫(huà)向量函數(shù)的差分均勻度，特別地，給出APN函數(shù)的如下等價(jià)判別準(zhǔn)則：

定理6[42].設(shè)F:F2n→F2n，則F為APN函數(shù)當(dāng)且僅當(dāng)下列任一條件成立：

APN函數(shù)和AB函數(shù)具有聯(lián)系：

定理7[10,43].設(shè)F:F2n→F2n.若F為AB函數(shù)，則F為APN函數(shù).反過(guò)來(lái)，當(dāng)n為奇數(shù)時(shí)，如果F為APN函數(shù)，且其所有Walsh譜值均被2n+1整除，那么F為AB函數(shù)；特別地，二次APN函數(shù)必為AB函數(shù).

對(duì)于APN冪函數(shù)，Berger等完全刻畫(huà)了它的映射性質(zhì).

定理8[42].設(shè)xd為F2n上的APN函數(shù)，則:

上述結(jié)果表明，F(xiàn)2n(n奇)上的APN冪函數(shù)必然是置換，但F2n(n偶)上的APN冪函數(shù)則不可能為置換.

2011年Leander和Rodier[44]研究了APN函數(shù)的代數(shù)次數(shù)上界，證明了x-1+g(x)，其中g(shù)為非仿射函數(shù)，至多對(duì)有限個(gè)n能在F2n上為APN函數(shù).最近Budaghyan等人[45]研究了F2n上代數(shù)次數(shù)為n的APN函數(shù)的存在性，利用差分、Walsh譜的冪級(jí)數(shù)刻畫(huà)了這些函數(shù)，給出了一些不存在性的結(jié)果.特別地，證明了對(duì)于F2n上多數(shù)已知APN函數(shù)F(x)，x2n-1+F(x)不是APN函數(shù)；這意味著，如果改變這些APN函數(shù)的一個(gè)點(diǎn)，得到的是非APN函數(shù).

2016年Gorodilova[46]刻畫(huà)了APN函數(shù)的子函數(shù)，證明了一個(gè)n元向量函數(shù)為APN函數(shù)當(dāng)且僅當(dāng)其2個(gè)n-1元子函數(shù)或者為APN函數(shù)，或者為4差分函數(shù)，且滿足相容性條件.

3.2 已有構(gòu)造

2005年以前，有限域F2n上APN函數(shù)的研究主要集中于冪函數(shù)，包括Gold函數(shù)、Kasami函數(shù)、Welch函數(shù)、Niho函數(shù)、逆函數(shù)和Dobbertin函數(shù)這6類(lèi)APN冪函數(shù).

3) Welch函數(shù)[50]：x2k+3，其中n=2k+1；

4) Niho函數(shù)[51]：x2k+2k2-1，當(dāng)k是偶數(shù)時(shí)；x2k+2(3k+1)2-1，當(dāng)k是奇數(shù)時(shí)；其中n=2k+1；

5) Inverse函數(shù)[52,48]：x22k-1，其中n=2k+1；

6) Dobbertin函數(shù)[53]：x24k+23k+22k+2k-1，其中n=5k.

2006年Dillon在F26上發(fā)現(xiàn)了很多不等價(jià)于冪函數(shù)的多項(xiàng)式APN函數(shù)[54].學(xué)者們從這些例子出發(fā)，陸續(xù)構(gòu)造了一些與冪函數(shù)不等價(jià)的多項(xiàng)式二次APN函數(shù)無(wú)限類(lèi)，它們的形式是通過(guò)對(duì)不同參數(shù)的Gold函數(shù)進(jìn)行組合得到新的APN函數(shù).我們將這些函數(shù)歸納總結(jié)，它們均是定義在F2n上的:

1) Budaghyan-Carlet-Leander函數(shù)[55]：

x2s+1+α2t-1x2it+2rt+s,

其中,n=lt≥12,l∈{3,4},gcd(t,l)=gcd(s,lt)=1,i≡stmodl,r=l-i,α∈F2n為本原元.

2) Bracken-Byrne-Markin-McGuire第1類(lèi)函數(shù)[56]：

其中,n=2m,m為奇數(shù),γi∈F2m,gcd(s,m)=1,s為奇數(shù)，α,β∈F2n為本原元；

3) Bracken-Byret-Markin-McGuire第2類(lèi)函數(shù)[57]：

α2tx2n-t+2t+s+αx2s+1+βx2n-t+1+γα2t+1x2t+s+2s,

其中,n=3t,gcd(s,3t)=gcd(3,t)=1,3|t+s，α∈F2n為本原元，β,γ∈F2t,βγ≠1；

4) Budaghyan-Carlet第1類(lèi)函數(shù)[55]：

x22s+2s+αx2m+1+βx22s+m+2s+m,

其中,n=2m,gcd(i,m)=1,α,β∈F2n使得：

β2m+1=1,β?{λ(2i+1)(2m-1),λ∈F2n},βα2m+α≠0；

5) Budaghyan-Carlet第2類(lèi)函數(shù)[55]：

x(x2i+x2m+αx2m+i)+x2i(α2mx2m+βx2m+i)+x2m(2i+1)

其中，n=2m，gcd(i,n)=1，β∈F2nF2m，并且x2i+1+αx2i+α2mx+1在F2n上沒(méi)有滿足x2m+1=1的解.

2009年，Budaghyan等人[58]從x3出發(fā)，構(gòu)造了一類(lèi)形式非常簡(jiǎn)單的在任何F2n上都存在的APN函數(shù)無(wú)限類(lèi):

并在文獻(xiàn)[59]中構(gòu)造了更多具有這種形式的APN函數(shù)無(wú)限類(lèi).Edel和Pott[60]研究了構(gòu)造該APN函數(shù)的方法并提出“交換構(gòu)造(switching construction)”技術(shù)，通過(guò)變換已有APN函數(shù)的坐標(biāo)函數(shù)來(lái)構(gòu)造新的APN函數(shù)，得到了目前唯一的一個(gè)既CCZ不等價(jià)于冪函數(shù)也CCZ不等價(jià)于二次函數(shù)的F26上的APN函數(shù):

其中,本原元α為x6+x4+x3+x+1的一個(gè)根.

2011年Carlet[61]以及2013年周悅和Pott等人[27]分別利用向量Bent函數(shù)構(gòu)造APN函數(shù)，該方法得到的構(gòu)造涵蓋了以往的許多構(gòu)造.這2個(gè)構(gòu)造都使用了雙變?cè)硎荆串?dāng)n=2m時(shí)，將F2n視為F2m×F2m.

1) Carlet函數(shù)[61]：令n=2m，整數(shù)i,j滿足gcd(n2,i-j)=1.令

g(x,y)=αx2i+2j+γx2iy2j+δx2jy2i+βy2i+2j,

則：

F(x,y)=(xy,g(x,y))

是APN函數(shù)當(dāng)且僅當(dāng)多項(xiàng)式

g(x,1)=αx2i+2j+γx2i+δx2j+β

在F2m中無(wú)根；

g(x,y)=x2k+1+α(σ(y))2k+1,

則：

F(x,y)=(xy,g(x,y))

是APN函數(shù)當(dāng)且僅當(dāng)α不能寫(xiě)成

a2k+1(t2k+t)(σ(t2k+t))

的形式，其中a,t∈F2m.

2014年，余玉銀等人[62]提出了一個(gè)通過(guò)齊二次函數(shù)對(duì)應(yīng)矩陣坐標(biāo)變換的方法構(gòu)造二次APN函數(shù)，在F27,F28上分別發(fā)現(xiàn)了471類(lèi)和2252類(lèi)CCZ不等價(jià)的二次APN函數(shù).同時(shí)，翁國(guó)標(biāo)等人[63]受DO函數(shù)與半域的對(duì)應(yīng)啟發(fā)，提出了APN代數(shù)(APN algebra)的概念來(lái)刻畫(huà)二次APN函數(shù)，同樣在F27,F28上發(fā)現(xiàn)了大量新的二次APN函數(shù).2014年，Carlet等人[64]通過(guò)尋找特殊形式的二次置換多項(xiàng)式的方法在F28上找到了18類(lèi)APN函數(shù).

介紹一下非凡幾乎完全非線性函數(shù)(exceptional almost perfect nonlinear function)即在無(wú)窮多個(gè)擴(kuò)域上具有幾乎完全非線性的函數(shù).利用代數(shù)幾何的方法，2011年Hernando和McGuire[65]證明了結(jié)果：

定理9.設(shè)d為正整數(shù)，單項(xiàng)式F(x)=xd為F2n上的APN函數(shù)對(duì)無(wú)窮多個(gè)整數(shù)n成立當(dāng)且僅當(dāng)d為Gold指數(shù)或者Kasami指數(shù)，即d=2i+1或d=22i-2i+1.

目前人們僅知道上述2個(gè)非凡APN函數(shù).

3.3 等價(jià)性

理論上分析APN函數(shù)之間的CCZ等價(jià)性非常困難，人們一般通過(guò)計(jì)算機(jī)在小域上計(jì)算一些CCZ等價(jià)不變量來(lái)說(shuō)明APN函數(shù)之間的CCZ等價(jià)性.目前APN函數(shù)CCZ等價(jià)性的理論研究主要集中于冪函數(shù)之間以及多項(xiàng)式函數(shù)與部分冪函數(shù)之間.雖然學(xué)者們普遍認(rèn)為3.2節(jié)中所列出的APN冪函數(shù)相互之間應(yīng)該是CCZ不等價(jià)的，但在很長(zhǎng)一段時(shí)間里，Gold函數(shù)、Kasami函數(shù)、Welch函數(shù)和Niho函數(shù)四者之間的等價(jià)性以及逆函數(shù)和Dobbertin函數(shù)兩者之間的等價(jià)性目前都沒(méi)能給出嚴(yán)格的數(shù)學(xué)證明[31].直到2018年，Dempwolf[66]完全解決了冪函數(shù)之間的CCZ等價(jià)性問(wèn)題.但各類(lèi)多項(xiàng)式APN函數(shù)無(wú)限類(lèi)之間的CCZ等價(jià)性依舊是公開(kāi)問(wèn)題.目前已有的結(jié)果可以歸結(jié)為6個(gè)方面：

1) 參數(shù)不同的Gold函數(shù)之間是CCZ不等價(jià)的[67]；

2) 逆函數(shù)和Dobbertin函數(shù)這2類(lèi)函數(shù)與Gold函數(shù),Kasami函數(shù),Welch函數(shù) 和 Niho函數(shù)這四類(lèi)函數(shù)之間CCZ不等價(jià)[68-69]；

3) Budaghyan[55]證明了當(dāng)n≥12時(shí)，論文中構(gòu)造的APN函數(shù)CCZ不等價(jià)于Gold函數(shù)、Kasami函數(shù)、逆函數(shù)和Dobbertin函數(shù)且EA不等價(jià)于任何冪函數(shù)；

4) 2012年Yoshiara[70]證明了Edel的猜想：2個(gè)二次APN函數(shù)CCZ等價(jià)當(dāng)且僅當(dāng)它們EA等價(jià)；

5) 2017年Yoshiara[71]證明了n為偶數(shù)時(shí)，如果有2個(gè)plateaued APN函數(shù)且其中一個(gè)為冪函數(shù)，則它們CCZ等價(jià)當(dāng)且僅當(dāng)它們EA等價(jià)；

6) Dempwolf[66]證明了Fpn上的2個(gè)冪函數(shù)xk和xl是CCZ等價(jià)的當(dāng)且僅當(dāng)存在整數(shù)0≤a

另外，目前所有二次APN函數(shù)族的Walsh譜都得到了計(jì)算，結(jié)果表明，這些函數(shù)都具有與Gold函數(shù)相同的Walsh譜，即當(dāng)n為奇數(shù)時(shí)為三譜值，而當(dāng)n為偶數(shù)時(shí)為五譜值[72-73,58].

3.4 大APN問(wèn)題

為了避免熵泄露，一般要求分組密碼中使用的向量函數(shù)是個(gè)置換；同時(shí)為了軟硬件實(shí)現(xiàn)時(shí)具有較高的效率，又希望其定義在二元域的偶數(shù)維擴(kuò)域(偶數(shù)維擴(kuò)張，以下簡(jiǎn)稱(chēng)偶擴(kuò)張)上.于是尋找偶擴(kuò)張上的APN置換就成為了密碼學(xué)研究中的一個(gè)重要問(wèn)題，該問(wèn)題被稱(chēng)為“大APN問(wèn)題(big APN problem)”.

問(wèn)題1.大APN問(wèn)題.當(dāng)n為偶數(shù)時(shí)，是否存在F2n上的APN置換？

該問(wèn)題已經(jīng)公開(kāi)近30年了，是目前密碼函數(shù)領(lǐng)域里最著名的公開(kāi)問(wèn)題.很長(zhǎng)一段時(shí)間里，人們只能得到關(guān)于該問(wèn)題的一些負(fù)面結(jié)果，于是很多密碼學(xué)家和數(shù)學(xué)家猜想，F(xiàn)2的偶次擴(kuò)域上不存在APN置換.但2009年Dillon等人發(fā)現(xiàn)了F26上的一個(gè)APN置換[74]，然而n≥8情況下的“大APN問(wèn)題”目前仍然是公開(kāi)的.關(guān)于“大APN問(wèn)題”，目前已知有4個(gè)方面結(jié)果：

1) 2009年Dillon通過(guò)分解一個(gè)APN函數(shù)所對(duì)應(yīng)的線性碼，找到了F26上的一個(gè)APN置換[74].但其表達(dá)形式非常復(fù)雜.2016年，Perrin等人[75]提出了“蝴蝶結(jié)構(gòu)(butterfly structure)”，很好地從理論上詮釋了這個(gè)APN置換，但是，他們的方法并沒(méi)有發(fā)現(xiàn)偶擴(kuò)張上的其他APN置換.

2)F22和F24上不存在APN置換.Langevin等人[76]結(jié)合計(jì)算機(jī)驗(yàn)證指出，F(xiàn)26上的3次APN置換一定與Dillon等人發(fā)現(xiàn)的APN置換是CCZ等價(jià)的.

3) 定理8表明偶擴(kuò)張上的冪函數(shù)不可能為APN置換.Seberry等人證明了偶擴(kuò)張上的二次函數(shù)也不可能為APN置換.Pasalic[77]、李永強(qiáng)等人[78-79]分別證明了某些形如一個(gè)冪函數(shù)和一個(gè)線性函數(shù)的和函數(shù)不可能為APN置換.

APN函數(shù)研究的困難性有3個(gè)方面：1)一個(gè)隨機(jī)函數(shù)是APN函數(shù)的概率很低，這為其搜索、構(gòu)造帶來(lái)很大困難；2)缺乏判斷CCZ等價(jià)的有效工具，研究中人們經(jīng)常會(huì)發(fā)現(xiàn)找到的函數(shù)CCZ等價(jià)于已知函數(shù)；3)除了單項(xiàng)式(冪函數(shù))和二項(xiàng)式外，已知APN函數(shù)的表達(dá)形式往往比較復(fù)雜，例如Dillon等人構(gòu)造的APN置換，這也進(jìn)一步研究帶來(lái)較大困難.因此我們對(duì)于APN函數(shù)的認(rèn)識(shí)還不夠深刻，亟需更深刻、更有力的研究工具.

4 4差分置換

4差分函數(shù)是偶特征有限域上具有次優(yōu)差分均勻度的函數(shù).4差分函數(shù)的構(gòu)造并不困難，一種自然的方法是復(fù)合一個(gè)APN函數(shù)和一個(gè)2到1的線性函數(shù).從密碼應(yīng)用角度看，由于缺乏偶擴(kuò)張上的APN置換，密碼算法S -盒設(shè)計(jì)的一個(gè)自然選擇就是使用4差分置換，比如著名AES(advanced encryption standard)算法的S -盒使用了F28上的逆函數(shù)就是一個(gè)4差分置換.偶擴(kuò)張上4差分置換的構(gòu)造與性質(zhì)對(duì)于對(duì)稱(chēng)密碼設(shè)計(jì)與分析具有十分重要的意義.因此接下來(lái)本節(jié)只論述偶擴(kuò)張上4差分置換.

4.1 已有構(gòu)造

近年來(lái)偶擴(kuò)張上4差分置換的研究受到較多關(guān)注，人們給出了一系列新的構(gòu)造，下面分為具有五譜值的4差分置換和從逆函數(shù)出發(fā)構(gòu)造的4差分置換兩大類(lèi)進(jìn)行敘述.

4.1.1 具有五譜值的4差分置換

已有具有五譜值的4差分置換其Walsh譜取值均為{0，±2n/2,±2(n+2)/2}，因此非線性度達(dá)到已知最優(yōu)2n-1-2n/2，其中一些構(gòu)造的代數(shù)次數(shù)也不太低，但目前已有的構(gòu)造均無(wú)法達(dá)到最優(yōu)代數(shù)次數(shù)n-1.

1) 基礎(chǔ)構(gòu)造

2011年以前，偶擴(kuò)張上的4差分置換無(wú)限類(lèi)只有Gold函數(shù)、Kasami函數(shù)、逆函數(shù)、Bracken-Leander函數(shù)和Bracken-Tan-Tan函數(shù)5類(lèi)基礎(chǔ)構(gòu)造.其中除了逆函數(shù)外，其余4類(lèi)Walsh譜取值均為{0，±2n2,±2(n+2)2}.

① Gold函數(shù)[47]：x2i+1，其中n=2k，k為奇數(shù)且gcd(i,n)=2；

② Kasami函數(shù)[81-82]：x22i-2i+1，其中n=2k，k為奇數(shù)且gcd(i,n)=2；

③ 逆函數(shù)：x-1，其中定義0-1=0；

④ Bracken-Leander函數(shù)[83]：x22k+2k+1，其中n=4k，k為奇數(shù)；

⑤ Bracken-Tan-Tan函數(shù)[84]：αx2s+1+α2kx2-k+2k+s，其中n=3k，k是偶數(shù)，但3?k且k2是奇數(shù)，gcd(i,n)=2，3|(k+s)，α是F2n上的本原元.

其中,前4類(lèi)為冪函數(shù)，最后一類(lèi)為二項(xiàng)式函數(shù).除了Kasami函數(shù)和逆函數(shù)之外，其他函數(shù)的代數(shù)次數(shù)都是2或者3，且僅有逆函數(shù)是對(duì)合函數(shù).容易看出，這里除了Bracken-Leander函數(shù)以外，其余3類(lèi)都是從APN函數(shù)修改構(gòu)造的.

2) Gold函數(shù)收縮構(gòu)造

2011年Carlet提出了一種利用F22k+1上APN置換來(lái)構(gòu)造F22k上4差分置換的方法[85].李永強(qiáng)等人對(duì)該方法進(jìn)行了進(jìn)一步研究，從Gold函數(shù)出發(fā)，成功地構(gòu)造了2類(lèi)偶擴(kuò)張上的具有已知最優(yōu)非線性度的4差分置換[86].其具體形式如下:

限制在T(0)上的函數(shù).

這2類(lèi)函數(shù)的代數(shù)次數(shù)為(n+2)2，但均不是對(duì)合函數(shù).

3) 蝴蝶結(jié)構(gòu)

① Perrin-Udovenko-Biryukov構(gòu)造[75]：

R(x,y)=(x+αy)3+y3，

② Canteaut-Duval-Perrin構(gòu)造[87]：

R(x,y)=(x+αy)3+βy3,

③ Fu-Feng構(gòu)造[88-89]：

R(x,y)=(x+αy)2t(2i+1)+y2t(2i+1)，

這些4差分置換具有已知最優(yōu)的非線性度，代數(shù)次數(shù)為n2或者(n+2)2，這些函數(shù)的“開(kāi)蝴蝶結(jié)構(gòu)”形式均為對(duì)合的.利用“蝴蝶結(jié)構(gòu)”可以給出Dillon等構(gòu)造APN置換的簡(jiǎn)潔表達(dá)形式.但遺憾的是Canteaut等證明在該結(jié)構(gòu)構(gòu)造的函數(shù)中，除了Dillon等構(gòu)造的APN置換外，沒(méi)有其他APN置換.

4.1.2 從逆函數(shù)出發(fā)構(gòu)造的4差分置換

當(dāng)n為偶數(shù)時(shí)，逆函數(shù)x-1是對(duì)合的4差分置換[48,52]，具有最優(yōu)代數(shù)次數(shù)n-1，其非線性度達(dá)到已知最優(yōu)2n-1-2n2，Walsh譜可以取遍±2(n+2)2之間的每一個(gè)被4整除的整數(shù)值.AES,Camellia等很多標(biāo)準(zhǔn)算法均使用逆函數(shù)做S盒.從逆函數(shù)出發(fā)構(gòu)造的4差分置換普遍具有最優(yōu)代數(shù)次數(shù)n-1和較高的非線性度，其中一些子類(lèi)還可以達(dá)到已知最優(yōu)非線性度.

1) 逆函數(shù)交換構(gòu)造

2013年屈龍江等人通過(guò)“交換構(gòu)造(switching construction)” 的技術(shù)研究了逆函數(shù)，提出了優(yōu)先函數(shù)的概念，并且以此為工具構(gòu)造為

其中,d=2n-2 或者 3(2t+1)，2≤t≤n2-1的2個(gè)簡(jiǎn)潔的4差分置換無(wú)限類(lèi)[90].他們又提出優(yōu)先布爾函數(shù)的概念，在偶擴(kuò)張上構(gòu)造出了至少2(2n+2)3個(gè)形如x-1+f(x-1)的具有最優(yōu)代數(shù)次數(shù)的4差分置換，從而在理論上首次證明了F22k上4差分置換的個(gè)數(shù)是隨著變?cè)獋€(gè)數(shù)增長(zhǎng)而呈雙指數(shù)增長(zhǎng)的[91].這些函數(shù)都可以看作是在逆函數(shù)基礎(chǔ)上添加某個(gè)布爾函數(shù)得到的，我們簡(jiǎn)稱(chēng)為BI函數(shù)，這類(lèi)函數(shù)是4差分置換的充分必要條件如下[92]：

BI 4差分置換：令n為偶數(shù)，ω是F2n中階為3的元素，f是n元布爾函數(shù).則BI函數(shù)是4差分置換當(dāng)且僅當(dāng)對(duì)于任意x∈F2n均有f(x)=f(x+1)且對(duì)于任意z∈F2nF4，2個(gè)等式中至少有一個(gè)成立：

查正邦等學(xué)者[93-94]、彭杰等學(xué)者[95]也先后研究了逆函數(shù)的交換構(gòu)造法，并進(jìn)一步研究了其中一些具有良好密碼學(xué)性質(zhì)的子類(lèi).BI 4差分置換具有最優(yōu)代數(shù)次數(shù)和較高的非線性度，其中一些子類(lèi)還具有已知最優(yōu)非線性度.BI 4差分置換是對(duì)合函數(shù)當(dāng)且僅當(dāng)2種情況之一成立[96]：

①n=2k，k為奇數(shù)，

Supp(f)={0,1},{ω,ω2}或{0,1,ω,ω2}；

②n=2k，k為偶數(shù)，

Supp(f)={0,1,ω,ω2}.

2) 逆函數(shù)其他修改構(gòu)造

李永強(qiáng)、查正邦、彭杰、唐燈和Carlet等學(xué)者也先后通過(guò)不同的方法對(duì)F2n上的逆函數(shù)進(jìn)行修改，得到了一些新的4差分置換，這些4差分置換普遍具有最優(yōu)代數(shù)次數(shù)和較高的非線性度.具體修改方式為：

① Li-Wang-Yu構(gòu)造[97]：

其中,{ai|0≤i≤m}為滿足一定條件的圈.

② Zha-Hu-Sun構(gòu)造[93]：

其中,d是偶數(shù)，d|n且nd為奇數(shù)，

③ Peng-Tan構(gòu)造[98]：

其中,α,β∈F2d滿足某些具體條件.

④ Peng-Tan-Wang第1類(lèi)構(gòu)造[99]：

其中,γ∈F2n，U是循環(huán)群γ中一些集合的并.

⑤ Peng-Tan-Wang第2類(lèi)構(gòu)造[100]：

其中,U是F2nF4中一些六元集合的并.

⑥ Tang-Carlet-Tang構(gòu)造[101]：

其中,第⑥類(lèi)函數(shù)的逆變換是BI 4差分置換，因此它們是CCZ等價(jià)的.前5類(lèi)函數(shù)均包含一些對(duì)合的4差分置換子類(lèi)，這里不具體列出相關(guān)條件，感興趣的讀者請(qǐng)參閱文獻(xiàn)[96].

3) 逆函數(shù)擴(kuò)張構(gòu)造

2014年，Carlet和唐燈等人[102]利用F22k-1上的逆函數(shù)是APN函數(shù)這一特性，構(gòu)造了F22k上一大類(lèi)

4.2 等價(jià)性研究

4差分置換同樣可以通過(guò)計(jì)算差分譜、擴(kuò)展Walsh譜、Γ-秩、Δ-秩和各種形式的自同構(gòu)群等CCZ等價(jià)不變量來(lái)判斷它們之間的等價(jià)性，最常見(jiàn)的是計(jì)算Walsh譜和差分譜.具有五譜值的4差分置換和從逆函數(shù)出發(fā)構(gòu)造的4差分置換這2類(lèi)相互之間的CCZ不等價(jià)性一般可以通過(guò)計(jì)算Walsh 譜來(lái)證明或者驗(yàn)證，因?yàn)閺哪婧瘮?shù)出發(fā)構(gòu)造的4差分置換一般不是五譜值的.而在每一大類(lèi)里各自不同構(gòu)造之間的CCZ不等價(jià)性多數(shù)情況下是通過(guò)在小域上計(jì)算Walsh譜或者差分譜來(lái)驗(yàn)證的.接下來(lái)我們主要描述該方面的理論結(jié)果.

首先，具有五譜值的4差分置換之間的等價(jià)性研究相對(duì)較少.由于函數(shù)存在域的不同，Bracken-Leander函數(shù)、Bracken-Tan-Tan函數(shù)與其他2類(lèi)基礎(chǔ)構(gòu)造是CCZ不等價(jià)的.其次，由于F2n上一個(gè)函數(shù)的CCZ等價(jià)類(lèi)里至多包含24n2+2n個(gè)函數(shù)，而B(niǎo)I 4差分置換里至少有2(2n+2)/3個(gè)函數(shù)，因此BI 4差分置換里至少含有2(2n+2)/3-4n2-2n個(gè)不同的CCZ等價(jià)類(lèi)[91].再次，唐燈和Carlet等人通過(guò)差分譜證明了BI 4差分置換與Carlet-Tang-Tang-Liao函數(shù)這兩大類(lèi)4差分置換分別與二次函數(shù)是CCZ不等價(jià)的，并分別從這2類(lèi)4差分置換中找出了一些子類(lèi)在理論上證明了這些子類(lèi)與逆函數(shù)是CCZ不等價(jià)的[101].最后，陳璽等人提出投影差分譜的概念，將所研究的函數(shù)投影到低維空間上，檢驗(yàn)其投影函數(shù)的投影差分譜是否滿足2個(gè)CCZ等價(jià)函數(shù)投影差分譜所滿足的必要條件，并通過(guò)該方法證明了所有 Carlet-Tang-Tang-Liao函數(shù)與逆函數(shù)是CCZ不等價(jià)的[103].

5 應(yīng) 用

本節(jié)簡(jiǎn)單地回顧低差分函數(shù)在實(shí)際密碼算法中的應(yīng)用.

在Nyberg和Knudsen設(shè)計(jì)的64 b類(lèi)似DES的KN密碼中，使用了域F233上二次單項(xiàng)式x|→x3[104].但隨后Jakobsen和Knudsen利用x3函數(shù)代數(shù)次數(shù)太低的弱點(diǎn)提出了高階差分攻擊[105]，攻破了KN 密碼.KASUMI算法[106]使用了64 b的8輪DES -類(lèi)置換，F(xiàn)O和FL是其中的2輪置換.FO函數(shù)是一個(gè)32 b置換，它由含有FI輪置換的3輪MISTY型變換所組成.FI函數(shù)是一個(gè)4輪非平衡MISTY-type變換所組成的16 b置換，它由一個(gè)7 b APN置換與一個(gè)9 b APN置換組成.

1998年NIST發(fā)起了一場(chǎng)為了建立新分組密碼標(biāo)準(zhǔn)的比賽，由比利時(shí)密碼學(xué)家Daemen和Rijmen設(shè)計(jì)的Rijndael算法最終勝出，被遴選為AES算法[107].AES算法使用的S -盒是有限域F28上逆函數(shù)的仿射變換，這個(gè)4差分置換[108]達(dá)到了8維空間上已知最優(yōu)的差分均勻度和已知最優(yōu)的非線性度.除了AES算法以外，Camellia算法[109]、PRESENT算法[110]、PRINCE算法[111]、LED算法[112]等近期設(shè)計(jì)算法中均使用了逆函數(shù)作為S盒.

FIDES是Bilgin等設(shè)計(jì)的認(rèn)證加密算法[113]，其置換由32個(gè)Dillon等發(fā)現(xiàn)的APN置換組成.該APN置換的代數(shù)次數(shù)是4，非線性度與逆函數(shù)的非線性度相同均為16，同樣達(dá)到已知最大非線性度.這表明對(duì)該函數(shù)的差分攻擊和線性攻擊與逆函數(shù)的情況類(lèi)似.但FIDES算法的構(gòu)造設(shè)計(jì)存在缺陷.Dinur和Jean[114]使用猜測(cè)-決定攻擊破譯了FIDES算法，該攻擊基于線性層中擴(kuò)散上的弱點(diǎn)，S -盒的差分性質(zhì)對(duì)這種攻擊完全不起作用.該結(jié)果表明，密碼算法設(shè)計(jì)即使使用密碼學(xué)性質(zhì)良好的低差分置換，也還需要精心設(shè)計(jì)密碼結(jié)構(gòu)，避免存在安全缺陷.

6 總 結(jié)

綜上所述，近年來(lái)國(guó)內(nèi)外學(xué)者在有限域上低差分函數(shù)研究方面已經(jīng)取得了許多重要的結(jié)果，但仍有許多問(wèn)題亟需進(jìn)一步的研究.例如已有PN函數(shù)和APN函數(shù)構(gòu)造都集中在冪函數(shù)和二次函數(shù)，如何構(gòu)造一個(gè)(CCZ等價(jià)意義下)非二次的多項(xiàng)式PN函數(shù)和APN函數(shù)是低差分函數(shù)研究中的一個(gè)非常重要的問(wèn)題.還有，已知的PN冪函數(shù)和APN冪函數(shù)列表是否完全？二次PN函數(shù)和APN函數(shù)的CCZ等價(jià)類(lèi)個(gè)數(shù)是否隨變?cè)獋€(gè)數(shù)增長(zhǎng)而呈指數(shù)增長(zhǎng)？“大APN問(wèn)題”，即一般偶擴(kuò)張上是否存在APN置換的問(wèn)題，還遠(yuǎn)沒(méi)有解決.另外，能否構(gòu)造與Gold函數(shù)具有不同Walsh譜的二次APN函數(shù)類(lèi)也是一個(gè)非常有趣的問(wèn)題.最后，盡管人們?cè)谂紨U(kuò)張已經(jīng)構(gòu)造了大量的4差分置換，但像逆函數(shù)那樣多種密碼學(xué)指標(biāo)折衷最優(yōu)的密碼函數(shù)的構(gòu)造還很匱乏.另外，已知偶擴(kuò)張上4差分置換無(wú)限類(lèi)要么是從逆函數(shù)出發(fā)構(gòu)造的，要么與Gold函數(shù)聯(lián)系緊密，能否通過(guò)其他的方法進(jìn)行構(gòu)造是非常有趣的問(wèn)題.所有這些問(wèn)題都值得我們繼續(xù)深入研究.