一類低差分均勻度冪函數(shù)的差分譜

夏永波，包福榮，彭麗娜

（中南民族大學 數(shù)學與統(tǒng)計學學院，武漢 430074）

S-盒在分組密碼中扮演著非常重要的角色.為了衡量S-盒抵抗差分攻擊的能力，1993 年Nyberg［1］在歐密會上提出了差分均勻度的概念.一個密碼函數(shù)的差分均勻度越低，其抵抗差分攻擊的能力就越強［2-3］.因此，尋找和構(gòu)造低差分均勻度的密碼函數(shù)成為近年來的研究熱點.目前研究者們找到了有限域上大量的低差分置換，如：Gold 函數(shù)［4］、Kasami 函數(shù)［5］、Inverse 函 數(shù)［1］、Bracken-Leander 函 數(shù)［6］和Bracken-Tan-Tan二項式函數(shù)［7］.其中，Inverse 函數(shù)由于具有較好的密碼學性質(zhì)，被用到了美國高級加密標準AES 的S-盒設(shè)計中.在研究密碼函數(shù)的差分性質(zhì)時，一個重要的課題就是計算密碼函數(shù)的差分譜，差分譜從取值頻次上對密碼函數(shù)的差分分布表進行刻畫，可以更精細地反映出密碼函數(shù)的差分性質(zhì).此外，差分譜在序列、編碼理論和組合設(shè)計中也扮演著非常重要的角色.因此，計算低差分一致性密碼函數(shù)的差分譜具有重要的理論意義與實際應(yīng)用價值.

設(shè)奇素數(shù)p、正整數(shù)n滿 足pn≡3 (mod 4)，Helleseth 和Sandberg 在文獻［8］中研究了有限域上的冪函數(shù)f(x)=的差分一致性，但他們并沒有計算出該函數(shù)的差分譜.閻昊德等以此為動機，在文獻［9］中首先計算方程組：的解的個數(shù)，然后利用文獻［10］中建立的此方程組的解數(shù)和差分譜之間的關(guān)系以及差分譜的兩個重要等式（見后文等式（1））確定了此函數(shù)的差分譜.本文通過直接研究函數(shù)f（x）的差分方程，給出了另外一種計算其差分譜的方法，這種方法比閻昊德等在文獻［9］中所使用的方法更為直接、簡便，并且給出了關(guān)于差分方程解數(shù)的更多信息.

1 基礎(chǔ)知識

設(shè)p為奇素數(shù)，n為正整數(shù)，表示具有pn個元素的有限域表示有限域去掉0 元素后得到的乘法群.

定義1［1］設(shè)f(x)是從有限域到自身的映射，對于任意的，定義函數(shù)f(x)的差分方程為Δaf(x)=f(x+a) -f(x)，δf(a，b) 表 示Δaf(x)=b在Fpn上解的個數(shù)，即：

其中|S|表示集合S的基數(shù).令：

則稱函數(shù)f(x)的差分均勻度為δ(f)或稱函數(shù)f(x)為δ(f)-差分一致性函數(shù).

若函數(shù)f(x)是從有限域到自身的冪映射，即f(x)=xd，對于任意的(a，b) ∈根據(jù)：

可知δf(a，b)=δf(1，b/ad)，也就是說冪函數(shù)f(x)的差分均勻度完全由δf(1，b)決定，其中b遍歷

定義2［11］設(shè)f(x)=xd是從有限域到自身的冪映射，且f(x)為k-差分一致性函數(shù)，則f(x)的差分譜定義為[ω0，ω1，...，ωk]，其中：

根據(jù)差分譜的定義，可以得到：

定義3稱函數(shù)χ(·)是有限域上的二次特征，如果χ(·)滿足：

注1當pn≡3 (mod 4)時，那么恒有χ(-1)=-1，即此時-1是有限域中的非平方元.

引理1［12］令p為奇素數(shù)，f(x)=a2x2+a1x+a0∈[x]，其中a2≠0.令d=a12-4a0a2，χ(·)是有限域上的二次特征，那么有：

令Np，n表示橢圓曲線有理點的個數(shù)，由文獻［13］，可以得到：

其中α和β是二次方程T2+λp，1T+p=0 的兩個復數(shù)解.本文主要考察以下兩個二次特征和：

以下用兩個例子來說明二次特征和（3）、（4）式的計算方法.

例1令p=7，那 么=2.二次方程T2+2T+7=0 有兩個復數(shù)解，因此由（2）式可以得到，即：

例2令p=11，那么=0.二次方程T2+11=0有兩個復數(shù)解由（2）式可以確定二次特征和的值，即：

注2當λp，1=0且n為奇數(shù)時，λp，n=0.

下面介紹后文中將會用到的兩個二次特征和等式.

引理2令pn≡3 (mod 4)，那么有：

與（1）類似，（2）的第1個等式顯然成立.下面證明（2）的第2個等式.由題意可知：

其中t=1 當且僅當x=-1，當t≠1 時，此方程是一個二次方程，它的判別式為Δ=16t2-16(1 -t).對于每個t≠1，此二次方程有(1+χ(Δ))個x與之對應(yīng).因此：

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

設(shè)奇素數(shù)p、正整數(shù)n滿足pn≡3 (mod 4)，f(x)=，Helleseth 和Sandberg 在文獻［8］中證明了如下結(jié)果：當pn=27 時函數(shù)f（x）的差分均勻度為1；當χ(5)=-1時，f（x）的差分均勻度為2；當χ(5)=1時，f（x）的差分均勻度為3.閻昊德等在文獻［9］中通過研究四變元方程組解的個數(shù)建立了差分譜所滿足的等式關(guān)系，從而確定了f（x）的差分譜.本節(jié)將直接研究f(x)=的差分方程，通過刻畫差分方程僅有兩個解的充要條件，給出一種不同于文獻［9］的方法來計算冪函數(shù)f（x）的差分譜.

在證明主要結(jié)果時，需要用到如下引理3.

引理3設(shè)奇素數(shù)p、正整數(shù)n滿足pn≡3 (mod 4)，那么Fpn{0，±1}中滿足條件：

證明由于pn≡3 (mod 4)，可知χ(-1)=-1，因此可以將條件（A）轉(zhuǎn)換成χ(b)=-1，χ(b-4)=-1，χ(b2+4)=1，條件（B）轉(zhuǎn)換成χ(b)=1，χ(b+4)=1，χ(b2+4)=1.令N1為滿足條件（A）的元素b的個數(shù)，N2為滿足條件（B）的元素b的個數(shù).通過引理的條件和引理1、引理2可以得到：

同理有：

基于前述結(jié)果可以確定冪函數(shù)f(x)=的差分譜，如定理1所示.

定理1設(shè)p為奇素數(shù)，pn≡3 (mod 4)，pn≠27，d=設(shè)f(x)=xd是定義在有限域上的冪函數(shù)，則當χ(5)=-1時函數(shù)f(x)的差分譜為：

當χ(5)=1時函數(shù)f(x)的差分譜為：

證明已知d為偶數(shù)，下面討論函數(shù)f(x)差分方程

解的個數(shù)，其中b∈首先考慮x?{-1，0}的情形，可以將上式化簡為：

等式兩邊同時乘上x(x+1)得到：

當b≠0 時，這是一個二次方程，其至多只有兩個解.由于x?{-1，0}，因此χ(x)和χ(x+1)都只有±1兩種取值.根據(jù)χ(x)和χ(x+1)的取值情況，將此二次方程分為4 種情況進行討論，如表1 所示.x∈{-1，0}和b=0的情況在后文進行討論.

表1 方程等式列表Tab.1 List of equations

由表1 可知情形I（resp.IV）至多只有一個所需解（所需解指的是該解首先是對應(yīng)情形二次方程的解，其次該解還需滿足對應(yīng)情形的χ(x)和χ(x+1)的取值），這是因為χ(x1x2)=-χ(x(x+1)).情形I 和IV 不會同時存在所需解，這是因為情形I 有所需解要求情形IV有所需解要求這兩種情況不可能同時成立，因為當pn≡3 (mod 4)時，χ(-1)=-1.因此這兩種情況至多只能提供一個所需解.

情形Ⅱ也至多只有一個所需解.假設(shè)x1和x2是情形Ⅱ所對應(yīng)方程的兩個解（注：這兩個解不一定是所需解），那么x1+1和x2+1是方程：

的兩個解，將上述方程簡化得到：

根據(jù)根與系數(shù)的關(guān)系可以得到：

故(x1，x1+1)和(x2，x2+1)至多只有一個滿足條件（χ(x)=1，χ(x+1))=(1，-1)，所以情形Ⅱ至多只有一個所需解.同理可以證明情形Ⅲ也至多只有一個所需解.

下面說明情形Ⅱ和Ⅲ不可能同時存在所需解.假設(shè)x1和x2是情形Ⅱ所對應(yīng)方程的兩個解，y1和y2是情形Ⅲ所對應(yīng)方程的兩個解（注：這些解不一定都是所需解），可驗證-(x1+1)和-(x2+1)是情形Ⅲ所對應(yīng)方程的兩個解.根據(jù)前面的分析可知情形Ⅱ和Ⅲ至多只有一個所需解，不妨設(shè)χ(x1)=1，χ(x1+1)=-1 和χ(y1)=-1，χ(y1+1)=1，則x1=-(y2+1)和x2=-(y1+1).由于和χ(-1)=-1，所以：

同理可以得到：

這就產(chǎn)生了矛盾.所以情形Ⅱ和Ⅲ不可能同時存在所需解.

綜上所述，當x?{-1，0}和b≠0時情形Ⅰ-Ⅳ至多只有兩個解.下面討論b=0 的情況.當b=0 時函數(shù)f(x)的差分方程為(x+1)d=xd，此方程至多有g(shù)cd(d，pn-1) -1=1個解.

當b=1 時，函數(shù)f（x）的差分方程在｛0，-1｝中有1個解；當b=-1時，函數(shù)f（x）的差分方程在｛0，-1｝中也有1 個解.下面根據(jù)表1 討論當b=±1 時，函數(shù)f（x）的差分方程在Fpn｛0，-1｝中解的情況.當b=±1 時，若χ(5)=-1，則情形Ⅱ和Ⅲ都沒有所需解，因為這兩種情形所對應(yīng)方程的判別式都是非平方元.此時對于情形Ⅰ和Ⅳ來說，這兩種情況也沒有所需解，這是因為當b=1 時，情形Ⅰ中的不滿足前提條件χ(x(x+1))=1，情形Ⅳ的判別式b2+4b=5 是一個非平方元.同理可以說明當b=-1時情形I和IV也沒有所需解.

若χ(5)=1，則情形Ⅰ-Ⅳ一共會提供兩個解.原因如下：不妨設(shè)b=1，那么對于情形I 來說，由于所以情形Ⅰ無所需解.對于情形IV 來說，由于方程判別式的值為5 是一個平方元以及所以情形Ⅳ有一個所需解.情形Ⅱ和Ⅲ也會提供一個所需解.這是因為當b=1時情形Ⅱ和Ⅲ的判別式都是一個平方元，假設(shè)x1和x2是情形Ⅲ所對應(yīng)方程的兩個解，由于不妨設(shè)χ(x1)=-1，χ(x2)=1.當χ(x1+1)=χ(x2+1)=1時，x1顯然是情形Ⅲ的一個所需解.否則根據(jù)χ(x1x2(x1+1)(x2+1))=-1，可 知χ(x1+1)=χ(x2+1)=-1，此時-(x2+1)是情形Ⅱ的一個所需解，這是因為χ(-(x2+1))=1，χ(-x2)=-1.

所以當b=1 時并且χ(5)=1，函數(shù)f(x)的差分方程有3個解.同理可以證明當b=-1時且χ(5)=1，函數(shù)f(x)的差分方程也有3個解.

由上述討論可知，如果f(x)的差分方程有兩個解，那么它們只可能來自情形Ⅰ-Ⅳ.下面給出情形Ⅰ-Ⅳ恰有兩個解的充要條件：

其中b∈{0，±1}.由χ(-b)=χ(b2-4b)=1，可知情形Ⅰ有一個所需解，這是因為情形I 所對應(yīng)方程的判別式為平方元，所以此方程在上有兩個解，又因為所以情形Ⅰ有一個所需解.由χ(-b)=χ(b2+4)=1 可知情形Ⅱ或Ⅲ有一個所需解，這是因為對于情形Ⅱ來說此時方程的判別式是一個平方元，又由于不妨設(shè)χ(x1)=1，χ(x2)=-1.當χ(x1+1)=χ(x2+1)=-1 時，x1顯然是情形Ⅱ的一個所需解，否則根據(jù)χ(x1x2(x1+1)(x2+1))=-1，可知χ(x1+1)=χ(x2+1)=1，此時-(x2+1)是情形Ⅲ的一個所需解，這是因為χ(-(x2+1))=-1，χ(-x2)=1.情形Ⅳ沒有所需解，因為χ(x(x+1))=-1.因此當b∈Fpn{0，±1}并且滿足條件（A）時，函數(shù)f(x) 的差分方程恰有兩個解.同理可以證明當b∈Fpn{0，±1}并且滿足條件（B）時，函數(shù)f(x)的差分方程也恰有兩個解.

由引理3 和等式（1），可以計算出f（x）的差分譜.對于滿足定理條件中的p和n，當χ(5)=-1 時，函數(shù)f(x)為APN函數(shù)并且其差分譜為：

當χ(5)=1 時，函數(shù)f(x)為3-差分一致性函數(shù)并且其差分譜為：

下面用Magma計算兩個例子來驗證定理1.

例3令p=7，n=3，此時χ(5)=-1.通過Magma計算得到F73上的冪函數(shù)f(x)=x170的差分譜為：

例4令p=11，n=3，此時χ(5)=1.通過Magma計算得到F113上的冪函數(shù)f(x)=x664的差分譜為：

3 結(jié)論