一类低差分均匀度幂函数的差分谱

夏永波，包福荣，彭丽娜

（中南民族大学 数学与统计学学院，武汉 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 结论