特征2域上的兩類差分均勻度4的函數(shù)

王彥平，鄭大彬，陳臻

( 1.西安翻譯學(xué)院基礎(chǔ)課部，陜西 西安 710105;2.湖北大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)學(xué)院，湖北 武漢 430062)

特征2域上的兩類差分均勻度4的函數(shù)

王彥平1，鄭大彬2，陳臻2

( 1.西安翻譯學(xué)院基礎(chǔ)課部，陜西 西安 710105;2.湖北大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)學(xué)院，湖北 武漢 430062)

構(gòu)造特征2有限域上的兩類差分均勻度4的函數(shù)，確定這兩類函數(shù)的代數(shù)次數(shù)，并給出一些具體例子.

差分均勻度4；代數(shù)次數(shù)；特征2

0 引言及主要結(jié)果

設(shè)p是一個素數(shù)，GF(pn)是含有pn個元素的有限域，而GF*(pn)是有限域GF(pn)中除去零元素構(gòu)成的乘法群.設(shè)f(x)∈GFp[x]，并把f看成是GF(pn)到GF(pn)的一個映射，定義

當Δf=δ時，則稱f(x)是差分均勻度δ的函數(shù).

特征2有限域上的差分均勻度4的函數(shù)是近年來密碼學(xué)理論研究的一個熱點.目前人們在這方面已取得很多好的成果[1-13]，而且構(gòu)造密碼學(xué)性質(zhì)優(yōu)良的差分均勻度4的函數(shù)引起了人們極大的興趣.例如，域GF(2n)上單項式或二項式型的差分均勻度4的函數(shù)有Gold函數(shù)[1]，Kasami函數(shù)[2]，Inverse函數(shù)[3]，Bracken-Leander函數(shù)[4]和Bracken-Tan-Tan函數(shù)[5].通常直接構(gòu)造全新的多項式型的差分均勻度4的函數(shù)很困難.于是，通過改造已知的單項式型的低差分均勻度函數(shù)來構(gòu)造較高非線性度和代數(shù)次數(shù)的多項式型的低差分均勻度函數(shù).像鄭大彬[6]通過交換Gold函數(shù)任意兩點之間的函數(shù)值，構(gòu)造了一類具有較高非線性度和代數(shù)次數(shù)的差分均勻度4的函數(shù).Yu Y Y等[7]通過交換Inverse函數(shù)兩點處的函數(shù)值，給出了一類差分均勻度4的函數(shù).屈龍江等[8]利用“switchig construction”方法分析已知的函數(shù)，構(gòu)造了兩類高非線性度，高代數(shù)次數(shù)的差分4置換函數(shù).李永強等[9]給出一種利用有限域GF(22m+1)上的二次APN置換函數(shù)來構(gòu)造GF(22m)上差分4置換函數(shù)的一般方法.肖理等[10]通過交換Kasami函數(shù)在兩個點處的取值，得到了一類差分均勻度4的函數(shù).查正邦等[11]通過改變Inverse函數(shù)在有限域的一個子域上的取值得到了具有較高非線性度和代數(shù)次數(shù)的兩類差分均勻度4的函數(shù).Tang D等[12]通過改變Inverse函數(shù)在有限域的一個任意子集上的函數(shù)值構(gòu)造了一類高非線性度和高代數(shù)次數(shù)的差分均勻度4的函數(shù).最近，謝濤等[13]沿用文獻[12]中的方法構(gòu)造了一類密碼學(xué)性良好的差分均勻度4的函數(shù).

沿用文獻[11-13]中的思路，通過改變冪函數(shù)x2k+2在有限域GF(2n)的一個子域上的函數(shù)值，構(gòu)造兩類新的多項式型的差分均勻度4的函數(shù).其主要結(jié)果如下：

定理1 設(shè)f(x)∈GF2[x]，f:GF(2n)|→GF(2n)，n=mk，m>2，k>1是正整數(shù)，且(m,k-1)=1，則

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

是差分均勻度4的函數(shù)，且代數(shù)次數(shù)deg(f)=k(m-1)+1.

定理2 設(shè)f(x)∈GF2[x]，f:GF(2n)|→GF(2n)，n=2k，k>2是偶數(shù)，且ε∈GF*(2k)，則

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

是差分均勻度4的函數(shù)，且代數(shù)次數(shù)deg(f)=k.

下文中給出一些預(yù)備知識并證明這兩個結(jié)果.

1 預(yù)備知識

引理[6]設(shè)k是正整數(shù)，且滿足gcd(n,k)=s.對于GF(2n)上的方程

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

2 主要結(jié)果的證明

本節(jié)證明定理1和定理2，并給出相應(yīng)的例子.

定理1的證明 欲證f(x)是差分均勻度4的函數(shù)，根據(jù)差分均勻度的定義，只要證明對任意的a,b∈GF(2n)且a≠0，方程

(1)

最多有4個解.

下面分4種情況討論方程(1)的解個數(shù).

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)

結(jié)合方程(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函數(shù)，所以該方程最多有兩個解.

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，于是根據(jù)引理，方程(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的函數(shù)，根據(jù)差分均勻度的定義，只要證明對任意的a,b∈GF(2n)且a≠0，方程

(12)

最多有4個解.

下面分4種情況討論方程(12)的解個數(shù).

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是偶數(shù)，所以gcd(2k,k-1)=1，根據(jù)引理，方程(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)

下面給出利用數(shù)學(xué)軟件MAGMA在小域上計算的具體例子.

例2.1 設(shè)m=3，k=5，在域GF(215)上，則

是差分均勻度4的函數(shù)，且代數(shù)次數(shù)deg(f)=11.

例2.2 設(shè)k=4，ε∈GF*(24)，在域GF(28)上，則

是差分均勻度4的函數(shù)，且代數(shù)次數(shù)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] 肖理, 張習(xí)勇. 特征為2的有限域上的一類差分4一致函數(shù)[J]. 數(shù)學(xué)進展, 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-差分置換的構(gòu)造[J].系統(tǒng)科學(xué)與數(shù)學(xué), 2015, 35(10): 1194-1208.

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

(責(zé)任編輯 趙燕)

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

西安翻譯學(xué)院重點科研項目(16A03)和湖北大學(xué)研究生教育教學(xué)改革項目(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