一类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.