有限域上低差分函數研究進展

屈龍江 陳 璽 牛泰霖 李 超

(國防科技大學文理學院 長沙 410073) (ljqu_happy@hotmail.com)

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

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

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

1 基本概念和知識

1.1 基本概念

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

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

如果F為有限域Fpn到其自身的映射，則它可以表示為Fpn上的單變元多項式：

定義1.代數次數.設F為有限域Fpn到其自身的映射，其單變元表示為

那么F的代數次數定義為

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

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

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

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

(1)

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

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

F的非線性度定義為

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

1.2 CCZ等價與EA等價

新的低差分函數的構造是密碼函數研究中的重要問題，它涉及到這些函數之間的等價性問題.最主要的等價性有2個：CCZ等價和EA等價.

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

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

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

由于在理論上分析不同函數之間的CCZ等價性非常困難，實踐上人們一般通過計算機計算一些CCZ等價不變量，比如差分均勻度、擴展Walsh譜、Γ-秩、Δ-秩和各種形式的自同構群等.如果2個函數有不同的CCZ等價不變量，則它們一定不等價；反之則不能判斷.另外，一個無限函數類的差分均勻度、擴展Walsh譜等CCZ等價不變量的有效計算研究在理論上和應用上都是很有意義的，特別是擴展Walsh譜的計算.這不僅是因為由擴展Walsh譜可以決定出非線性度，還因為：由APN函數可以構造性能優良的線性碼，并且APN函數的擴展Walsh譜對應于該線性碼的重量分布，而線性碼的重量分布是線性碼的一個重要參數，利用其可以有效計算譯碼算法的錯誤概率.

2 PN函數

2.1 性質與判定

PN函數有一些等價判別準則.

定理1.設F:Fpn→Fpn，則3個條件等價：

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

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

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

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

特別地，對于二次PN函數，也稱為Demobowski-Ostrom(DO)型函數，有等價判定準則：

定理2.設F:Fpn→Fpn且為二次函數，則2個條件等價：

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

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

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

預半域與域相比，可能失去結合律且可能不含單位元.

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

2012年翁國標和曾祥勇刻畫了DO型PN函數的映射性質[17].

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

2.2 已有構造

2005年以前，有限域Fpn上PN函數的研究主要集中于冪函數(單項式)，包括2類(不等價的)PN冪函數：

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

π1(x)=xpt+1,

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

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

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

2006年以后，人們陸續發現了一些多項式形式的二次PN函數.目前Fpn上已知的多項式PN函數有：

1) Ding-Yuan多項式[19-20]：

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

2) Zha-Kyureghyan-Wang多項式[21]：

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

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

3) Budaghyan-Helleseth第1類多項式[22]：

4) Budaghyan-Helleseth第2類多項式[22]：

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

5) Bierbrauer多項式[23]：

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

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

如定理2所述，上述二次PN函數還等價于交換預半域.人們還構造了一些其他的半域，其對應的多項式較復雜，下面列出這些半域，感興趣的讀者可以自行推導其對應PN函數的多項式表達式：

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

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

其中,α∈Fqk為一個非平方元；

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

(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為一個非平方元；

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

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

其中,α∈Fpm為一個非平方元；δ為Fpm上的一個自同構.

除此之外，人們還在F35,F38,F55中發現了一些零散半域[28-30].目前還不能把它們推廣到無限類.

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

定義6.非凡完全非線性函數(exceptional perfect nonlinear function).設F:Fq→Fq, 若F在Fq的無窮多個擴域上為完全非線性函數，則稱F為非凡完全非線性函數.若F(x)=xd，則稱d為非凡完全非線性指數.

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

定理4.設p為奇素數，d為正整數，單項式F(x)=xd為Fpn上的完全非線性函數對無窮多個整數n成立當且僅當d為下列情形之一：

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

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

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

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

定義7.偽平面函數.設F:F2n→F2n，若對任意0≠a∈F2n，函數

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

均為F2n上的線性化置換多項式，則稱F為偽平面函數.

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

3 APN函數

由于密碼學應用主要使用(向量)布爾函數，所以本節主要討論偶特征域上的APN函數.對于奇特征域上APN函數感興趣的，請參閱文獻[38-40].

3.1 性質與判定

APN函數有一些等價判別準則：

定理5.設F:F2n→F2n，則6個條件等價：

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

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

3) 對任意非零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元布爾函數:γF(a,b)=1當且僅當a≠0，且方程F(x+a)+F(x)=b有解[10]；

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

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

2017年Carlet以Walsh變換為工具刻畫向量函數的差分均勻度，特別地，給出APN函數的如下等價判別準則：

定理6[42].設F:F2n→F2n，則F為APN函數當且僅當下列任一條件成立：

APN函數和AB函數具有聯系：

定理7[10,43].設F:F2n→F2n.若F為AB函數，則F為APN函數.反過來，當n為奇數時，如果F為APN函數，且其所有Walsh譜值均被2n+1整除，那么F為AB函數；特別地，二次APN函數必為AB函數.

對于APN冪函數，Berger等完全刻畫了它的映射性質.

定理8[42].設xd為F2n上的APN函數，則:

上述結果表明，F2n(n奇)上的APN冪函數必然是置換，但F2n(n偶)上的APN冪函數則不可能為置換.

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

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

3.2 已有構造

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

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

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

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

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

2006年Dillon在F26上發現了很多不等價于冪函數的多項式APN函數[54].學者們從這些例子出發，陸續構造了一些與冪函數不等價的多項式二次APN函數無限類，它們的形式是通過對不同參數的Gold函數進行組合得到新的APN函數.我們將這些函數歸納總結，它們均是定義在F2n上的:

1) Budaghyan-Carlet-Leander函數[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類函數[56]：

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

3) Bracken-Byret-Markin-McGuire第2類函數[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類函數[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類函數[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上沒有滿足x2m+1=1的解.

2009年，Budaghyan等人[58]從x3出發，構造了一類形式非常簡單的在任何F2n上都存在的APN函數無限類:

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

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

2011年Carlet[61]以及2013年周悅和Pott等人[27]分別利用向量Bent函數構造APN函數，該方法得到的構造涵蓋了以往的許多構造.這2個構造都使用了雙變元表示，即當n=2m時，將F2n視為F2m×F2m.

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

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

則：

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

是APN函數當且僅當多項式

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

在F2m中無根；

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

則：

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

是APN函數當且僅當α不能寫成

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

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

2014年，余玉銀等人[62]提出了一個通過齊二次函數對應矩陣坐標變換的方法構造二次APN函數，在F27,F28上分別發現了471類和2252類CCZ不等價的二次APN函數.同時，翁國標等人[63]受DO函數與半域的對應啟發，提出了APN代數(APN algebra)的概念來刻畫二次APN函數，同樣在F27,F28上發現了大量新的二次APN函數.2014年，Carlet等人[64]通過尋找特殊形式的二次置換多項式的方法在F28上找到了18類APN函數.

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

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

目前人們僅知道上述2個非凡APN函數.

3.3 等價性

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

1) 參數不同的Gold函數之間是CCZ不等價的[67]；

2) 逆函數和Dobbertin函數這2類函數與Gold函數,Kasami函數,Welch函數 和 Niho函數這四類函數之間CCZ不等價[68-69]；

3) Budaghyan[55]證明了當n≥12時，論文中構造的APN函數CCZ不等價于Gold函數、Kasami函數、逆函數和Dobbertin函數且EA不等價于任何冪函數；

4) 2012年Yoshiara[70]證明了Edel的猜想：2個二次APN函數CCZ等價當且僅當它們EA等價；

5) 2017年Yoshiara[71]證明了n為偶數時，如果有2個plateaued APN函數且其中一個為冪函數，則它們CCZ等價當且僅當它們EA等價；

6) Dempwolf[66]證明了Fpn上的2個冪函數xk和xl是CCZ等價的當且僅當存在整數0≤a

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

3.4 大APN問題

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

問題1.大APN問題.當n為偶數時，是否存在F2n上的APN置換？

該問題已經公開近30年了，是目前密碼函數領域里最著名的公開問題.很長一段時間里，人們只能得到關于該問題的一些負面結果，于是很多密碼學家和數學家猜想，F2的偶次擴域上不存在APN置換.但2009年Dillon等人發現了F26上的一個APN置換[74]，然而n≥8情況下的“大APN問題”目前仍然是公開的.關于“大APN問題”，目前已知有4個方面結果：

1) 2009年Dillon通過分解一個APN函數所對應的線性碼，找到了F26上的一個APN置換[74].但其表達形式非常復雜.2016年，Perrin等人[75]提出了“蝴蝶結構(butterfly structure)”，很好地從理論上詮釋了這個APN置換，但是，他們的方法并沒有發現偶擴張上的其他APN置換.

2)F22和F24上不存在APN置換.Langevin等人[76]結合計算機驗證指出，F26上的3次APN置換一定與Dillon等人發現的APN置換是CCZ等價的.

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

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

4 4差分置換

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

4.1 已有構造

近年來偶擴張上4差分置換的研究受到較多關注，人們給出了一系列新的構造，下面分為具有五譜值的4差分置換和從逆函數出發構造的4差分置換兩大類進行敘述.

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

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

1) 基礎構造

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

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

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

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

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

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

其中,前4類為冪函數，最后一類為二項式函數.除了Kasami函數和逆函數之外，其他函數的代數次數都是2或者3，且僅有逆函數是對合函數.容易看出，這里除了Bracken-Leander函數以外，其余3類都是從APN函數修改構造的.

2) Gold函數收縮構造

2011年Carlet提出了一種利用F22k+1上APN置換來構造F22k上4差分置換的方法[85].李永強等人對該方法進行了進一步研究，從Gold函數出發，成功地構造了2類偶擴張上的具有已知最優非線性度的4差分置換[86].其具體形式如下:

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

這2類函數的代數次數為(n+2)2，但均不是對合函數.

3) 蝴蝶結構

① Perrin-Udovenko-Biryukov構造[75]：

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

② Canteaut-Duval-Perrin構造[87]：

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

③ Fu-Feng構造[88-89]：

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

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

4.1.2 從逆函數出發構造的4差分置換

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

1) 逆函數交換構造

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

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

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

查正邦等學者[93-94]、彭杰等學者[95]也先后研究了逆函數的交換構造法，并進一步研究了其中一些具有良好密碼學性質的子類.BI 4差分置換具有最優代數次數和較高的非線性度，其中一些子類還具有已知最優非線性度.BI 4差分置換是對合函數當且僅當2種情況之一成立[96]：

①n=2k，k為奇數，

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

②n=2k，k為偶數，

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

2) 逆函數其他修改構造

李永強、查正邦、彭杰、唐燈和Carlet等學者也先后通過不同的方法對F2n上的逆函數進行修改，得到了一些新的4差分置換，這些4差分置換普遍具有最優代數次數和較高的非線性度.具體修改方式為：

① Li-Wang-Yu構造[97]：

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

② Zha-Hu-Sun構造[93]：

其中,d是偶數，d|n且nd為奇數，

③ Peng-Tan構造[98]：

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

④ Peng-Tan-Wang第1類構造[99]：

其中,γ∈F2n，U是循環群γ中一些集合的并.

⑤ Peng-Tan-Wang第2類構造[100]：

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

⑥ Tang-Carlet-Tang構造[101]：

其中,第⑥類函數的逆變換是BI 4差分置換，因此它們是CCZ等價的.前5類函數均包含一些對合的4差分置換子類，這里不具體列出相關條件，感興趣的讀者請參閱文獻[96].

3) 逆函數擴張構造

2014年，Carlet和唐燈等人[102]利用F22k-1上的逆函數是APN函數這一特性，構造了F22k上一大類

4.2 等價性研究

4差分置換同樣可以通過計算差分譜、擴展Walsh譜、Γ-秩、Δ-秩和各種形式的自同構群等CCZ等價不變量來判斷它們之間的等價性，最常見的是計算Walsh譜和差分譜.具有五譜值的4差分置換和從逆函數出發構造的4差分置換這2類相互之間的CCZ不等價性一般可以通過計算Walsh 譜來證明或者驗證，因為從逆函數出發構造的4差分置換一般不是五譜值的.而在每一大類里各自不同構造之間的CCZ不等價性多數情況下是通過在小域上計算Walsh譜或者差分譜來驗證的.接下來我們主要描述該方面的理論結果.

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

5 應 用

本節簡單地回顧低差分函數在實際密碼算法中的應用.

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

1998年NIST發起了一場為了建立新分組密碼標準的比賽，由比利時密碼學家Daemen和Rijmen設計的Rijndael算法最終勝出，被遴選為AES算法[107].AES算法使用的S -盒是有限域F28上逆函數的仿射變換，這個4差分置換[108]達到了8維空間上已知最優的差分均勻度和已知最優的非線性度.除了AES算法以外，Camellia算法[109]、PRESENT算法[110]、PRINCE算法[111]、LED算法[112]等近期設計算法中均使用了逆函數作為S盒.

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

6 總 結

綜上所述，近年來國內外學者在有限域上低差分函數研究方面已經取得了許多重要的結果，但仍有許多問題亟需進一步的研究.例如已有PN函數和APN函數構造都集中在冪函數和二次函數，如何構造一個(CCZ等價意義下)非二次的多項式PN函數和APN函數是低差分函數研究中的一個非常重要的問題.還有，已知的PN冪函數和APN冪函數列表是否完全？二次PN函數和APN函數的CCZ等價類個數是否隨變元個數增長而呈指數增長？“大APN問題”，即一般偶擴張上是否存在APN置換的問題，還遠沒有解決.另外，能否構造與Gold函數具有不同Walsh譜的二次APN函數類也是一個非常有趣的問題.最后，盡管人們在偶擴張已經構造了大量的4差分置換，但像逆函數那樣多種密碼學指標折衷最優的密碼函數的構造還很匱乏.另外，已知偶擴張上4差分置換無限類要么是從逆函數出發構造的，要么與Gold函數聯系緊密，能否通過其他的方法進行構造是非常有趣的問題.所有這些問題都值得我們繼續深入研究.