特征2域上的两类差分均匀度4的函数

王彦平，郑大彬，陈臻

( 1.西安翻译学院基础课部，陕西 西安 710105;2.湖北大学数学与统计学学院，湖北 武汉 430062)

特征2域上的两类差分均匀度4的函数

王彦平1，郑大彬2，陈臻2

( 1.西安翻译学院基础课部，陕西 西安 710105;2.湖北大学数学与统计学学院，湖北 武汉 430062)

构造特征2有限域上的两类差分均匀度4的函数，确定这两类函数的代数次数，并给出一些具体例子.

差分均匀度4；代数次数；特征2

0 引言及主要结果

设p是一个素数，GF(pn)是含有pn个元素的有限域，而GF*(pn)是有限域GF(pn)中除去零元素构成的乘法群.设f(x)∈GFp[x]，并把f看成是GF(pn)到GF(pn)的一个映射，定义

当Δf=δ时，则称f(x)是差分均匀度δ的函数.

特征2有限域上的差分均匀度4的函数是近年来密码学理论研究的一个热点.目前人们在这方面已取得很多好的成果[1-13]，而且构造密码学性质优良的差分均匀度4的函数引起了人们极大的兴趣.例如，域GF(2n)上单项式或二项式型的差分均匀度4的函数有Gold函数[1]，Kasami函数[2]，Inverse函数[3]，Bracken-Leander函数[4]和Bracken-Tan-Tan函数[5].通常直接构造全新的多项式型的差分均匀度4的函数很困难.于是，通过改造已知的单项式型的低差分均匀度函数来构造较高非线性度和代数次数的多项式型的低差分均匀度函数.像郑大彬[6]通过交换Gold函数任意两点之间的函数值，构造了一类具有较高非线性度和代数次数的差分均匀度4的函数.Yu Y Y等[7]通过交换Inverse函数两点处的函数值，给出了一类差分均匀度4的函数.屈龙江等[8]利用“switchig construction”方法分析已知的函数，构造了两类高非线性度，高代数次数的差分4置换函数.李永强等[9]给出一种利用有限域GF(22m+1)上的二次APN置换函数来构造GF(22m)上差分4置换函数的一般方法.肖理等[10]通过交换Kasami函数在两个点处的取值，得到了一类差分均匀度4的函数.查正邦等[11]通过改变Inverse函数在有限域的一个子域上的取值得到了具有较高非线性度和代数次数的两类差分均匀度4的函数.Tang D等[12]通过改变Inverse函数在有限域的一个任意子集上的函数值构造了一类高非线性度和高代数次数的差分均匀度4的函数.最近，谢涛等[13]沿用文献[12]中的方法构造了一类密码学性良好的差分均匀度4的函数.

沿用文献[11-13]中的思路，通过改变幂函数x2k+2在有限域GF(2n)的一个子域上的函数值，构造两类新的多项式型的差分均匀度4的函数.其主要结果如下：

定理1 设f(x)∈GF2[x]，f:GF(2n)|→GF(2n)，n=mk，m>2，k>1是正整数，且(m,k-1)=1，则

f(x)=(x2k+2+x3+x)(x+x2k)2n-1+x3+x

是差分均匀度4的函数，且代数次数deg(f)=k(m-1)+1.

定理2 设f(x)∈GF2[x]，f:GF(2n)|→GF(2n)，n=2k，k>2是偶数，且ε∈GF*(2k)，则

f(x)=(x2k+2+x3+ε)(x+x2k)2n-1+x3+ε

是差分均匀度4的函数，且代数次数deg(f)=k.

下文中给出一些预备知识并证明这两个结果.

1 预备知识

引理[6]设k是正整数，且满足gcd(n,k)=s.对于GF(2n)上的方程

αx2k+βx+γ=0,α,β,γ∈GF(2n),α≠0，

2 主要结果的证明

本节证明定理1和定理2，并给出相应的例子.

定理1的证明 欲证f(x)是差分均匀度4的函数，根据差分均匀度的定义，只要证明对任意的a,b∈GF(2n)且a≠0，方程

(1)

最多有4个解.

下面分4种情况讨论方程(1)的解个数.

i)x+a∈GF(2n)GF(2k)，x∈GF(2k)，则a2k≠a，x2k=x，且方程(1)可变成

(x+a)2k+2+x3+x=b

(2)

将x2k=x代入方程(2)可得

a2kx2+(a2+1)x+(a2k+2+b)=0

(3)

方程(3)除以a2k并在两边2k次幂，且将x2k=x代入，得

x2+(a2k+1-22k+a-22k)x+(a2k+1+b2ka-22k)=0

(4)

结合方程(3)与(4)式，得

(a2-2k+a2k+1-22k+a-2k+a-22k)x+(a2k+1+a2+ba-2k+b2ka-22k)=0，

该方程最多有一个解.即在此种情况中方程(1)最多有一个解.

ii)x+a∈GF(2k)，x∈GF(2n)GF(2k)，则a2k≠a，x2k=x+a+a2k，且方程(1)可变成

(x+a)3+(x+a)+x2k+2=b

(5)

将x2k=x+a+a2k代入方程(5)可得

a2kx2+(a2+1)x+(a3+a+b)=0

(6)

方程(6)除以a2k并在两边2k次幂，且将x2k=x+a+a2k代入，得

x2+(a2k+1-22k+a-22k)x+(a2k+1+a2+a2k+1-22k+1+a1-22k+b2ka-22k)=0

(7)

(a2-2k+a2k+1-22k+a-2k+a-22k)x+(a2k+1-22k+1+a1-22k+a3-2k+a1-2k+a2k+1+a2+ba-2k+b2ka-22k)=0，

该方程最多有一个解.即在此种情况中方程(1)最多有一个解.

iii)x+a∈GF(2k)，x∈GF(2k)，则a2k=a，x2k=x，且方程(1)可变成

(x+a)3+(x+a)+x3+x=b

(8)

因为x3+x是APN函数，所以该方程最多有两个解.

iv)x+a∈GF(2n)GF(2k)，x∈GF(2n)GF(2k)，且方程(1)可变成

(x+a)2k+2+x2k+2=b

(9)

方程(9)可化成

x2k+a2k-2x2+(a2k+ba-2)=0

(10)

令y=x2，则方程(10)可化为

y2k-1+a2k-2y+(a2k+ba-2)=0

(11)

因为(m,k-1)=1，所以gcd(mk,k-1)=1，于是根据引理，方程(11)最多有两个解.所以此种情况下方程(1)最多有两个解.

综上所述，若a∈GF(2n)GF(2k)，当b=a2k+2时，i) 中有x=0或a-2k+a2-2k两个解，这与i)中最多有一个解矛盾，所以i)中无解.ii)中有x=a或a+a-2k+a2-2k两个解，这与ii)中最多有一个解矛盾，所以ii)中也无解.iv)中有x=0，x=a两个解.所以方程(1)有x=0，x=a两个解.当b≠a2k+2时，i)，ii)中最多各有一个解，iv)中最多有两个解.所以方程(1)最多有4个解.

若a∈GF(2k)，当b=a3+a时，iii)中有x=0，a两个解，iv)中最多有两个解.所以方程(1)最多有4个解.当b≠a3+a时，iii)中最多有两个解，iv)中最多有两个解.所以方程(1)最多有4个解.

(*)

定理2的证明 欲证f(x)是差分均匀度4的函数，根据差分均匀度的定义，只要证明对任意的a,b∈GF(2n)且a≠0，方程

(12)

最多有4个解.

下面分4种情况讨论方程(12)的解个数.

i)x+a∈GF(2n)GF(2k)，x∈GF(2k)，则a2k≠a，x2k=x，且方程(12)可变成

(x+a)2k+2+x3+ε=b

(13)

将x2k=x代入方程(13)可得

a2kx2+a2x+(a2k+2+b+ε)=0

(14)

方程(14)除以a2k并在两边2k次幂，且将x2k=x代入，得

x2+a2k+1-1x+(a2k+1+b2ka-1+εa-1)=0

(15)

将方程(15)代入(14)，得

(a2k+1-1+a2-2k)x+(a2k+1+a2+ba-2k+b2ka-1+εa-2k+εa-1)=0，

ii)x+a∈GF(2k)，x∈GF(2n)GF(2k)，则a2k≠a，x2k=x+a+a2k，且方程(12)可变成

(x+a)3+ε+x2k+2=b

(16)

将x2k=x+a+a2k代入方程(16)可得

a2kx2+a2x+(a3+b+ε)=0

(17)

方程(17)除以a2k并在两边2k次幂，且将x2k=x+a+a2k代入，得

x2+a2k+1-1x+(a2+b2ka-1+εa-1)=0

(18)

将方程(18)代入(17)，得

(a2k+1-1+a2-2k)x+(a3-2k+a2+ba-2k+b2ka-1+εa-2k+εa-1)=0，

iii)x+a∈GF(2k)，x∈GF(2k)，则a2k=a，x2k=x，而且方程(12)可变成

(x+a)3+ε+x3+ε=b

(19)

将x2k=x代入方程(19)，得

x2+ax+a2+a-1b=0

(20)

因此方程(20)最多有两个解.

iv)x+a∈GF(2n)GF(2k)，x∈GF(2n)GF(2k)，则方程(12)可变成

(x+a)2k+2+x2k+2=b

(21)

方程(21)可化成

x2k+a2k-2x2+(a2k+ba-2)=0

(22)

令y=x2，则方程(22)可化为

y2k-1+a2k-2y+(a2k+ba-2)=0

(23)

因为k是偶数，所以gcd(2k,k-1)=1，根据引理，方程(23)最多有两个解.所以此种情况下方程(12)最多有两个解.

综上所述，若a∈GF(2n)GF(2k)，当b=a2k+2+ε时，(i)中有x=0或a2k+1-1两个解，这与i)中最多有一个解矛盾，所以i)中无解.ii)中有x=a或a2k+1-1+a两个解，这与ii)中最多有一个解矛盾，所以ii)中也无解.ivs)中最多有两个解.所以方程(12)有0，a与iv)中最多有两个解，即共有4个解.当b≠a2k+2+ε时，i)，ii)中最多各有一个解，iv)中最多有两个解.所以方程(12)最多有4个解.

若a∈GF(2k)，当b=a3时，iii)中有x=0，a两个解，iv)中最多有两个解.所以方程(12)最多有4个解.当b≠a3时，iii)中最多有两个解，iv)中最多有两个解.所以方程(12)最多有4个解.

(24)

下面给出利用数学软件MAGMA在小域上计算的具体例子.

例2.1 设m=3，k=5，在域GF(215)上，则

是差分均匀度4的函数，且代数次数deg(f)=11.

例2.2 设k=4，ε∈GF*(24)，在域GF(28)上，则

是差分均匀度4的函数，且代数次数deg(f)=4.

[1] Gold R. Maximal recursive sequences with 3-valued recursive cross-correlation functions[J].IEEE Transactions on Information Theory, 1968, 14(1): 154-156.

[2] Kasami T.The weight enumberators for several classes of subcodes of the second order binary Reed-Muller codes[J]. Information and Control, 1971, 18(4): 369-394.

[3] Nyberg K. Differentially uniform mappings for cryptography[C]. Advances in Cryptology-EUROCRYPT 93, Lecture Notes in Computer Science, Berlin: Springer-Verlag, 1994, 765:55-64.

[4] Bracken C, Leander G. A highly nonlinear differentially 4 uniform power mapping that permutes fields of even degree[J]. Finite Fields and Their Applications, 2010, 16(4): 231-242.

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

[6] Zheng D B.A class of differential 4 uniform functions from Gold functions[J].Instumentation, Measurement,Circuits and Systems, AISC, 2012, 127: 467-476.

[7] Yu Y Y, Wang M S, Li Y Q. Constructing differentially 4 uniform permutations from known ones[J]. Chinese Journal of Electronics, 2013, 22(3): 495-499.

[8] Qu L J, Tan Y,Tan C, et al. Constructing differentially 4-uniform permutations overGF(22k)via the switching method[J]. IEEE Transactions on Information Theory, 2013, 59(7): 4675-4686.

[9] Li Y Q, Wang M S. Constructing differentially 4-uniform permutations overGF(22m)from quadratic APN permutations overGF(22m+1)[J]. Designs, Codes and Cryptography, 2014, 72(2): 249-264.

[10] 肖理, 张习勇. 特征为2的有限域上的一类差分4一致函数[J]. 数学进展, 2013, 42(3): 1-8.

[11] Zha Z B, Hu L, Sun S W.Constructing new differentially 4-uniform permutations from the inverse function[J]. Finite Fields and Their Applications, 2014, 25: 64-78.

[12] Tang D, Carlet C, Tang X H. Differentially 4-uniform bijections by permuting the inverse function[J]. Designs, Codes and Cryptography, 2015, 77(1): 117-141.

[13] 谢涛, 陈媛, 曾祥勇.一类4-差分置换的构造[J].系统科学与数学, 2015, 35(10): 1194-1208.

[14] Lidl R, Niederreiter H. Finite fields[M].Cambridge, UK: Cambridge University Press, 1997.

(责任编辑 赵燕)

Two classes of differentially 4-uniform functions over finite fields of characteristic 2

WANG Yanping1, ZHENG Dabin2, CHEN Zhen2

(1.Department of Fundamental Courses, Xi’an Fanyi University, Xi’an 710105, China；2.Faculty of Mathematics and Statistics, Hubei University, Wuhan 430062, China)

We constructed two classes of differential 4-uniform functions over finite fields of characteristic 2, and determined their algebraic degree. Finally, some examples were provided.

differential 4-uniform; algebra degree; characteristic 2

2016-03-27

西安翻译学院重点科研项目(16A03)和湖北大学研究生教育教学改革项目(170-150034)资助

王彦平(1987-)，男，硕士，助教，E-mail：ypwang@aliyun.com

1000-2375(2017)01-0082-05

O157.4

A

10.3969/j.issn.1000-2375.2017.01.016