有限域{\mathrm{F}}_{{\mathrm{2}}^n}上两类三项式的密码学性质

Cryptographic properties of two classes of trinomials over finite field {\mathbf{F}}_{{\mathrm{2}}^n}

摘要

刻画了有限域{\mathrm{F}}_{{\mathrm{2}}^n}上两类三项式的差分谱，第一类是f(x)=x+x^{{\mathrm{2}}^{m+\mathrm{1}}-\mathrm{1}}+x^{{\mathrm{2}}^n-{\mathrm{2}}^{m+\mathrm{1}}+\mathrm{1}}，其中n=\mathrm{2}m+\mathrm{1}；第二类是g(x)=x^{{\mathrm{2}}^{\mathrm{2}k}+{\mathrm{2}}^k}+x^{{\mathrm{2}}^{\mathrm{2}k}+\mathrm{1}}+x^{{\mathrm{2}}^k+\mathrm{1}}，其中\mathrm{g}\mathrm{c}\mathrm{d}(n,k)=\mathrm{1}. 对于第一类三项式采用的方法是通过计算f(x)的Walsh谱，再根据差分谱和Walsh谱之间的关系来确定它的差分谱；对于第二类则是直接通过研究g\left(x\right)的差分方程有确定解数的条件，从而计算出差分谱，此外根据二次型理论，还确定了它的Walsh谱.

Abstract

The differential spectra of two classes of trinomials over finite field {\mathrm{F}}_{{\mathrm{2}}^n} are described. The first class is f(x)=x+x^{{\mathrm{2}}^{m+\mathrm{1}}-\mathrm{1}}+x^{{\mathrm{2}}^n-{\mathrm{2}}^{m+\mathrm{1}}+\mathrm{1}}with n=\mathrm{2}m+\mathrm{1}， and the second one is g(x)=x^{{\mathrm{2}}^{\mathrm{2}k}+{\mathrm{2}}^k}+x^{{\mathrm{2}}^{\mathrm{2}k}+\mathrm{1}}+x^{{\mathrm{2}}^k+\mathrm{1}}， where \mathrm{g}\mathrm{c}\mathrm{d}(n,k)=\mathrm{1}. For the first class， the differential spectrum is determined by calculating the Walsh spectrum of f(x). For the second one， the differential spectrum is calculated directly by determining the conditions for which the differential equation has specific number of solutions. Moreover， the Walsh spectrum of g(x) is also determined based on the theory of quadratic forms.

关键词

有限域 / 差分均匀度 / 差分谱 / Walsh谱

Key words

finite field / differential uniformity / differential spectrum / Walsh spectrum

分组密码作为密码学中的一种对称加密体制，由于其具有速度快、易于标准化和便于软硬件实现等特点，一直受到广泛的关注和使用. S-盒是分组密码中唯一的非线性部分在分组密码算法中扮演着重要的角色，为了衡量S-盒抵抗差分攻击^［1］的能力，Nyberg于1993年在欧密会上提出了差分均匀度的概念^［2］. 一个密码函数的差分均匀度越低，它抵抗差分攻击的能力便越强. 与密码函数的差分均匀度相关联的另外一种重要性质是该函数的差分谱，它能够更精细地刻画密码函数的差分性质，为寻找差分攻击路径提供依据，此外差分谱也在编码理论、序列和组合设计中起着重要作用.

当前对具有低差分均匀度密码函数的研究中，主要的对象是幂函数以及形式较好的二项式或三项式，美国高级加密标准AES算法S-盒的设计采用的是有限域{\mathrm{F}}_{{\mathrm{2}}^{\mathrm{8}}}上差分均匀度为4的逆函数x^{-\mathrm{1}}，研究相关类型的函数有着重要的理论意义与现实价值.目前对该类型函数的研究，可以在文献［3-10］中找到相关的结论.

本文研究了两类三项式的差分谱和Walsh谱，其中第一类是由丁存生、屈龙江以及王强等构造的{\mathrm{F}}_{{\mathrm{2}}^n}上的置换三项式f(x)=x+x^{{\mathrm{2}}^{m+\mathrm{1}}-\mathrm{1}}+x^{{\mathrm{2}}^n-{\mathrm{2}}^{m+\mathrm{1}}+\mathrm{1}}，其中m是任意正整数，n=\mathrm{2}m+\mathrm{1}^［4］；第二类是由查正邦在文献［11］中提出的{\mathrm{F}}_{{\mathrm{2}}^n}上的几乎低差分一致性函数g(x)=x^{{\mathrm{2}}^{\mathrm{2}k}+{\mathrm{2}}^k}+x^{{\mathrm{2}}^{\mathrm{2}k}+\mathrm{1}}+x^{{\mathrm{2}}^k+\mathrm{1}}，其中\mathrm{g}\mathrm{c}\mathrm{d}(n,k)=\mathrm{1}. 对于第一类三项式，本文首先计算了其Walsh谱，再根据Walsh谱与差分谱的关系，间接计算出了它的差分谱；对于第二类三项式，则是直接从差分方程出发，通过分析差分方程有特定解数的条件，计算出了它的差分谱. 此外，利用二次型理论，确定了第二类三项式的Walsh谱.

1 基本定义

设{\mathrm{F}}_{p^n}表示元素个数为p^n的有限域，其中p是素数，n是正整数，并设{\mathrm{F}}_{p^n}^{\mathrm{*}}={\mathrm{F}}_{p^n}\backslash \left\{\mathrm{0}\right\}.

定义1^［2，12］ 令f\left(x\right)是从{\mathrm{F}}_{p^n}到自身的映射，\forall \left(a,b\right)\in {\mathrm{F}}_{p^n}^{\mathrm{*}}\times {\mathrm{F}}_{p^n}，定义差分方程D_{a}f(x)=f(x+a)-f(x)=b. 设{\delta }_f(a,b)表示差分方程D_{a}f(x)=b在{\mathrm{F}}_{p^n}中解的个数，即：

{\delta }_f\left(a,b\right)=\left|\left\{x\in {\mathrm{F}}_{p^n}\left|f\left(x+a\right)\right.-f\left(x\right)=b,\left(a,b\right)\in {\mathrm{F}}_{p^n}^{\mathrm{*}}\times {\mathrm{F}}_{p^n}\right\}\right|，

这里|S|表示集合S的基数. f\left(x\right)的差分均匀度定义为：

{\delta }_f=\mathrm{m}\mathrm{a}\mathrm{x}\left\{{\delta }_f\left(a,b\right)\left|a\in {\mathrm{F}}_{p^n}^{\mathrm{*}},b\in {\mathrm{F}}_{p^n}\right.\right\}.

若{\delta }_f=k，则称f\left(x\right)为k差分一致性函数. 此外，若除了某一个a值外都有{\delta }_f(a,b)\le \mathrm{4}，则称函数f(x)为几乎低差分一致函数，此时大于\mathrm{4}的{\delta }_f(a,b)值称为偏差（Deviation）.

当f\left(x\right)被用于构造分组密码的S-盒时，f\left(x\right)的差分均匀度越小，其抵抗差分攻击的能力越强. 当{\delta }_f=\mathrm{1}时，函数f\left(x\right)称为完全非线性（Perfect Nonlinear）函数，简称PN函数，此时f\left(x\right)抵抗差分攻击的能力最强. 当{\delta }_f=\mathrm{2}时，函数f\left(x\right)称为几乎完全非线性（Almost Perfect Nonlinear）函数，简称APN函数. 注意到当p=\mathrm{2}时，{\delta }_f的最小值是2，这是因为\forall a\in {\mathrm{F}}_{{\mathrm{2}}^n}^{\mathrm{*}}，有f\left(x+a\right)+f\left(x\right)=f\left(\left(x+a\right)+a\right)+f\left(x+a\right)，即差分方程D_{a}f(x)=b的解总是成对出现，所以特征为2的有限域上不存在PN函数.

定义2^［2］ 设f\left(x\right)是从有限域{\mathrm{F}}_{p^n}到自身的映射，若{\delta }_f=k，则定义多重集\left\{{\omega }_{\mathrm{0}},{\omega }_{\mathrm{1}},...,{\omega }_k\right\}为f\left(x\right)的差分谱，其中：

{\omega }_i=\left|\left\{a\in {\mathrm{F}}_{p^n}^{\mathrm{*}},b\in {\mathrm{F}}_{p^n}:{\delta }_f\left(a,b\right)=i\right\}\right|,\mathrm{0}\le i\le k.

根据差分谱的定义，可以得到如下等式成立：

{\displaystyle \sum _{i=\mathrm{0}}^k}{\omega }_i={\displaystyle \sum _{i=\mathrm{0}}^k}i{\omega }_i=p^n(p^n-\mathrm{1}).

令\mathrm{T}{\mathrm{r}}_{\mathrm{1}}^n(\cdot )表示从{\mathrm{F}}_{p^n}到{\mathrm{F}}_p的迹函数，即\mathrm{T}{\mathrm{r}}_{\mathrm{1}}^n(x)=x+x^p+x^{p^{\mathrm{2}}}+\cdot \cdot \cdot +x^{p^{n-\mathrm{1}}}，下面给出Walsh变换的定义.

定义3^［13］ 设f(x)是从{\mathrm{F}}_{p^n}到{\mathrm{F}}_{p^n}的映射，\forall \left(a,b\right)\in {\mathrm{F}}_{p^n}\times {\mathrm{F}}_{p^n}，f(x)在\left(a,b\right)处的Walsh变换定义为：

W_f(a,b)=\sum _{x\in {\mathrm{F}}_{p^n}}{\omega }^{\mathrm{T}{\mathrm{r}}_{\mathrm{1}}^n(af(x)+bx)}，

其中\omega ={\mathrm{e}}^{\frac{\mathrm{2}\mathrm{\pi }\sqrt[]{-\mathrm{1}}}{p}}是p次单位根. f(x)的Walsh谱定义为如下多重集：

\left\{W_f\left(a,b\right):a\in {\mathrm{F}}_{p^n}^{\mathrm{*}},b\in {\mathrm{F}}_{p^n}\right\}.

注1 当f(x)是从{\mathrm{F}}_{{\mathrm{2}}^n}到{\mathrm{F}}_{\mathrm{2}}的布尔函数时，其Walsh变换定义为：

\widehat{f}(x)=\sum _{x\in {\mathrm{F}}_{{\mathrm{2}}^n}}{(-\mathrm{1})}^{f(x)+\mathrm{T}{\mathrm{r}}_{\mathrm{1}}^n(\lambda x)},\lambda \in {\mathrm{F}}_{{\mathrm{2}}^n}.

当f(x)=x^d是有限域{\mathrm{F}}_{p^n}上的幂函数，且\mathrm{g}\mathrm{c}\mathrm{d}(d,p^n-\mathrm{1})=\mathrm{1}，那么\forall \left(a,b\right)\in {\mathrm{F}}_{p^n}^{\mathrm{*}}\times {\mathrm{F}}_{p^n}，不妨设c^d=a，则有：

W_f(a,b)=\sum _{x\in {\mathrm{F}}_{p^n}}{\omega }^{\mathrm{T}{\mathrm{r}}_{\mathrm{1}}^n(a{x}^d+bx)}\begin{array}{c}\underline{\underline{y=cx}}\\ \end{array}\sum _{y\in {\mathrm{F}}_{p^n}}{\omega }^{\mathrm{T}{\mathrm{r}}_{\mathrm{1}}^n({(y)}^d+\frac{by}{c})}=W_f(\mathrm{1},\frac{b}{c}).

由于x^d是置换，则c和a是一一对应的. 故f(x)的Walsh谱值完全由W_f(\mathrm{1},b)确定，其中b遍历{\mathrm{F}}_{p^n}，所以可以定义这类幂函数的Walsh谱为如下多重集：

\left\{W_f\left(\mathrm{1},b\right):b\in {\mathrm{F}}_{p^n}\right\}.

定义4^［14］ 设p(x)是从{\mathrm{F}}_{{\mathrm{2}}^n}到{\mathrm{F}}_{{\mathrm{2}}^n}的映射，且p(x)=\sum _{i,j}{a}_{ij}{x}^{{\mathrm{2}}^i+{\mathrm{2}}^j},其中a_{ij}\in {\mathrm{F}}_{{\mathrm{2}}^n}，，则称p(x)是{\mathrm{F}}_{{\mathrm{2}}^n}上的二次函数. \forall \lambda \in {\mathrm{F}}_{{\mathrm{2}}^n}^{\mathrm{*}}，称Q_{\lambda }(x)=\mathrm{T}{\mathrm{r}}_{\mathrm{1}}^n(\lambda p(x))是{\mathrm{F}}_{{\mathrm{2}}^n}到{\mathrm{F}}_{\mathrm{2}}的二次型.

令V(Q_{\lambda })=\{x\in {\mathrm{F}}_{{\mathrm{2}}^n}|Q_{\lambda }(x+z)+Q_{\lambda }(x)+Q_{\lambda }(z)=\mathrm{0},\forall z\in {\mathrm{F}}_{{\mathrm{2}}^n}\}，显然V(Q_{\lambda })是在{\mathrm{F}}_{{\mathrm{2}}^n}上的向量空间，不妨记j=\mathrm{d}\mathrm{i}{\mathrm{m}}_{{\mathrm{F}}_{\mathrm{2}}}(V(Q_{\lambda }))，则二次型Q_{\lambda }(x)的秩为\mathrm{R}\mathrm{a}\mathrm{n}\mathrm{k}(Q_{\lambda })=n-j.

注2 根据Q_{\lambda }(x)的定义，显然有如下等式成立：

\begin{array}{l}{(\sum _{x\in {\mathrm{F}}_{{\mathrm{2}}^n}}{(-\mathrm{1})}^{Q_{\lambda }(x)})}^{\mathrm{2}}=\sum _{x\in {\mathrm{F}}_{{\mathrm{2}}^n}}{(-\mathrm{1})}^{Q_{\lambda }(x)}\cdot \\ \sum _{z\in {\mathrm{F}}_{{\mathrm{2}}^n}}{(-\mathrm{1})}^{Q_{\lambda }(x+z)+Q_{\lambda }(x)+Q_{\lambda }(z)}={\mathrm{2}}^n\sum _{x\in V(Q_{\lambda })}{(-\mathrm{1})}^{Q_{\lambda }(x)}.\end{array}

因为Q_{\lambda }(x)是V(Q_{\lambda })上的线性函数，所以有：

\sum _{x\in F_{{\mathrm{2}}^n}}{(-\mathrm{1})}^{Q_{\lambda }(x)}=\left\{\begin{array}{l}\pm {\mathrm{2}}^{n-\frac{\mathrm{R}\mathrm{a}\mathrm{n}\mathrm{k}(Q_{\lambda })}{\mathrm{2}}},\mathrm{若对}\mathrm{于任}\mathrm{意的}x\in V(Q_{\lambda }),\mathrm{有}{Q}_{\lambda }(x)=\mathrm{0},\\ \mathrm{0},\mathrm{其他},\end{array}\right.

故Q_{\lambda }(x)的秩总是一个偶数\mathrm{2}h，且满足\mathrm{2}\le \mathrm{2}h\le n.

2 预备知识

引理1^［3-4］ 设m是任意正整数，n=\mathrm{2}m+\mathrm{1}，那么三项式

f(x)=x+x^{{\mathrm{2}}^{m+\mathrm{1}}-\mathrm{1}}+x^{{\mathrm{2}}^n-{\mathrm{2}}^{m+\mathrm{1}}+\mathrm{1}}，

是{\mathrm{F}}_{{\mathrm{2}}^n}上的置换三项式，并且f(x)是4差分一致函数.

对于定义在有限域{\mathrm{F}}_{p^n}上的幂函数f\left(x\right)=x^d，其中d是任意正整数，文献［15］揭示了f(x)的Walsh谱和差分谱之间的关系. 实际上，对于一般的函数同样有类似的结果，文献［14］在计算Welch置换三项式的差分谱时，便给出了如下相关的结论.

引理2^［14］ 令f(x)是{\mathrm{F}}_{p^n}到{\mathrm{F}}_{p^n}的k差分一致函数，其中p是任意素数，\left\{{\omega }_{\mathrm{1}},{\omega }_{\mathrm{2}},...,{\omega }_k\right\}为其差分谱，W_f(a,b)是f(x)在\left(a,b\right)\in {\mathrm{F}}_{p^n}\times {\mathrm{F}}_{p^n}处的Walsh变换，则有如下等式成立：

{\sum _{a,b\in {\mathrm{F}}_{p^n}}\left|W_f(a,b)\right|}^{\mathrm{4}}=p^{\mathrm{4}n}+p^{\mathrm{2}n}{\displaystyle \sum _{i=\mathrm{0}}^k}{i}^{\mathrm{2}}{\omega }_i.

引理3^［16］ 令q(x)=x^{{\mathrm{2}}^{m+\mathrm{1}}+\mathrm{1}}是定义在有限域{\mathrm{F}}_{{\mathrm{2}}^n}上的一类幂函数，其中n=\mathrm{2}m+\mathrm{1}，那么q(x)的Walsh变换W_q(\mathrm{1},b)的取值分布如下：

W_q(\mathrm{1},b)=\left\{\begin{array}{l}{\mathrm{2}}^{\frac{n+\mathrm{1}}{\mathrm{2}}},{\mathrm{2}}^{n-\mathrm{2}}+{\mathrm{2}}^{\frac{n-\mathrm{3}}{\mathrm{2}}}\mathrm{次},\\ -{\mathrm{2}}^{\frac{n+\mathrm{1}}{\mathrm{2}}},{\mathrm{2}}^{n-\mathrm{2}}-{\mathrm{2}}^{\frac{n-\mathrm{3}}{\mathrm{2}}}\mathrm{次},\\ \\ \mathrm{0},{\mathrm{2}}^{n-\mathrm{1}}\mathrm{次},\end{array}\right.

特别地，\forall b\in {\mathrm{F}}_{{\mathrm{2}}^n}，W_q(\mathrm{1},b)=\mathrm{0}当且仅当\mathrm{T}{\mathrm{r}}_{\mathrm{1}}^n(b)=\mathrm{0}.

引理4^［14］ 设正整数n,t,l满足\mathrm{g}\mathrm{c}\mathrm{d}(n,t)=\mathrm{1}且\mathrm{2}l\le n.令Q(x)={\displaystyle \sum _{i=\mathrm{1}}^l}T{r}_{\mathrm{1}}^n(c_i{x}^{{\mathrm{2}}^{ti}+\mathrm{1}})，其中c_i\in {\mathrm{F}}_{{\mathrm{2}}^n}且至少存在一个c_i非零(\mathrm{1}\le i\le l)，则Q(x)的秩\mathrm{2}h满足n-\mathrm{2}l\le \mathrm{2}h\le n.

引理5^［17］ 设Q(x)是{\mathrm{F}}_{{\mathrm{2}}^n}到{\mathrm{F}}_{\mathrm{2}}的秩为\mathrm{2}h的二次型，则它的Walsh变换有如下分布：

\widehat{Q}(\lambda )=\left\{\begin{array}{l}\pm {\mathrm{2}}^{n-h},{\mathrm{2}}^{\mathrm{2}h-\mathrm{1}}\pm {\mathrm{2}}^{h-\mathrm{1}},\\ \mathrm{0},{\mathrm{2}}^n-{\mathrm{2}}^{\mathrm{2}h}.\end{array}\right.

3 主要结果及证明

定理1 设f(x)=x+x^{{\mathrm{2}}^{m+\mathrm{1}}-\mathrm{1}}+x^{{\mathrm{2}}^n-{\mathrm{2}}^{m+\mathrm{1}}+\mathrm{1}}是有限域{\mathrm{F}}_{{\mathrm{2}}^n}上的置换三项式，其中n=\mathrm{2}m+\mathrm{1}，那么f(x)的Walsh谱由表1给出.

证明 设(a,b)\in {\mathrm{F}}_{{\mathrm{2}}^n}^{\mathrm{*}}\times {\mathrm{F}}_{{\mathrm{2}}^n}，根据Walsh变换的定义，有：

W_f(a,b)=\sum _{x\in {\mathrm{F}}_{{\mathrm{2}}^n}}{(-\mathrm{1})}^{\mathrm{T}{\mathrm{r}}_{\mathrm{1}}^n(af(x)+bx)}=\sum _{x\in {\mathrm{F}}_{{\mathrm{2}}^n}}{(-\mathrm{1})}^{\mathrm{T}{\mathrm{r}}_{\mathrm{1}}^n(a{x}^{{\mathrm{2}}^{m+\mathrm{1}}-\mathrm{1}}+a{x}^{\mathrm{2}-{\mathrm{2}}^{m+\mathrm{1}}}+(a+b)x)}=\sum _{x\in {\mathrm{F}}_{{\mathrm{2}}^n}}{(-\mathrm{1})}^{\mathrm{T}{\mathrm{r}}_{\mathrm{1}}^n((a^{{\mathrm{2}}^m}+a)x^{{\mathrm{2}}^{m+\mathrm{1}}-\mathrm{1}}+(a+b)x)}.

令q\left(x\right)=x^{{\mathrm{2}}^{m+\mathrm{1}}+\mathrm{1}}，由于\mathrm{g}\mathrm{c}\mathrm{d}({\mathrm{2}}^{m+\mathrm{1}}+\mathrm{1},{\mathrm{2}}^n-\mathrm{1})=\mathrm{1}，不妨设x=y^{{\mathrm{2}}^{m+\mathrm{1}}+\mathrm{1}}，则：

\begin{array}{c}{W}_f(a,b)=\sum _{y^{{\mathrm{2}}^{m+\mathrm{1}}+\mathrm{1}}\in {\mathrm{F}}_{{\mathrm{2}}^n}}{(-\mathrm{1})}^{\mathrm{T}{\mathrm{r}}_{\mathrm{1}}^n((a^{{\mathrm{2}}^m}+a)y+(a+b)y^{{\mathrm{2}}^{m+\mathrm{1}}+\mathrm{1}})}=\\ \sum _{y\in F_{{\mathrm{2}}^n}}{(-\mathrm{1})}^{T{r}_{\mathrm{1}}^n((a^{{\mathrm{2}}^m}+a)y+(a+b)y^{{\mathrm{2}}^{m+\mathrm{1}}+\mathrm{1}})}=W_q(a+b,a^{{\mathrm{2}}^m}+a).\end{array}

再令a+b=c，则W_q(a+b,a^{{\mathrm{2}}^m}+a)=W_q(c,{(b+c)}^{{\mathrm{2}}^m}+(b+c))，其中b遍历{\mathrm{F}}_{{\mathrm{2}}^n}. 给定b，因为a\ne \mathrm{0}，所以c\ne b. 注意到当c=b，有：

\begin{array}{c}{W}_q(c,{(b+c)}^{{\mathrm{2}}^m}+(b+c))=W_q(c,\mathrm{0})=\\ \sum _{x\in {\mathrm{F}}_{{\mathrm{2}}^n}}{(-\mathrm{1})}^{\mathrm{T}{\mathrm{r}}_{\mathrm{1}}^n(c{x}^{{\mathrm{2}}^{m+\mathrm{1}}+\mathrm{1}})}=\left\{\begin{array}{l}{\mathrm{2}}^n,c=\mathrm{0},\\ \mathrm{0},c\ne \mathrm{0}.\end{array}\right.\end{array}(\mathrm{1})

为了方便计算，下面先确定当(b,c)遍历{\mathrm{F}}_{{\mathrm{2}}^n}\times {\mathrm{F}}_{{\mathrm{2}}^n}时，W_q(c,{(b+c)}^{{\mathrm{2}}^m}+(b+c))的取值分布情况.

当c=\mathrm{0}时，W_q(c,{(b+c)}^{{\mathrm{2}}^m}+(b+c))=\sum _{x\in {\mathrm{F}}_{{\mathrm{2}}^n}}{(-\mathrm{1})}^{\mathrm{T}{\mathrm{r}}_{\mathrm{1}}^n((b^{{\mathrm{2}}^m}+b)x)}，所以：

W_q(\mathrm{0},b^{{\mathrm{2}}^m}+b)=\left\{\begin{array}{l}{\mathrm{2}}^n,b\in {\mathrm{F}}_{\mathrm{2}},\\ \mathrm{0},b\notin {\mathrm{F}}_{\mathrm{2}}.\end{array}\right.

当c\ne \mathrm{0}时，由于q(x)是{\mathrm{F}}_{{\mathrm{2}}^n}上的置换，设c=d^{{\mathrm{2}}^{m+\mathrm{1}}+\mathrm{1}}，这里d\in {\mathrm{F}}_{{\mathrm{2}}^n}^{\mathrm{*}}，且d与c是一一对应的关系，所以有：

\begin{array}{l}{W}_q(c,{(b+c)}^{{\mathrm{2}}^m}+(b+c))=\\ \sum _{x\in {\mathrm{F}}_{{\mathrm{2}}^n}}{(-\mathrm{1})}^{\mathrm{T}{\mathrm{r}}_{\mathrm{1}}^n({(dx)}^{{\mathrm{2}}^{m+\mathrm{1}}+\mathrm{1}}+\frac{{(b+c)}^{{\mathrm{2}}^m}+b+c}{d}(dx))}=\\ \sum _{dx\in {\mathrm{F}}_{{\mathrm{2}}^n}}{(-\mathrm{1})}^{\mathrm{T}{\mathrm{r}}_{\mathrm{1}}^n({(dx)}^{{\mathrm{2}}^{m+\mathrm{1}}+\mathrm{1}}+\frac{{(b+c)}^{{\mathrm{2}}^m}+b+c}{d}(dx))}=\\ \sum _{dx\in {\mathrm{F}}_{{\mathrm{2}}^n}}{(-\mathrm{1})}^{\mathrm{T}{\mathrm{r}}_{\mathrm{1}}^n({(dx)}^{{\mathrm{2}}^{m+\mathrm{1}}+\mathrm{1}}+(d^{{\mathrm{2}}^m}+d^{{\mathrm{2}}^{m+\mathrm{1}}}+\frac{b^{{\mathrm{2}}^m}+b}{d})(dx))}=\\ W_q(\mathrm{1},d^{{\mathrm{2}}^m}+d^{{\mathrm{2}}^{m+\mathrm{1}}}+\frac{b^{{\mathrm{2}}^m}+b}{d}).\end{array}

根据引理3，W_q(\mathrm{1},d^{{\mathrm{2}}^m}+d^{{\mathrm{2}}^{m+\mathrm{1}}}+\frac{b^{{\mathrm{2}}^m}+b}{d})的可能取值为\mathrm{0},\pm {\mathrm{2}}^{\frac{n+\mathrm{1}}{\mathrm{2}}}，并且W_q(\mathrm{1},d^{{\mathrm{2}}^m}+d^{{\mathrm{2}}^{m+\mathrm{1}}}+\frac{b^{{\mathrm{2}}^m}+b}{d})=\mathrm{0}当且仅当\mathrm{T}{\mathrm{r}}_{\mathrm{1}}^n(d^{{\mathrm{2}}^m}+d^{{\mathrm{2}}^{m+\mathrm{1}}}+\frac{b^{{\mathrm{2}}^m}+b}{d})=\mathrm{0}，即\mathrm{T}{\mathrm{r}}_{\mathrm{1}}^n(\frac{b^{{\mathrm{2}}^m}+b}{d})=\mathrm{0}. 由于\mathrm{g}\mathrm{c}\mathrm{d}(m,n)=\mathrm{1}，那么b^{{\mathrm{2}}^m}+b=\mathrm{0}当且仅当b\in {\mathrm{F}}_{\mathrm{2}}. 当b\in {\mathrm{F}}_{\mathrm{2}}时，显然\forall d\in {\mathrm{F}}_{{\mathrm{2}}^n}^{\mathrm{*}}，\mathrm{T}{\mathrm{r}}_{\mathrm{1}}^n(\frac{b^{{\mathrm{2}}^m}+b}{d})=\mathrm{0}，那么此时使\mathrm{T}{\mathrm{r}}_{\mathrm{1}}^n(\frac{b^{{\mathrm{2}}^m}+b}{d})=\mathrm{0}的元素(b,d)的个数是\mathrm{2}({\mathrm{2}}^n-\mathrm{1})；当b\notin {\mathrm{F}}_{\mathrm{2}}，即b^{{\mathrm{2}}^m}+b\ne \mathrm{0}时，由于迹函数是均匀分布的，则对于每一个给定的b，当d取遍{\mathrm{F}}_{{\mathrm{2}}^n}^{\mathrm{*}}，使\mathrm{T}{\mathrm{r}}_{\mathrm{1}}^n(\frac{b^{{\mathrm{2}}^m}+b}{d})=\mathrm{0}的元素d的个数是{\mathrm{2}}^{n-\mathrm{1}}-\mathrm{1}，故此时使\mathrm{T}{\mathrm{r}}_{\mathrm{1}}^n(\frac{b^{{\mathrm{2}}^m}+b}{d})=\mathrm{0}的元素(b,d)的个数是({\mathrm{2}}^{n-\mathrm{1}}-\mathrm{1})({\mathrm{2}}^n-\mathrm{2})；所以当(b,d)遍历{\mathrm{F}}_{{\mathrm{2}}^n}^{\mathrm{*}}\times {\mathrm{F}}_{{\mathrm{2}}^n}时，使W_q(\mathrm{1},d^{{\mathrm{2}}^m}+d^{{\mathrm{2}}^{m+\mathrm{1}}}+\frac{b^{{\mathrm{2}}^m}+b}{d})=\mathrm{0}的(b,d)的个数是({\mathrm{2}}^{n-\mathrm{1}}-\mathrm{1})({\mathrm{2}}^n-\mathrm{2})+\mathrm{2}({\mathrm{2}}^n-\mathrm{1})={\mathrm{2}}^{\mathrm{2}n-\mathrm{1}}.

由于d与c是一一对应的关系，从以上讨论可知：当(b,c)遍历{\mathrm{F}}_{{\mathrm{2}}^n}\times {\mathrm{F}}_{{\mathrm{2}}^n}时，使W_q(c,{(b+c)}^{{\mathrm{2}}^m}+(b+c))=\mathrm{0}的(b,c)对的个数为{\mathrm{2}}^{\mathrm{2}n-\mathrm{1}}+({\mathrm{2}}^n-\mathrm{2})，使W_q(c,{(b+c)}^{{\mathrm{2}}^m}+(b+c))={\mathrm{2}}^n的(b,c)对的个数为2.

再注意到当c=b时，由公式（1）可知，W_q(c,\mathrm{0})={\mathrm{2}}^n当且仅当c=\mathrm{0}，以及W_q(c,\mathrm{0})=\mathrm{0}当且仅当c\ne \mathrm{0}. 所以\forall b,c\in {\mathrm{F}}_{{\mathrm{2}}^n},c\ne b，使W_q(c,{(b+c)}^{{\mathrm{2}}^m}+(b+c))=\mathrm{0}的(b,c)对的个数为{\mathrm{2}}^{\mathrm{2}n-\mathrm{1}}+({\mathrm{2}}^n-\mathrm{2})-({\mathrm{2}}^n-\mathrm{1})={\mathrm{2}}^{\mathrm{2}n-\mathrm{1}}-\mathrm{1}，使W_q(c,{(b+c)}^{{\mathrm{2}}^m}+(b+c))={\mathrm{2}}^n的(b,c)对个数为1，即\forall a,b\in {\mathrm{F}}_{{\mathrm{2}}^n},a\ne \mathrm{0}，使W_f(a,b)=\mathrm{0}的(a,b)对的个数为{\mathrm{2}}^{\mathrm{2}n-\mathrm{1}}-\mathrm{1}，使W_f(a,b)={\mathrm{2}}^n的(a,b)对的个数为1. 下面不妨设使W_f(a,b)={\mathrm{2}}^{\frac{n+\mathrm{1}}{\mathrm{2}}}的(a,b)对的个数为{\lambda }_{\mathrm{1}}，使W_f(a,b)=-{\mathrm{2}}^{\frac{n+\mathrm{1}}{\mathrm{2}}}的(a,b)对的个数为{\lambda }_{\mathrm{2}}. 因为a\in {\mathrm{F}}_{{\mathrm{2}}^n}^{\mathrm{*}},b\in {\mathrm{F}}_{{\mathrm{2}}^n}，所以有：

{\lambda }_{\mathrm{1}}+{\lambda }_{\mathrm{2}}+\mathrm{1}+{\mathrm{2}}^{\mathrm{2}n-\mathrm{1}}-\mathrm{1}={\mathrm{2}}^{\mathrm{2}n}-{\mathrm{2}}^n.(\mathrm{2})

另一方面，根据Walsh变换的定义：

\begin{array}{l}\sum _{a\in {\mathrm{F}}_{{\mathrm{2}}^n}^{\mathrm{*}}}\sum _{b\in {\mathrm{F}}_{{\mathrm{2}}^n}}{W}_f(a,b)=\\ \sum _{a\in {\mathrm{F}}_{{\mathrm{2}}^n}^{\mathrm{*}}}\sum _{b\in {\mathrm{F}}_{{\mathrm{2}}^n}}\sum _{x\in {\mathrm{F}}_{{\mathrm{2}}^n}}{(-\mathrm{1})}^{\mathrm{T}{\mathrm{r}}_{\mathrm{1}}^n(af(x)+bx)}=\\ \sum _{x\in {\mathrm{F}}_{{\mathrm{2}}^n}}\sum _{a\in {\mathrm{F}}_{{\mathrm{2}}^n}^{\mathrm{*}}}{(-\mathrm{1})}^{\mathrm{T}{\mathrm{r}}_{\mathrm{1}}^n(af(x))}\cdot \sum _{b\in {\mathrm{F}}_{{\mathrm{2}}^n}}{(-\mathrm{1})}^{\mathrm{T}{\mathrm{r}}_{\mathrm{1}}^n(bx)}=\\ {\mathrm{2}}^n\sum _{a\in {\mathrm{F}}_{{\mathrm{2}}^n}^{\mathrm{*}}}{(-\mathrm{1})}^{\mathrm{T}{\mathrm{r}}_{\mathrm{1}}^n(af(\mathrm{0}))}=\\ {\mathrm{2}}^{\mathrm{2}n}-{\mathrm{2}}^n.\end{array}

又因为\sum _{a\in {\mathrm{F}}_{{\mathrm{2}}^n}^{\mathrm{*}}}\sum _{b\in {\mathrm{F}}_{{\mathrm{2}}^n}}{W}_f(a,b)={\mathrm{2}}^n+{\mathrm{2}}^{\frac{n+\mathrm{1}}{\mathrm{2}}}{\lambda }_{\mathrm{1}}-{\mathrm{2}}^{\frac{n+\mathrm{1}}{\mathrm{2}}}{\lambda }_{\mathrm{2}}. 所以：

{\mathrm{2}}^n+{\mathrm{2}}^{\frac{n+\mathrm{1}}{\mathrm{2}}}{\lambda }_{\mathrm{1}}-{\mathrm{2}}^{\frac{n+\mathrm{1}}{\mathrm{2}}}{\lambda }_{\mathrm{2}}={\mathrm{2}}^{\mathrm{2}n}-{\mathrm{2}}^n. (\mathrm{3})

联立方程(\mathrm{2})，(\mathrm{3})便可解得{\lambda }_{\mathrm{1}},{\lambda }_{\mathrm{2}}，即：

{\lambda }_{\mathrm{1}}={\mathrm{2}}^{\mathrm{2}n-\mathrm{2}}-{\mathrm{2}}^{n-\mathrm{1}}+{\mathrm{2}}^{\mathrm{2}n-\frac{n+\mathrm{3}}{\mathrm{2}}}-{\mathrm{2}}^{\frac{n-\mathrm{1}}{\mathrm{2}}}，{\lambda }_{\mathrm{2}}={\mathrm{2}}^{\mathrm{2}n-\mathrm{2}}-{\mathrm{2}}^{n-\mathrm{1}}-{\mathrm{2}}^{\mathrm{2}n-\frac{n+\mathrm{3}}{\mathrm{2}}}+{\mathrm{2}}^{\frac{n-\mathrm{1}}{\mathrm{2}}}.

定理2 设f(x)=x+x^{{\mathrm{2}}^{m+\mathrm{1}}-\mathrm{1}}+x^{{\mathrm{2}}^n-{\mathrm{2}}^{m+\mathrm{1}}+\mathrm{1}}是有限域{\mathrm{F}}_{{\mathrm{2}}^n}上的三项式，其中n=\mathrm{2}m+\mathrm{1}，那么f(x)的差分谱为：\{{\omega }_{\mathrm{0}}=\mathrm{5}\cdot {\mathrm{2}}^{\mathrm{2}n-\mathrm{3}}-\mathrm{3}\cdot {\mathrm{2}}^{n-\mathrm{2}},{\omega }_{\mathrm{1}}=\mathrm{0},{\omega }_{\mathrm{2}}={\mathrm{2}}^{\mathrm{2}n-\mathrm{2}},{\omega }_{\mathrm{3}}=\mathrm{0},{\omega }_{\mathrm{4}}={\mathrm{2}}^{\mathrm{2}n-\mathrm{3}}-{\mathrm{2}}^{n-\mathrm{2}}\}.

证明 由引理1可知f(x)是{\mathrm{F}}_{{\mathrm{2}}^n}上的4差分一致性函数，即当i\notin \{\mathrm{0},\mathrm{2},\mathrm{4}\}时，{\omega }_i=\mathrm{0}，再根据差分谱的两个基本等式以及引理2便能够得到如下方程组：

\left\{\begin{array}{l}{\omega }_{\mathrm{0}}+{\omega }_{\mathrm{2}}+{\omega }_{\mathrm{4}}={\mathrm{2}}^{\mathrm{2}n-\mathrm{1}}-{\mathrm{2}}^n,\\ \mathrm{2}{\omega }_{\mathrm{2}}+\mathrm{4}{\omega }_{\mathrm{4}}={\mathrm{2}}^{\mathrm{2}n-\mathrm{1}}-{\mathrm{2}}^n,\\ {\mathrm{2}}^{\mathrm{2}n}(\mathrm{4}{\omega }_{\mathrm{2}}+\mathrm{16}{\omega }_{\mathrm{4}})={\mathrm{2}}^{\mathrm{4}n}+({\mathrm{2}}^{\frac{n+\mathrm{1}}{\mathrm{2}}}{)}^{\mathrm{4}}({\mathrm{2}}^{\mathrm{2}n-\mathrm{2}}-{\mathrm{2}}^n),\end{array}\right.

解得：{\omega }_{\mathrm{0}}=\mathrm{5}\cdot {\mathrm{2}}^{\mathrm{2}n-\mathrm{3}}-\mathrm{3}\cdot {\mathrm{2}}^{n-\mathrm{2}},{\omega }_{\mathrm{2}}={\mathrm{2}}^{\mathrm{2}n-\mathrm{2}},{\omega }_{\mathrm{4}}={\mathrm{2}}^{\mathrm{2}n-\mathrm{3}}-{\mathrm{2}}^{n-\mathrm{2}}.

定理3 设g(x)=x^{{\mathrm{2}}^{\mathrm{2}k}+{\mathrm{2}}^k}+x^{{\mathrm{2}}^{\mathrm{2}k}+\mathrm{1}}+x^{{\mathrm{2}}^k+\mathrm{1}}是有限域{\mathrm{F}}_{{\mathrm{2}}^n}上的三项式，其中\mathrm{g}\mathrm{c}\mathrm{d}(n,k)=\mathrm{1}，那么g(x)的差分谱为：{\omega }_{\mathrm{0}}=\mathrm{3}\cdot {\mathrm{2}}^{\mathrm{2}n-\mathrm{2}}-\mathrm{3}\cdot {\mathrm{2}}^{n-\mathrm{1}}-\mathrm{1},{\omega }_{\mathrm{4}}={\mathrm{2}}^{\mathrm{2}n-\mathrm{2}}-{\mathrm{2}}^{n-\mathrm{1}},{\omega }_{{\mathrm{2}}^n}=\mathrm{1}；当i\notin \{\mathrm{0},\mathrm{4},{\mathrm{2}}^n\}时，{\omega }_i=\mathrm{0}.

证明\forall a,b\in {\mathrm{F}}_{{\mathrm{2}}^n}且a\ne \mathrm{0}，g(x)的差分方程为：

(a^{{\mathrm{2}}^k}+a)x^{{\mathrm{2}}^{\mathrm{2}k}}+(a^{{\mathrm{2}}^{\mathrm{2}k}}+a)x^{{\mathrm{2}}^k}+(a^{{\mathrm{2}}^{\mathrm{2}k}}+a^{{\mathrm{2}}^k})x=b+g(a).(\mathrm{4})

当a=\mathrm{1}时，方程(\mathrm{4})左边恒为0，所以当b+g(a)=\mathrm{0}即b=g(\mathrm{1})=\mathrm{1}时，\forall x\in {\mathrm{F}}_{{\mathrm{2}}^n}，方程(\mathrm{4})恒成立，故此时差分方程解的个数为{\mathrm{2}}^n；若b+g(\mathrm{1})\ne \mathrm{0}即b\ne \mathrm{1}，则方程(\mathrm{4})无解.

当a\ne \mathrm{1}时，注意到方程(\mathrm{4})左边是一个线性化多项式，所以只需考虑齐次方程：

(a^{{\mathrm{2}}^k}+a)x^{{\mathrm{2}}^{\mathrm{2}k}}+(a^{{\mathrm{2}}^{\mathrm{2}k}}+a)x^{{\mathrm{2}}^k}+(a^{{\mathrm{2}}^{\mathrm{2}k}}+a^{{\mathrm{2}}^k})x=\mathrm{0}

解的个数即可. 令x=\frac{y}{a}，那么便有：

a^{{\mathrm{2}}^{\mathrm{2}k}}(a^{{\mathrm{2}}^k}+a)y^{{\mathrm{2}}^{\mathrm{2}k}}+a^{{\mathrm{2}}^k}(a^{{\mathrm{2}}^{\mathrm{2}k}}+a)y^{{\mathrm{2}}^k}+a(a^{{\mathrm{2}}^{\mathrm{2}k}}+a^{{\mathrm{2}}^k})y=\mathrm{0},

即：

(a^{{\mathrm{2}}^{\mathrm{2}k}-\mathrm{1}}+a^{{\mathrm{2}}^{\mathrm{2}k}-{\mathrm{2}}^k})y^{{\mathrm{2}}^{\mathrm{2}k}}+(a^{{\mathrm{2}}^{\mathrm{2}k}-\mathrm{1}}+\mathrm{1})y^{{\mathrm{2}}^k}+(a^{{\mathrm{2}}^{\mathrm{2}k}-{\mathrm{2}}^k}+\mathrm{1})y=\mathrm{0}.(\mathrm{5})

下面不妨设t=y^{{\mathrm{2}}^k}+y，带入方程并化简得：

a^{{\mathrm{2}}^{\mathrm{2}k}-{\mathrm{2}}^k}(a^{{\mathrm{2}}^k-\mathrm{1}}+\mathrm{1})t^{{\mathrm{2}}^k}+(a^{{\mathrm{2}}^k-\mathrm{1}}{+\mathrm{1})}^{{\mathrm{2}}^k}t=\mathrm{0}.(\mathrm{6})

因为\mathrm{g}\mathrm{c}\mathrm{d}(n,k)=\mathrm{1}，所以\mathrm{g}\mathrm{c}\mathrm{d}({\mathrm{2}}^k-\mathrm{1},{\mathrm{2}}^n-\mathrm{1})=\mathrm{1}，又因为a\ne \mathrm{1}所以a^{{\mathrm{2}}^k-\mathrm{1}}+\mathrm{1}\ne \mathrm{0}，故方程(\mathrm{6})有两个解：t_{\mathrm{1}}=\mathrm{0},t_{\mathrm{2}}=\frac{\mathrm{1}+a^{{\mathrm{2}}^k-\mathrm{1}}}{a^{{\mathrm{2}}^k}}. 对于给定的t，方程y^{{\mathrm{2}}^k}+y=t要么有两个解要么无解.注意到当t_{\mathrm{1}}=\mathrm{0}方程y^{{\mathrm{2}}^k}+y=t_{\mathrm{1}}有两个解：y=\mathrm{0}和y=\mathrm{1}；当t_{\mathrm{2}}=\frac{\mathrm{1}+a^{{\mathrm{2}}^k-\mathrm{1}}}{a^{{\mathrm{2}}^k}}时，方程y^{{\mathrm{2}}^k}+y=t_{\mathrm{2}}也有两个解：\frac{\mathrm{1}}{a}和\frac{\mathrm{1}}{a}+\mathrm{1}，故方程(\mathrm{5})有4个解，从而当a\ne \mathrm{1}时差分方程(\mathrm{4})可能的解数为\mathrm{4}或\mathrm{0}.

综上所述，\forall a,b\in {\mathrm{F}}_{{\mathrm{2}}^n}且a\ne \mathrm{0}，差分方程(\mathrm{4})可能的解数为\mathrm{0},\mathrm{4},{\mathrm{2}}^n.所以当i\notin \{\mathrm{0},\mathrm{4},{\mathrm{2}}^n\}时，{\omega }_i=\mathrm{0}.从上述分析还可知：当且仅当a=\mathrm{1}且b=\mathrm{1}时，差分方程(\mathrm{4})有{\mathrm{2}}^n个解，所以{\omega }_{{\mathrm{2}}^n}=\mathrm{1}. 结合差分谱的两个基本等式从而得到如下方程组：

\left\{\begin{array}{l}{\omega }_{\mathrm{0}}+{\omega }_{\mathrm{4}}+\mathrm{1}={\mathrm{2}}^n({\mathrm{2}}^n-\mathrm{1}),\\ \mathrm{4}{\omega }_{\mathrm{4}}+{\mathrm{2}}^n={\mathrm{2}}^n({\mathrm{2}}^n-\mathrm{1}),\end{array}\right.

解得：{\omega }_{\mathrm{0}}=\mathrm{3}\cdot {\mathrm{2}}^{\mathrm{2}n-\mathrm{2}}-{\mathrm{2}}^{n-\mathrm{1}}-\mathrm{1}，{\omega }_{\mathrm{4}}={\mathrm{2}}^{\mathrm{2}n-\mathrm{2}}-{\mathrm{2}}^{n-\mathrm{1}}，即得g(x)的差分谱.

定理4 设g(x)=x^{{\mathrm{2}}^{\mathrm{2}k}+{\mathrm{2}}^k}+x^{{\mathrm{2}}^{\mathrm{2}k}+\mathrm{1}}+x^{{\mathrm{2}}^k+\mathrm{1}}是有限域{\mathrm{F}}_{{\mathrm{2}}^n}上的三项式，其中\mathrm{g}\mathrm{c}\mathrm{d}(n,k)=\mathrm{1}，n\ge \mathrm{6}，那么g(x)的Walsh谱由表2（n是奇数）和表3（n是偶数）给出.

证明\forall a,b\in {\mathrm{F}}_{{\mathrm{2}}^n}，根据Walsh变换的定义，有：

W_g(a,b)=\sum _{x\in {\mathrm{F}}_{{\mathrm{2}}^n}}{(-\mathrm{1})}^{\mathrm{T}{\mathrm{r}}_{\mathrm{1}}^n(ag(x)+bx)}=\sum _{x\in {\mathrm{F}}_{{\mathrm{2}}^n}}{(-\mathrm{1})}^{\mathrm{T}{\mathrm{r}}_{\mathrm{1}}^n(a(x^{{\mathrm{2}}^{\mathrm{2}k}+{\mathrm{2}}^k}+x^{{\mathrm{2}}^{\mathrm{2}k}+\mathrm{1}}+x^{{\mathrm{2}}^k+\mathrm{1}})+bx)}=\sum _{x\in {\mathrm{F}}_{{\mathrm{2}}^n}}{(-\mathrm{1})}^{\mathrm{T}{\mathrm{r}}_{\mathrm{1}}^n((a^{{\mathrm{2}}^{n-k}}+a)x^{{\mathrm{2}}^k+\mathrm{1}}+a{x}^{{\mathrm{2}}^{\mathrm{2}k}+\mathrm{1}})+bx)}.

注意到当a=\mathrm{0}时，显然有：

W_g(a,b)=\left\{\begin{array}{l}{\mathrm{2}}^n,b=\mathrm{0},\\ \mathrm{0},b\ne \mathrm{0}.\end{array}\right.

当a\ne \mathrm{0}时，不妨记Q_a(x)=\mathrm{T}{\mathrm{r}}_{\mathrm{1}}^n((a^{{\mathrm{2}}^{n-k}}+a)x^{{\mathrm{2}}^k+\mathrm{1}}+a{x}^{{\mathrm{2}}^{\mathrm{2}k}+\mathrm{1}})，则Q_a(x)是{\mathrm{F}}_{{\mathrm{2}}^n}上的二次型. 由引理4可得n-\mathrm{4}\le \mathrm{R}\mathrm{a}\mathrm{n}\mathrm{k}(Q_a(x))\le n. 由于\mathrm{R}\mathrm{a}\mathrm{n}\mathrm{k}(Q_a(x))是一个偶数，所以当n是奇数时，\mathrm{R}\mathrm{a}\mathrm{n}\mathrm{k}(Q_a(x))的可能取值为n-\mathrm{3}和n-\mathrm{1}；当n是偶数时，\mathrm{R}\mathrm{a}\mathrm{n}\mathrm{k}(Q_a(x))的可能取值为n-\mathrm{4}，n-\mathrm{2}和n.

另一方面，根据V(Q_a)的定义，\forall y\in {\mathrm{F}}_{{\mathrm{2}}^n}，计算

\begin{array}{l}{Q}_a(x+y)+Q_a(x)+Q_a(y)=\\ \mathrm{T}{\mathrm{r}}_{\mathrm{1}}^n((a^{{\mathrm{2}}^k}+a){(x+y)}^{{\mathrm{2}}^{\mathrm{2}k}+{\mathrm{2}}^k}+a{(x+y)}^{{\mathrm{2}}^{\mathrm{2}k}+\mathrm{1}}+(a^{{\mathrm{2}}^k}+\\ a)x^{{\mathrm{2}}^{\mathrm{2}k}+{\mathrm{2}}^k}+a{x}^{{\mathrm{2}}^{\mathrm{2}k}+\mathrm{1}}+(a^{{\mathrm{2}}^k}+a)y^{{\mathrm{2}}^{\mathrm{2}k}+{\mathrm{2}}^k}+a{y}^{{\mathrm{2}}^{\mathrm{2}k}+\mathrm{1}})=\\ \mathrm{T}{\mathrm{r}}_{\mathrm{1}}^n((a^{{\mathrm{2}}^k}{x}^{{\mathrm{2}}^k}+a{x}^{{\mathrm{2}}^k}+a^{{\mathrm{2}}^{\mathrm{2}k}}{x}^{{\mathrm{2}}^{\mathrm{3}k}}+a^{{\mathrm{2}}^k}{x}^{{\mathrm{2}}^{\mathrm{3}k}}+a^{{\mathrm{2}}^{\mathrm{2}k}}{x}^{{\mathrm{2}}^{\mathrm{4}k}}+ax)y^{{\mathrm{2}}^{\mathrm{2}k}})=\\ \mathrm{T}{\mathrm{r}}_{\mathrm{1}}^n((a^{{\mathrm{2}}^k}(x^{{\mathrm{2}}^k}+x^{{\mathrm{2}}^{\mathrm{3}k}})+a(x^{{\mathrm{2}}^k}+x)+a^{{\mathrm{2}}^{\mathrm{2}k}}(x^{{\mathrm{2}}^{\mathrm{3}k}}+x^{{\mathrm{2}}^{\mathrm{4}k}}))y^{{\mathrm{2}}^{\mathrm{2}k}}).\end{array}

对于给定a\ne \mathrm{0}，根据上式知：当x\in {\mathrm{F}}_{\mathrm{2}}时，\forall y\in {\mathrm{F}}_{{\mathrm{2}}^n}，总有Q_a(x+y)+Q_a(x)+Q_a(y)=\mathrm{0}，所以{\mathrm{F}}_{\mathrm{2}}\subseteq V(Q_a)，即\mathrm{d}\mathrm{i}{\mathrm{m}}_{{\mathrm{F}}_{\mathrm{2}}}(V(Q_a))\ge \mathrm{1}，故\mathrm{R}\mathrm{a}\mathrm{n}\mathrm{k}(Q_{\lambda })\le n-\mathrm{1}. 因此当n是偶数时\mathrm{R}\mathrm{a}\mathrm{n}\mathrm{k}(Q_a(x))的可能取值为n-\mathrm{4}和n-\mathrm{2}.

下面以n是奇数为例，来计算g(x)的Walsh谱，n是偶数时类似可得.

设a\in {\mathrm{F}}_{{\mathrm{2}}^n}^{\mathrm{*}}，使\mathrm{R}\mathrm{a}\mathrm{n}\mathrm{k}(Q_a(x))=n-\mathrm{3}的元素a的个数为n_{\mathrm{1}}，使\mathrm{R}\mathrm{a}\mathrm{n}\mathrm{k}(Q_a(x))=n-\mathrm{1}的个数为n_{\mathrm{2}}，由引理5可知此时g(x)的Walsh谱为：

W_g(a,b)=\left\{\begin{array}{l}\mathrm{0},n_{\mathrm{1}}({\mathrm{2}}^n-{\mathrm{2}}^{n-\mathrm{1}})+n_{\mathrm{2}}({\mathrm{2}}^n-{\mathrm{2}}^{n-\mathrm{3}}),\\ \pm {\mathrm{2}}^{\frac{n+\mathrm{1}}{\mathrm{2}}},n_{\mathrm{2}}({\mathrm{2}}^{n-\mathrm{2}}\pm {\mathrm{2}}^{\frac{n-\mathrm{3}}{\mathrm{2}}}),\\ \pm {\mathrm{2}}^{\frac{n+\mathrm{3}}{\mathrm{2}}},n_{\mathrm{1}}({\mathrm{2}}^{n-\mathrm{4}}\pm {\mathrm{2}}^{\frac{n-\mathrm{5}}{\mathrm{2}}}).\end{array}\right.

再根据引理2以及g(x)的差分谱，便能够得到关于n_{\mathrm{1}},n_{\mathrm{2}}的方程，即：

{\mathrm{2}}^{n-\mathrm{3}}({\mathrm{2}}^{\frac{n+\mathrm{3}}{\mathrm{2}}}{)}^{\mathrm{4}}{n}_{\mathrm{1}}+{\mathrm{2}}^{n-\mathrm{1}}({\mathrm{2}}^{\frac{n+\mathrm{1}}{\mathrm{2}}}{)}^{\mathrm{4}}{n}_{\mathrm{2}}+{\mathrm{2}}^{\mathrm{4}n}={\mathrm{2}}^{\mathrm{4}n}+{\mathrm{2}}^{\mathrm{2}n}(\mathrm{16}({\mathrm{2}}^{\mathrm{2}n-\mathrm{2}}-{\mathrm{2}}^{n-\mathrm{1}})+{\mathrm{2}}^{\mathrm{2}n}).

又因为n_{\mathrm{1}}+n_{\mathrm{2}}={\mathrm{2}}^n-\mathrm{1}，联立这两个方程解得：n_{\mathrm{1}}={\mathrm{2}}^{n-\mathrm{1}}-\mathrm{1},n_{\mathrm{2}}={\mathrm{2}}^{n-\mathrm{1}}，从而确定了n为奇数时g(x)的Walsh谱.

下面给出利用软件Magma计算差分谱和Walsh谱所得到的具体结果.

例1 当m=\mathrm{3}时，f\left(x\right)=x+x^{\mathrm{15}}+x^{\mathrm{113}}，利用软件Magma可以得到此时f\left(x\right)的差分谱为：\left\{{\omega }_{\mathrm{0}}=\mathrm{10144},{\omega }_{\mathrm{2}}=\mathrm{4096},{\omega }_{\mathrm{4}}=\mathrm{2016}\right\}，Walsh谱为：

W_f(a,b)=\left\{\begin{array}{l}\mathrm{128},\mathrm{1}\mathrm{次},\\ \mathrm{16},\mathrm{4536}\mathrm{次},\\ -\mathrm{16},\mathrm{3528}\mathrm{次},\\ \mathrm{0},\mathrm{8191}\mathrm{次}.\end{array}\right.

例2 当k=\mathrm{3}，n=\mathrm{5}时，g\left(x\right)=x^{\mathrm{72}}+x^{\mathrm{65}}+x^{\mathrm{9}}，由软件Magma可以得到此时g\left(x\right)的差分谱为：\left\{{\omega }_{\mathrm{0}}=\mathrm{12223},{\omega }_{\mathrm{4}}=\mathrm{4032},{\omega }_{\mathrm{128}}=\mathrm{1}\right\}，Walsh谱为：

W_g(a,b)=\left\{\begin{array}{l}\mathrm{32},\mathrm{630}\mathrm{次},\\ -\mathrm{32},\mathrm{378}\mathrm{次},\\ \mathrm{16},\mathrm{2304}\mathrm{次},\\ -\mathrm{16},\mathrm{1792}\mathrm{次},\\ \mathrm{0},\mathrm{11152}\mathrm{次}.\end{array}\right.

4 结论

本文研究了在有限域{\mathrm{F}}_{{\mathrm{2}}^n}上两类不同三项式的差分谱和Walsh谱. 第一类是置换三项式f(x)=x+x^{{\mathrm{2}}^{m+\mathrm{1}}-\mathrm{1}}+x^{{\mathrm{2}}^n-{\mathrm{2}}^{m+\mathrm{1}}+\mathrm{1}}，其中n=\mathrm{2}m+\mathrm{1}；第二类是几乎低差分一致性函数g(x)=x^{{\mathrm{2}}^{\mathrm{2}k}+{\mathrm{2}}^k}+x^{{\mathrm{2}}^{\mathrm{2}k}+\mathrm{1}}+x^{{\mathrm{2}}^k+\mathrm{1}}，其中\mathrm{g}\mathrm{c}\mathrm{d}(n,k)=\mathrm{1}. 值得注意的是对于定义在特征为2的有限域上的函数，若它们的差分均匀度为4，那么可以考虑使用引理2中Walsh谱与差分谱之间的关系来计算差分谱. 目前国内外对差分谱的研究主要集中在幂函数和几类具有低差分均匀度的置换多项式上，采用的方法大多数都是从差分方程的定义出发，来分析方程的解出现的条件及个数. 感兴趣的读者可以尝试将本文中所使用的方法应用到目前未能解决的问题中，或许能够得到一些新的结果.

参考文献

[1] BIHAM E， SHAMIR A. Differential cryptanalysis of DES-like cryptosystems［J］. Journal of Cryptology， 1991， 4（1）： 3-72.

[2] NYBERG K. Differentially uniform mappings for cryptography［C］//EUROCRYPT. Workshop on the Theory and Application of Cryptographic Techniques. Lofthus： Springer， 1993， 55-64.

[3] ZHU X， ZENG X， CHEN Y. Some binomial and trinomial differentially 4-uniform permutation polynomials［J］. International Journal of Foundations of Computer Science， 2015， 26（4）： 487-497.

[4] DING C， QU L， WANG Q， et al. Permutation trinomials over finite fields with even characteristic［J］. SIAM Journal on Discrete Mathematics， 2015， 29（1）： 79-92.

[5] 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.

[6] BRACKEN C， TAN C H， TAN Y. Binomial differentially 4 uniform permutations with high nonlinearity［J］. Finite Fields and Their Applications， 2012， 18（3）： 537-546.

[7] LI Y， WANG M. Constructing differentially 4-uniform permutations over GF（22m） from quadratic APN permutations over GF（22m+1）［J］. Designs， Codes and Cryptography， 2014， 72（2）： 249-264.

[8] TAN Y， QU L， TAN C H， et al. New families of differentially 4-uniform permutations over $｛\mathbb F｝_｛2^｛2k｝｝ $［M］//Lecture Notes in Computer Science. Berlin， Springer 2012.

[9] TANG D， CARLET C， TANG X. Differentially 4-uniform bijections by permuting the inverse function［J］. Designs， Codes and Cryptography， 2015， 77（1）： 117-141.

[10] ZHA Z， HU L， SUN S. Constructing new differentially 4-uniform permutations from the inverse function［J］. Finite Fields and Their Applications， 2014， 25： 64-78.

[11] 查正邦. 低差分一致性函数的研究［D］. 长沙： 湖南大学， 2008.

[12] FELKE P. Computing the uniformity of power mappings： A systematic approach with multi-variate method over fnite fields of odd characteristic［D］. Bochum： University of Bochum， 2005.

[13] CHARPIN P， PENG J. New links between nonlinearity and differential uniformity［J］. Finite Fields and Their Applications， 2019， 56： 188-208.

[14] WANG Y B， KADIR W， LI C L， et al. On cryptographic properties of the Welch permutation and a related conjecture［C］//Sequences and Their Applications. Saint Petersburg： Springer， 2020： 1-13.

[15] HELLESETH T， RONG C， SANDBERG D. New families of almost perfect nonlinear power mappings［J］. IEEE Transactions on Information Theory， 1999， 45（2）： 475-485.

[16] GOLD R. Maximal recursive sequences with 3-valued recursive cross-correlation functions （Corresp.）［J］. IEEE Transactions on Information Theory， 1968， 14（1）： 154-156.

[17] HELLESETH T， KUMAR P V. Sequences with low correlation［A］. PLESS V S， HUFFMAN W C. Handbook of Coding Theory. Amsterdam： Elsevier Science， 1998：1765-1853．

基金资助

国家自然科学基金资助项目(62171479)

中南民族大学中央高校基本科研业务费专项资金资助项目(CZZ23004)