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

謝 濤, 朱小琨, 左可正

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

?

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

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

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

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

差分均勻度; 置換多項式; APN函數(shù)

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

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

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

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

(1)

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

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

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

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內(nèi)解的個數(shù)≤2t.

注意到

(4)

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

(5)

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

其中,a=(αv2k+2s+1)2k-1.經(jīng)過上述變換后易知要證(3)在F23k內(nèi)的解的個數(shù)≤2t只需證Va(x)=0在F23k內(nèi)的解的個數(shù)≤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)式等號右邊的表達(dá)式是一個2k+2s+1次方元, 而α2k-1不是一個2k+2s+1次方元.這是因為若α2k-1是一個2k+2s+1次方元, 即存在整數(shù)l使得

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

目標(biāo)是通過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是上述方程的一個解,當(dāng)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)的解的個數(shù)不超過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的推導(dǎo)可知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 與已知結(jié)論的比較

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

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

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

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

推論2[10]若正整數(shù)對s,k滿足(3,k)=(s,3k)=1,sk≡2(mod 3)且k為奇數(shù), 則函數(shù)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), 則可設(shè)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結(jié)論成立.

注2通過計算機(jī)搜索發(fā)現(xiàn)當(dāng)(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的推廣.

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

注3通過計算機(jī)搜索可以發(fā)現(xiàn)當(dāng)(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的推廣.

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

3 總結(jié)

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

[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.

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

1000-1190(2015)03-0344-04

O157.4; TN918.3

A

*通訊聯(lián)系人. E-mail: zxk@mail.ccnu.edu.cn.