一類低差分均勻度冪函數的差分譜

夏永波，包福榮，彭麗娜

（中南民族大學 數學與統計學學院，武漢 430074）

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

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

1 基礎知識

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

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

其中|S|表示集合S的基數.令：

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

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

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

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

根據差分譜的定義，可以得到：

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

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

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

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

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

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

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

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

注2當λp，1=0且n為奇數時，λ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與之對應.因此：

2 主要結果及證明

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

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

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

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

同理有：

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

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

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

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

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

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

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

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

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

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

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

根據根與系數的關系可以得到：

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

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

同理可以得到：

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

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

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

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

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

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

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

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

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

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

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

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

3 結論