一類2t-差分置換多項式

謝 濤, 朱小琨, 左可正

(1.湖北大學 數學與統計學學院, 武漢 430062; 2.華中師范大學 數學與統計學學院, 武漢 430079;3. 湖北師范學院 數學與統計學院, 湖北 黃石 435002)

?

一類2t-差分置換多項式

謝 濤1,3, 朱小琨2*, 左可正3

(1.湖北大學 數學與統計學學院, 武漢 430062; 2.華中師范大學 數學與統計學學院, 武漢 430079;3. 湖北師范學院 數學與統計學院, 湖北 黃石 435002)

構造了有限域F23k(k≥1)上一類二項式函數, 利用有限域上單變元方程化為多變元方程組的方法證明了該函數是差分均勻度為2t(t≥1)的置換.由此得到一類APN置換和4-差分置換, 并發現該兩類低差分置換是已有結果的推廣.

差分均勻度; 置換多項式; APN函數

F(x)+F(x+a)=b

在F2n中的解的個數都不超過δ, 則稱F是δ-差分一致函數[1]或者F的差分均勻度為δ.2-差分一致函數稱為almost perfect nonlinear (APN)函數.如果F是F2n到自身的一個一一映射,則稱F是一個置換.為了抵抗差分攻擊和線性攻擊及硬件方面實現的方便,通常要求分組密碼體制中使用的函數F是F2n上的低差分置換,其中n為偶數[2-3].顯然,APN置換是符合要求的最好的函數,但是當n為偶數時,只發現F26上存在APN置換[4].當n≥8且為偶數時,是否存在APN置換是相當困難的問題[5].于是,在實際的密碼體制的設計中,常常選擇4-差分置換或者6-差分置換作為設計組件, 例如歐洲加密標準就選擇了F28上的Inverse函數作為設計組件,而該函數是一個4-差分置換.然而,目前具有較好表達式的低差分置換函數類也非常少(可參考文獻[6]所列函數類),因此構造更多的低差分置換是一個有意義的課題.

2011年以前, 人們主要關注單項式函數的低差分置換, 到目前為止, 當n為偶數時, 只發現4類4-差分單項式[1,7-8]和兩類6-差分單項式[9].2011年以后, 由于許多二項式的APN函數被陸續發現, 通過修改APN函數的參數所滿足的條件結合有限域上方程解的討論的技巧是構造低差分置換的一個新途徑.2008年,文獻[10]構造了一類F23k上的APN二項式

F1(x)=x2s+1+α2k-1x22k+2k+s,

(1)

1 F2n上一類2t-差分置換(t≥1)

本節證明了F23k(k≥1)上一類二項式函數是一類差分均勻度為2t(t≥1)的置換.證明的方法參考了文獻[10]中將單個未知量的方程轉化為多個未知量方程組的思想.

定理1設s,k是兩個正整數且滿足(s,3k)=t.設

g1=(23k-1,2k+2s+1),

g2=(2k-1,2k+2s+1)，

(2)

F1(x)=x2s+1+α2k-1x22k+2k+s

是F23k上的差分均勻度為2t的置換, 其中,α是F23k的一個本原元.

證明 1)要證明F1的差分均勻度為2t,只需任取u,v∈F23k,v≠0, 證明方程

F1(x+v)+F1(x)=u

(3)

在F23k內解的個數≤2t.

注意到

(4)

則(4)是一個關于變元x的仿射函數, 從而若(3)有解, 則其解的個數與去掉常數項α2k-1v22k+2k+s+v2s+1后所得的線性方程的解的個數相同.另外, 注意到

(5)

在(4)中用vx代替x并在等式兩邊除以v2s+1, 所得的式子記為Va(x), 即

其中,a=(αv2k+2s+1)2k-1.經過上述變換后易知要證(3)在F23k內的解的個數≤2t只需證Va(x)=0在F23k內的解的個數≤2t.

令y=x2k,z=y2k,b=a2k,c=b2k,則方程Va(x)=0可以改寫成

a(z+y2s)+(x2s+x)=0.

(6)

下面說明a?F2:由于α是F23k的本原元及v≠0知a≠0.若a=1,即

(7)

注意到(7)式等號右邊的表達式是一個2k+2s+1次方元, 而α2k-1不是一個2k+2s+1次方元.這是因為若α2k-1是一個2k+2s+1次方元, 即存在整數l使得

下面考慮由(6)及其共軛方程構成的方程組:

目標是通過f1,f2,f3消去變元y,z得到一個只含有x的方程.由計算

R1=b(f1)2s+a2sf2=

a2sby22s+a2sy2s+a2sy+bx22s+bx2s+a2sbx

與

R2=a-1(b+1)-1(bf1+af2+abf3)=

(a2s(b+1)2s+(a+1)2sb)(b+1)-2sy2s+

a2sy+(a2sb2s+1+b)(b2s+1)-1x2s+a2sbx，

消去了z.為了消去y22s, 計算

R3=R1+a2sb(R2)2s=

(a2s(b+1)2s+(a+1)2sb)(b+1)-2sy2s+a2sy+

(a2sb2s+1+b)(b2s+1)-1x2s+a2sbx，

通過計算

R4=R3+(a2s(b+1)2s+

(a+1)2sb)(b+1)-2sR2=

P(a)(y+(b+1)x2s+bx),

其中,

(8)

并利用R2,R3可以消去y2s.通過計算

R5=(R4)2s+P(a)2sR2=

P(a)2s((a+1)(ab+a)-1y+(b2s+1)x22s+

(ab2s+1)a-1x2s+(ab+b)(ab+a)x),

可得

R6=(a+1)(ab+a)-1P(a)2s-1R4+R5=

P(a)2s(b+1)2s(x22s+x2s).

顯然, 若x是Va(x)=0的解,則x是R6=0的解.如果P(a)2s(b+1)2s≠0,則x滿足x22s+x2s=0.顯然x=0是上述方程的一個解,當x≠0時,x滿足x22s-2s=1.注意到

(22s-2s,23k-1)=2(s,3k)-1=2t-1,所以方程x22s-2s=1有2t-1個解,從而方程x22s+x2s=0有2t個解.因此方程(3)的解的個數不超過2t.

下面說明P(a)2s(b+1)2s≠0.因為a≠1,所以b=a2k≠1,即b+1≠0.下面說明P(a)≠0:一方面由a=(αv2k+2s+1)2k-1及前面說明a?F2的推導可知a不是一個2k+2s+1次方元(因為α2k-1不是一個2k+2s+1次方元); 另一方面, 若P(a)=0, 由a?F2可知

a=((a+1)(c+1)-1)2s+1c2s+1(b+1)(a+1)-1a=((a+1)(c+1)-1c)2k+2s+1,

即a是一個2k+2s+1次方元.這是一個矛盾.因此P(a)≠0.至此, 定理1的第1)部分的證明完成.

F1(x+v)+F1(x)=0

(9)

在F23k中無解.注意到F1(x+v)+F1(x)即為(4)式, 在(9)中用vx代替x并在等號兩邊除以v2s+1可得

a(x22k+x2k+s+1)+x2s+x+1=0,

(10)

其中,a=(αv2k+2s+1)2k-1.這樣,若x滿足(9)式, 則x滿足(10)式.由第1)部分的討論可知a?F2, 于是采用第1)部分求(6)的根的方法, 令y=x2k,z=y2k,b=a2k,c=b2k, 可得如下的方程組:

通過與1)類似的計算可得

P(a)2s(b+1)2s(x2s+x+1)=0,

其中,P(a)由(8)式給出.由1)的討論可知

P(a)2s(b+1)2s≠0,

從而x滿足

x2s+x+1=0.

(11)

將(11)式兩邊同時取2s次方并將x2s=x+1帶入可得

x22s+x=0,

從而

x∈F22s∩F23k=F2(2s,3k)=F2(s,3k)=

F2t=F2s∩F23k,

x2s+x+1=1≠0.

這與(11)式矛盾.這樣就證明了(9)無解, 即F1是一個置換.定理1證畢.

2 與已知結論的比較

由定理1可以導出一類APN置換和一類4-差分置換, 通過舉例說明這兩類函數都分別真包含已知的一類APN置換和一類4-差分置換.

在定理1中, 當正整數對s,t滿足條件(s,3k)=1時,則可得到F23k(k為奇數)上的一個APN置換, 即可得如下推論1.

推論1設s,k是兩個正整數且滿足(s,3k)=1, 其中k為奇數, 整數g1,g2由(2)式給出.若g1≠g2, 則函數F1(x)是F23k上的APN置換, 其中α是F23k的一個本原元.

若正整數s,k滿足sk≡2(mod 3)且(3,k)=1時, 可得如下推論2.

推論2[10]若正整數對s,k滿足(3,k)=(s,3k)=1,sk≡2(mod 3)且k為奇數, 則函數F1(x)是F23k上的APN置換.

證明一方面, 因為(3,k)=1, 所以2k-1不能被7整除, 從而g2不能被7整除, 于是(7,g2)=1.

另一方面, 因為(3,k)=(s,3k)=1,sk≡2(mod 3), 所以

或者

若s≡1(mod 3)且k≡2(mod 3), 則可設s=3s′+1,k=3k′+2.于是

2k+2s+1=23k′+2+23s′+1+1=

4(23k′-1)+2(23s′-1)+7.

注意到7|23k-1, 23k′-1, 23s′-1及g1=(23k-1,2k+2s+1), 有7|g1.

由上述兩方面的推理可知g1≠g2, 從而由推論1可知推論2結論成立.

注2通過計算機搜索發現當(s,k)∈{(1,21), (2,21), (29,21), (53,21), (55,21), (58,21), (59,21), (61,21), (62,21), (1,24), (5,24),…}時, (s,k)滿足推論1的條件, 顯然這些(s,k)不滿足推論2的條件, 這個事實表明推論1是推論2的推廣.

當(s,3k)=t=2時,可得到F23k上的一類4-差分函數,即有如下推論3.

注3通過計算機搜索可以發現當(s,k)∈{(4,18), (8,18), (10,18), (14,18), (16,18), (20,18), (22,18), (26,18), (32,18), (34,18),…}時, (s,k)滿足推論3的條件, 顯然這些(s,k)不滿足推論4的條件, 這個事實表明推論3是推論4的推廣.

當(s,3k)=t=3時,可得到F23k上的一類8-差分置換如下:

3 總結

本文構造了有限域F23k(k≥1)上的一類差分均勻度為2t(t≥1)的置換.讓t分別取1和2時, 得到一類APN置換和4-差分置換, 通過推理和舉例說明此兩類低差分置換分別真包含已知的兩類低差分置換.特別的, 由構造還得到了一類兩項式的8-差分置換.這些低差分置換將為分組密碼S-盒的設計提供更多選擇.

[1]NybergK.Differentiallyuniformmappingsforcryptogramphy[C]//AdvancesinCryptology-EUROCRYPT’93.LectureNotesinComputerScience, 1994, 765: 55-64.

[2]BihamE,ShamirA.DifferentialcryptanalysisofDES-likecryptosystems[J].JCryptol, 1991, 4(1): 3-72.

[3]MatsuiM.LinearcryptanalysismethodforDEScipher[C].LectureNotesinComputerScience, 1994, 765: 386-397.

[4]BrowningKA,DillonJ,McquistanMT,etal.AnAPNpermutationindimensionsix[J].ContemporaryMathematicsJournalofAmericanMathematicalSociety, 2010, 518(1):33-42.

[5]CarletC.VectorialBooleanFunctionsforCryptography[M].Oxford:CambridgeUniversityPress, 2010.

[6]CarletC.Onknownandnewdifferentiallyuniformfunctions[C].ACISP, 2011, 1-15.

[7]BrackenC,LeanderG.Ahighlynonlineardifferentially4uniformpowermappingthatpermutesfieldsofevendegree[J].FiniteFieldsAppl, 2010, 16(4):231-242.

[8]KasamiT.Weightenumeratorsforseveralclassesofthe2ndorderbinaryReed-Mullercodes[J].InformationandControl, 1971, 18(3):33-49.

[9]BlondeauC,CanteautA,CharpinP.Differentialpropertiesofx|→x2t-1[J]. IEEE Trans Infor Theory, 2011, 57(12):8127-8137.

[10] Budaghyan L, Carlet C, Leander G. Two classes of quadratic APN binomials in equivalent to power functions[J]. IEEE Trans Infor Theory, 2008, 54(9):4218-4229.

[11] Bracken C, Tan C H, Tan Y. Binomial differentially 4 uniform permutations with high nonlinearity[J]. Finite Fields and Their Applications, 2012, 18(3):537-546.

A class of 2t-difference uniform permutation polynomials

XIE Tao1,3, ZHU Xiaokun2, ZUO Kezheng3

(1.College of Mathematic and Statistic, Hubei University, Wuhan 430062;2.School of Mathematic and Statistic, Central China Normal University, Wuhan 430079;3.College of Mathematic and Statistic, Hubei Normal University, Huangshi, Hubei 435002)

By using the multivariate method solving system of equations over finite fieldsF23k(k≥1)， a class of permutation polynomials with 2t-difference uniformity was constructed, wheret≥1. A class of APN permutations and a class of 4-difference uniform permutations were obtained. Moreover， it is discovered that the two classes of low difference uniform permutations were generalizations of some known results．

difference uniformity; permutation polynomial; APN function

2014-09-29.

國家自然科學基金項目(70871050).

1000-1190(2015)03-0344-04

O157.4; TN918.3

A

*通訊聯系人. E-mail: zxk@mail.ccnu.edu.cn.