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函數的一個二階非線性度的下界。