Maiorana-McFarland类Bent函数的一个二阶非线性度下界*

余兴华，罗淑丹，李 镭

（中国电子科技集团公司第三十研究所，四川 成都 610041）

0 引 言

布尔函数在对称密码学、纠错码、通信系统和序列设计中具有广泛应用。二阶非线性度是布尔函数的一个重要参数，不但能够衡量布尔函数的稳定性，而且能抵抗一些已知和潜在的密码攻击手段。虽然这些潜在的密码攻击手段目前的攻击时间复杂度很大，但是随着计算机科学技术的迅猛发展，将来有可能真正威胁到密码系统的安全性。序列密码中所使用布尔函数二阶非线性度的攻击方法可参见文献[1-2]；分组密码中所使用布尔函数的攻击方法参见文献[3]。由于所有n变元布尔函数的最大二阶非线性度等于长度为2n的二阶Reed-Muller码RM(2,n)的覆盖半径[4]，因此该参数在编码理论中非常重要。此外，该参数与Gowers范数有关[5]。

众所周知，当变元个数n为偶数时，Bent函数[6]具有最高的1阶非线性度2n-1-2n/2-1。Bent函数是组合中一类非常重要的研究对象，与差集[7]直接相关；Bent函数可以用来构造和设计具有良好性能的纠错码[8]；Bent函数可以被修改为具有高非线性度的平衡布尔函数[9-10]，但这种平衡布尔函数具有较弱的快速代数免疫度[2,11]。对于布尔函数二阶非线性度的研究，目前没有已知太多结果，因为计算变元个数较大且代数次数较高的布尔函数的二阶非线性度是非常困难的。事实上，即使给出变元个数较大且代数次数较高的布尔函数的较紧二阶非线性度下界亦非常困难。2008年，Carlet[12]给出了计算布尔函数二阶非线性度下界的方法，主要依赖于布尔函数微商的非线性度。基于该方法，近十年来国内外给出了大量布尔函数的二阶非线性度下界，如文献[12-16]。

本文主要关注Bent函数的二阶非线性度下界，因为其具有最大的1阶非线性度。本文推导得到了MM类Bent函数（参见参考文献[7，17]和本文中的构造1）的一个二阶非线性度下界。该界主要依赖于MM类Bent函数构造中所使用置换的非线性度和差分均匀度。事实上，所有已知的MM类Bent函数的二阶非线性度下界，均可看作是所提方法结果的一个推论，极大地简化了已知MM类Bent函数的二阶非线性度下界的证明，如文献[13，15]中最简单的（PS）Bent函数和函数的二阶非线性度下界。此外，还得到了一类由Canteaut猜想、被Leander[18]证明的一类Bent函数的二阶非线性度的一个下界。

本文主要内容安排如下。第2章主要介绍一些符号和所需要的预备知识；第3章基于研究MM类Bent函数中使用的置换的非线性度和差分均匀度，给出计算MM类Bent函数的二阶非线性度下界的一个系统方法；第4章给出一类属于MM类Bent函数的一个二阶非线性度的下界；第5章对全文进行总结概括。

1 预备知识

令F2n为有限域F2={0,1}上的n维向量空间，F2n是阶为2n的有限域。对任意a=(a1,…,an)∈F2n，其支撑集定义为{1≤i≤n:ai=1}，汉明重wt(a)定义为其支撑集的大小（势），即wt(a)=|sup p(a)|。一个布尔函数是指从F2n到F2的映射，所有n变元的布尔函数的集合记作Bn。n变元布尔函数的支撑集定义为集合：{x∈F2n:f(x) ≠ 0}。n变元布尔函数f(x1,…,xn)的基本表示方法为它的真值表，即：

众所周知，Bn中的任何布尔函数f可以由F2上的多元多项式唯一表示，称为代数正规型（ANF），形式如下：

其中，au∈F2，u=(u1,…,un)，它的代数次数记作deg( f )，指满足au≠ 0的wt(u)的最大值。

向量空间F2n与有限域F2n同构。事实上，如果 (λ1,λ2,…,λn)是 F2n上的一组基，则对于 F2n上的每个元素 x，都可以被唯一表示成 x=x1λ1+x2λ2+…+xnλn∈F2n。于是，F2n上的每一个元素都可以映射成一个n长的二元向量。显然，元素0∈F2n映射成F2n上的全零向量。因此，任意一个n变元的布尔函数都可以在F2n上定义，并且被唯一表示成一元多项式：

其中：

n变元的布尔函数f的支撑集被定义为集合{x∈F2n:f (x)≠0}。当n=2k时，有限域F2n可以被表示成F22k。因此，任意一个偶数n变元的布尔函数可以被看作是定义在F22k上，并能够被唯一地表示成一个二元多项式：

其中x,y∈F2k，有：

两个布尔函数f, g∈Bn之间的汉明距离记作：

f的r阶非线性度定义为f与所有代数次数至多为r的n变元布尔函数之间的最小汉明距离：

f的一阶非线性度简称为f的非线性度，用nl( f )表示。布尔函数的非线性度可以通过f的Walsh变换计算。

假设：

并用a· x表示它们之间的点积，即：则f∈Bn在a∈F2n点的Walsh变换定义为：

在F2n上，布尔函数f在α∈F2n点的Walsh变换定义为：

是从F2n到F2上的迹函数。应当注意，对于任意布尔函数f∈Bn，由Parseval等式

当达到这个上界，即取等号的这类函数被称为Bent函数[6]。Bent函数只在n为偶数时存在。应当注意，每一个Bent函数f∈Bn的代数次数满足：对于n≥4，deg( f )≤n/2。

正如引言中所述，很难确定一个代数次数不小于r+1的布尔函数的r阶非线性度。在文献[12]中，Carlet提出了一种给出n变元布尔函数f的r阶非线性度下界的方法，主要依赖于f的微商Daf(x)=f(x)+f(x+a)，其中a∈F2n*的r-1阶非线性度是已知的。

引理1[12]：设n是任意一个正整数，f是任意一个n变元布尔函数，r是一个小于n的正整数，则：

2 MM类Bent函数的一类二阶非线性度下界

将给出MM类Bent函数的二阶非线性度的一个下界。这类Bent函数是由J.A. Maiorana和R.L.McFarland（参见文献[7，17]）独立发现的，其中包括大量的Bent函数。首先回顾MM类Bent函数的构造。

构造1：设n=2k是偶数，则所有形如：

的布尔函数是Bent函数，其中x,y∈F2，F是F2k上的任意一个置换，g是任意一个k变元布尔函数。

给定一个正整数n，从F2n到它自身的一个映射，通常被称为一个(n,n)-函数。设G是一个(n,n)-函数，则定义为G(x)=(g1(x),…,gn(x))的n变元布尔函数g1(x),…,gn(x)为G的分量函数。此外，若 (β1,β2,…,βn)=β ∈ F2n是 G 的分量函数的不全为零的系数，则由它们构成的线性组合布尔函数称为G的组合函数，可以简单记成β·G。G的代数次数等于它分量函数的最大代数次数，因此等于其组合函数的最大代数次数。式（16）中的f的代数次数等于deg( F )+1，其中置换F可以看作一个(n,n)函数。非线性度nl(G)定义为G的所有组合函数的最小非线性度，G的非线性度上界为如果非线性度达到这个上界，则称G为几乎Bent（Almost Bent，AB）函数。显然，AB函数仅当n为奇数时存在。当n为偶数时，nl(G)的最佳已知值G当 用于分组密码系统时，为了衡量G抵抗差分攻击[20]的能力，Nyberg[21]引入了一种称为差分均匀度的概念，定义为：k

显然，最小的差分均匀度是2。若δG=2，则称G为几乎完美非线性（Almost Perfect Nonlinear，APN）函数。

现在给出由式（16）定义的MM类Bent函数的一个二阶非线性度下界，其在很大程度上依赖于δF的大小和(k,k)置换F的非线性度。

定理1：设n=2k，设f(x,y)=F(x)·y+g(x)是式（16）所定义的MM类Bent函数，则：

证明：当 (α,β)=(0,0)时，nl(D(α,β)f )=0。对于任意一对 (α,β)∈

现 在 考 虑 D(α,β)f在 点 对 (a,b)∈ F2k×F2k处 的Walsh变换，由定义得：

考虑 WD(α,β)f(a,b)的以下两种情况。

情形1：α=0,β∈F2k*。这种情形下，有：

将方程（24）和方程（28）代入引理1，立即得证。

3 应用

作为定理1的直接应用，下面将给出两类MM类Bent函数一个二阶非线性度下界简单而直接的证明。

3.1 例1：最简单的PS类Bent函数的一类二阶非线性度下界

这类Bent函数由Dillon[7]引入，指的是支撑集由F22k上两两不相交的2k-1或2k-1+1个k维子空间组成的Bent函数。“不相交”意味着任何两个这种子空间的交集为零空间。2011年，Carlet[22]第一次给出了最简形式的PS类Bent函数的r阶非线性度的一个下界，其中2≤r≤k-1。最简形式的PS类Bent函数定义如下：

下面先给出后文所需的几个引理。

引理2[23]：设k是任意一个正整数，函数Tr1k(λ/y)是定义在F2k上的一个布尔函数，其中λ∈F*2k，则该函数的Walsh谱能够取得区间[-2k/2+1+1,2k/2+1+1]上所有能够被4整除的数。

方便起见，本文定义：

显然，当k为偶数时，有tk=2k/2+1。

由引理2以及确定一些二次方程在有限域上的解的个数，唐灯等首先得到了f的微商的一阶非线性度的下界。然后，通过引理1得到了最简形式的PS类Bent函数的一个二阶非线性度的下界。

定理 2[15]：设 n=2k，f∈ Bn是式（5）所定义的函数，则：

注意，由式（29）给定的f∈Bn属于MM类Bent函数（事实上，在F2k上的置换λ/y可以被看作是式（16）中定义的置换F），当k是偶数时，置换λ/y在F2k上是4差分均匀度；当k是奇数时，它是APN函数[21]。因此，应用置换λ/y的差分均匀度和定理1中Tr1k(λ/y)的非线性度，可以立即得到由式（29）给出的f的一个二阶非线性度的下界，其结果和定理2相同。

3.2 例2：函数Tr1 k(xy2i+1)的一个二阶非线性度下界

在文献[13]中，Gangopadhyay等给出了一类代数次数为3的MM类Bent函数的一个二阶非线性度下界。

定理3[13]：设f(x,y)=Tr1k(xy2i+1)，其中x,y∈F2k，n=2k，n≥ 6，i是一个整数且满足 1≤ i＜ k，gcd(2k-1,2i+1)=1以及gcd(i,k)=e，则：

显然，如果gcd(2k-1,2i+1)=1，则y2i+1在F2k上是一个置换。因此，f(x,y)=Tr1k(xy2i+1)属于MM类Bent函数，y2i+1可以被看作是式（16）中定义的置换F。在文献[21]的命题3中已经证明了(k,k)函数y2i+1具有2e的差分均匀度，Tr1k(y2i+1)的非线性度为因此，通过定理1可以很容易得到函数的一个二阶非线性度下界，其结果和定理3相同。

4 一类Bent函数的一个二阶非线性度下界

利用定理1，可以得到一类Bent函数的一个二阶非线性度下界。在文献[18]中，Leander证明了布尔函数：

在F2n上是Bent函数，其中n=4r，r是奇数，α=α'β(2r+1)2，α'∈ wF2r，w ∈ F4F2，β ∈ F2n。这类函数是Canteaut（参见文献[18]）利用计算机发现的，其后Leander在文献[18]中证明了这类函数确实是一类Bent函数，且属于MM类。事实上，Leander证明了由式（33）定义的函数在某些线性变换下等价于：

在F22r上是一个置换，且：

目前，还没有这类Bent函数的二阶非线性度下界的研究结果，由定理1可以得到这类函数的一个二阶非线性度下界。为此，下面阐述推导下界所需的一些基本结论。

定理4[24]：设F(x,y)=(x3+y3,(x+y)3+y3)，其中r是奇数，x,y∈F2r，则F(x,y)是一个4差分均匀度置换，它的任意一个组合函数具有非线性度22r-1-2r。

注意，任意两个仿射等价的函数具有相同的差分均匀度和非线性度（见文献[3]）。因此，根据定理4和文献[18]的引理7，有如下推论。

推论1：设F(x,y)=(x3+y3+x,(x+y)3+y3+y)，其中r是奇数，x, y∈F2r，则F(x,y)是一个4-差分置换，它的任意一个组合函数具有非线性度22r-1-2r。

下面给出并证明这一节的主要结果。

定理5：设f∈Bn是由式（33）所定义的函数，有：

证明：由文献[18]，可知f仿射等价于由式（34）所定义的函数f '，因此f和f '具有相同的二阶非线性度（参见文献[3]）。所以，为了得到f的一个二阶非线性度下界，只需要得到f '的一个二阶非线性度下界。由推论1可知，置换π(x1,x3)在F2r×F2r上是4-差分的，且其任意一个组合函数具有非线性度22r-1-2r。因此，通过定理1可以很容易得到：

5 结 语

本文给出了MM类Bent函数的一个二阶非线性度下界，其主要依赖于MM类Bent函数构造中所使用的置换的非线性度和差分均匀度。所有已知的MM类Bent函数的二阶非线性度下界均可看作是该下界结果的一个推论，从而极大地简化了已知MM类Bent函数的二阶非线性度下界的证明。此外，还得到了一类由Canteaut猜想、后被Leander证明的一类Bent函数的一个二阶非线性度的下界。