Maiorana-McFarland類Bent函數(shù)的一個(gè)二階非線性度下界*

余興華，羅淑丹，李 鐳

（中國電子科技集團(tuán)公司第三十研究所，四川 成都 610041）

0 引 言

布爾函數(shù)在對(duì)稱密碼學(xué)、糾錯(cuò)碼、通信系統(tǒng)和序列設(shè)計(jì)中具有廣泛應(yīng)用。二階非線性度是布爾函數(shù)的一個(gè)重要參數(shù)，不但能夠衡量布爾函數(shù)的穩(wěn)定性，而且能抵抗一些已知和潛在的密碼攻擊手段。雖然這些潛在的密碼攻擊手段目前的攻擊時(shí)間復(fù)雜度很大，但是隨著計(jì)算機(jī)科學(xué)技術(shù)的迅猛發(fā)展，將來有可能真正威脅到密碼系統(tǒng)的安全性。序列密碼中所使用布爾函數(shù)二階非線性度的攻擊方法可參見文獻(xiàn)[1-2]；分組密碼中所使用布爾函數(shù)的攻擊方法參見文獻(xiàn)[3]。由于所有n變?cè)紶柡瘮?shù)的最大二階非線性度等于長度為2n的二階Reed-Muller碼RM(2,n)的覆蓋半徑[4]，因此該參數(shù)在編碼理論中非常重要。此外，該參數(shù)與Gowers范數(shù)有關(guān)[5]。

眾所周知，當(dāng)變?cè)獋€(gè)數(shù)n為偶數(shù)時(shí)，Bent函數(shù)[6]具有最高的1階非線性度2n-1-2n/2-1。Bent函數(shù)是組合中一類非常重要的研究對(duì)象，與差集[7]直接相關(guān)；Bent函數(shù)可以用來構(gòu)造和設(shè)計(jì)具有良好性能的糾錯(cuò)碼[8]；Bent函數(shù)可以被修改為具有高非線性度的平衡布爾函數(shù)[9-10]，但這種平衡布爾函數(shù)具有較弱的快速代數(shù)免疫度[2,11]。對(duì)于布爾函數(shù)二階非線性度的研究，目前沒有已知太多結(jié)果，因?yàn)橛?jì)算變?cè)獋€(gè)數(shù)較大且代數(shù)次數(shù)較高的布爾函數(shù)的二階非線性度是非常困難的。事實(shí)上，即使給出變?cè)獋€(gè)數(shù)較大且代數(shù)次數(shù)較高的布爾函數(shù)的較緊二階非線性度下界亦非常困難。2008年，Carlet[12]給出了計(jì)算布爾函數(shù)二階非線性度下界的方法，主要依賴于布爾函數(shù)微商的非線性度?；谠摲椒?，近十年來國內(nèi)外給出了大量布爾函數(shù)的二階非線性度下界，如文獻(xiàn)[12-16]。

本文主要關(guān)注Bent函數(shù)的二階非線性度下界，因?yàn)槠渚哂凶畲蟮?階非線性度。本文推導(dǎo)得到了MM類Bent函數(shù)（參見參考文獻(xiàn)[7，17]和本文中的構(gòu)造1）的一個(gè)二階非線性度下界。該界主要依賴于MM類Bent函數(shù)構(gòu)造中所使用置換的非線性度和差分均勻度。事實(shí)上，所有已知的MM類Bent函數(shù)的二階非線性度下界，均可看作是所提方法結(jié)果的一個(gè)推論，極大地簡化了已知MM類Bent函數(shù)的二階非線性度下界的證明，如文獻(xiàn)[13，15]中最簡單的（PS）Bent函數(shù)和函數(shù)的二階非線性度下界。此外，還得到了一類由Canteaut猜想、被Leander[18]證明的一類Bent函數(shù)的二階非線性度的一個(gè)下界。

本文主要內(nèi)容安排如下。第2章主要介紹一些符號(hào)和所需要的預(yù)備知識(shí)；第3章基于研究MM類Bent函數(shù)中使用的置換的非線性度和差分均勻度，給出計(jì)算MM類Bent函數(shù)的二階非線性度下界的一個(gè)系統(tǒng)方法；第4章給出一類屬于MM類Bent函數(shù)的一個(gè)二階非線性度的下界；第5章對(duì)全文進(jìn)行總結(jié)概括。

1 預(yù)備知識(shí)

令F2n為有限域F2={0,1}上的n維向量空間，F(xiàn)2n是階為2n的有限域。對(duì)任意a=(a1,…,an)∈F2n，其支撐集定義為{1≤i≤n:ai=1}，漢明重wt(a)定義為其支撐集的大小（勢(shì)），即wt(a)=|sup p(a)|。一個(gè)布爾函數(shù)是指從F2n到F2的映射，所有n變?cè)牟紶柡瘮?shù)的集合記作Bn。n變?cè)紶柡瘮?shù)的支撐集定義為集合：{x∈F2n:f(x) ≠ 0}。n變?cè)紶柡瘮?shù)f(x1,…,xn)的基本表示方法為它的真值表，即：

眾所周知，Bn中的任何布爾函數(shù)f可以由F2上的多元多項(xiàng)式唯一表示，稱為代數(shù)正規(guī)型（ANF），形式如下：

其中，au∈F2，u=(u1,…,un)，它的代數(shù)次數(shù)記作deg( f )，指滿足au≠ 0的wt(u)的最大值。

向量空間F2n與有限域F2n同構(gòu)。事實(shí)上，如果 (λ1,λ2,…,λn)是 F2n上的一組基，則對(duì)于 F2n上的每個(gè)元素 x，都可以被唯一表示成 x=x1λ1+x2λ2+…+xnλn∈F2n。于是，F(xiàn)2n上的每一個(gè)元素都可以映射成一個(gè)n長的二元向量。顯然，元素0∈F2n映射成F2n上的全零向量。因此，任意一個(gè)n變?cè)牟紶柡瘮?shù)都可以在F2n上定義，并且被唯一表示成一元多項(xiàng)式：

其中：

n變?cè)牟紶柡瘮?shù)f的支撐集被定義為集合{x∈F2n:f (x)≠0}。當(dāng)n=2k時(shí)，有限域F2n可以被表示成F22k。因此，任意一個(gè)偶數(shù)n變?cè)牟紶柡瘮?shù)可以被看作是定義在F22k上，并能夠被唯一地表示成一個(gè)二元多項(xiàng)式：

其中x,y∈F2k，有：

兩個(gè)布爾函數(shù)f, g∈Bn之間的漢明距離記作：

f的r階非線性度定義為f與所有代數(shù)次數(shù)至多為r的n變?cè)紶柡瘮?shù)之間的最小漢明距離：

f的一階非線性度簡稱為f的非線性度，用nl( f )表示。布爾函數(shù)的非線性度可以通過f的Walsh變換計(jì)算。

假設(shè)：

并用a· x表示它們之間的點(diǎn)積，即：則f∈Bn在a∈F2n點(diǎn)的Walsh變換定義為：

在F2n上，布爾函數(shù)f在α∈F2n點(diǎn)的Walsh變換定義為：

是從F2n到F2上的跡函數(shù)。應(yīng)當(dāng)注意，對(duì)于任意布爾函數(shù)f∈Bn，由Parseval等式

當(dāng)達(dá)到這個(gè)上界，即取等號(hào)的這類函數(shù)被稱為Bent函數(shù)[6]。Bent函數(shù)只在n為偶數(shù)時(shí)存在。應(yīng)當(dāng)注意，每一個(gè)Bent函數(shù)f∈Bn的代數(shù)次數(shù)滿足：對(duì)于n≥4，deg( f )≤n/2。

正如引言中所述，很難確定一個(gè)代數(shù)次數(shù)不小于r+1的布爾函數(shù)的r階非線性度。在文獻(xiàn)[12]中，Carlet提出了一種給出n變?cè)紶柡瘮?shù)f的r階非線性度下界的方法，主要依賴于f的微商Daf(x)=f(x)+f(x+a)，其中a∈F2n*的r-1階非線性度是已知的。

引理1[12]：設(shè)n是任意一個(gè)正整數(shù)，f是任意一個(gè)n變?cè)紶柡瘮?shù)，r是一個(gè)小于n的正整數(shù)，則：

2 MM類Bent函數(shù)的一類二階非線性度下界

將給出MM類Bent函數(shù)的二階非線性度的一個(gè)下界。這類Bent函數(shù)是由J.A. Maiorana和R.L.McFarland（參見文獻(xiàn)[7，17]）獨(dú)立發(fā)現(xiàn)的，其中包括大量的Bent函數(shù)。首先回顧MM類Bent函數(shù)的構(gòu)造。

構(gòu)造1：設(shè)n=2k是偶數(shù)，則所有形如：

的布爾函數(shù)是Bent函數(shù)，其中x,y∈F2，F(xiàn)是F2k上的任意一個(gè)置換，g是任意一個(gè)k變?cè)紶柡瘮?shù)。

給定一個(gè)正整數(shù)n，從F2n到它自身的一個(gè)映射，通常被稱為一個(gè)(n,n)-函數(shù)。設(shè)G是一個(gè)(n,n)-函數(shù)，則定義為G(x)=(g1(x),…,gn(x))的n變?cè)紶柡瘮?shù)g1(x),…,gn(x)為G的分量函數(shù)。此外，若 (β1,β2,…,βn)=β ∈ F2n是 G 的分量函數(shù)的不全為零的系數(shù)，則由它們構(gòu)成的線性組合布爾函數(shù)稱為G的組合函數(shù)，可以簡單記成β·G。G的代數(shù)次數(shù)等于它分量函數(shù)的最大代數(shù)次數(shù)，因此等于其組合函數(shù)的最大代數(shù)次數(shù)。式（16）中的f的代數(shù)次數(shù)等于deg( F )+1，其中置換F可以看作一個(gè)(n,n)函數(shù)。非線性度nl(G)定義為G的所有組合函數(shù)的最小非線性度，G的非線性度上界為如果非線性度達(dá)到這個(gè)上界，則稱G為幾乎Bent（Almost Bent，AB）函數(shù)。顯然，AB函數(shù)僅當(dāng)n為奇數(shù)時(shí)存在。當(dāng)n為偶數(shù)時(shí)，nl(G)的最佳已知值G當(dāng) 用于分組密碼系統(tǒng)時(shí)，為了衡量G抵抗差分攻擊[20]的能力，Nyberg[21]引入了一種稱為差分均勻度的概念，定義為：k

顯然，最小的差分均勻度是2。若δG=2，則稱G為幾乎完美非線性（Almost Perfect Nonlinear，APN）函數(shù)。

現(xiàn)在給出由式（16）定義的MM類Bent函數(shù)的一個(gè)二階非線性度下界，其在很大程度上依賴于δF的大小和(k,k)置換F的非線性度。

定理1：設(shè)n=2k，設(shè)f(x,y)=F(x)·y+g(x)是式（16）所定義的MM類Bent函數(shù)，則：

證明：當(dāng) (α,β)=(0,0)時(shí)，nl(D(α,β)f )=0。對(duì)于任意一對(duì) (α,β)∈

現(xiàn) 在 考 慮 D(α,β)f在 點(diǎn) 對(duì) (a,b)∈ F2k×F2k處 的Walsh變換，由定義得：

考慮 WD(α,β)f(a,b)的以下兩種情況。

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

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

3 應(yīng)用

作為定理1的直接應(yīng)用，下面將給出兩類MM類Bent函數(shù)一個(gè)二階非線性度下界簡單而直接的證明。

3.1 例1：最簡單的PS類Bent函數(shù)的一類二階非線性度下界

這類Bent函數(shù)由Dillon[7]引入，指的是支撐集由F22k上兩兩不相交的2k-1或2k-1+1個(gè)k維子空間組成的Bent函數(shù)?！安幌嘟弧币馕吨魏蝺蓚€(gè)這種子空間的交集為零空間。2011年，Carlet[22]第一次給出了最簡形式的PS類Bent函數(shù)的r階非線性度的一個(gè)下界，其中2≤r≤k-1。最簡形式的PS類Bent函數(shù)定義如下：

下面先給出后文所需的幾個(gè)引理。

引理2[23]：設(shè)k是任意一個(gè)正整數(shù)，函數(shù)Tr1k(λ/y)是定義在F2k上的一個(gè)布爾函數(shù)，其中λ∈F*2k，則該函數(shù)的Walsh譜能夠取得區(qū)間[-2k/2+1+1,2k/2+1+1]上所有能夠被4整除的數(shù)。

方便起見，本文定義：

顯然，當(dāng)k為偶數(shù)時(shí)，有tk=2k/2+1。

由引理2以及確定一些二次方程在有限域上的解的個(gè)數(shù)，唐燈等首先得到了f的微商的一階非線性度的下界。然后，通過引理1得到了最簡形式的PS類Bent函數(shù)的一個(gè)二階非線性度的下界。

定理 2[15]：設(shè) n=2k，f∈ Bn是式（5）所定義的函數(shù)，則：

注意，由式（29）給定的f∈Bn屬于MM類Bent函數(shù)（事實(shí)上，在F2k上的置換λ/y可以被看作是式（16）中定義的置換F），當(dāng)k是偶數(shù)時(shí)，置換λ/y在F2k上是4差分均勻度；當(dāng)k是奇數(shù)時(shí)，它是APN函數(shù)[21]。因此，應(yīng)用置換λ/y的差分均勻度和定理1中Tr1k(λ/y)的非線性度，可以立即得到由式（29）給出的f的一個(gè)二階非線性度的下界，其結(jié)果和定理2相同。

3.2 例2：函數(shù)Tr1 k(xy2i+1)的一個(gè)二階非線性度下界

在文獻(xiàn)[13]中，Gangopadhyay等給出了一類代數(shù)次數(shù)為3的MM類Bent函數(shù)的一個(gè)二階非線性度下界。

定理3[13]：設(shè)f(x,y)=Tr1k(xy2i+1)，其中x,y∈F2k，n=2k，n≥ 6，i是一個(gè)整數(shù)且滿足 1≤ i＜ k，gcd(2k-1,2i+1)=1以及gcd(i,k)=e，則：

顯然，如果gcd(2k-1,2i+1)=1，則y2i+1在F2k上是一個(gè)置換。因此，f(x,y)=Tr1k(xy2i+1)屬于MM類Bent函數(shù)，y2i+1可以被看作是式（16）中定義的置換F。在文獻(xiàn)[21]的命題3中已經(jīng)證明了(k,k)函數(shù)y2i+1具有2e的差分均勻度，Tr1k(y2i+1)的非線性度為因此，通過定理1可以很容易得到函數(shù)的一個(gè)二階非線性度下界，其結(jié)果和定理3相同。

4 一類Bent函數(shù)的一個(gè)二階非線性度下界

利用定理1，可以得到一類Bent函數(shù)的一個(gè)二階非線性度下界。在文獻(xiàn)[18]中，Leander證明了布爾函數(shù)：

在F2n上是Bent函數(shù)，其中n=4r，r是奇數(shù)，α=α'β(2r+1)2，α'∈ wF2r，w ∈ F4F2，β ∈ F2n。這類函數(shù)是Canteaut（參見文獻(xiàn)[18]）利用計(jì)算機(jī)發(fā)現(xiàn)的，其后Leander在文獻(xiàn)[18]中證明了這類函數(shù)確實(shí)是一類Bent函數(shù)，且屬于MM類。事實(shí)上，Leander證明了由式（33）定義的函數(shù)在某些線性變換下等價(jià)于：

在F22r上是一個(gè)置換，且：

目前，還沒有這類Bent函數(shù)的二階非線性度下界的研究結(jié)果，由定理1可以得到這類函數(shù)的一個(gè)二階非線性度下界。為此，下面闡述推導(dǎo)下界所需的一些基本結(jié)論。

定理4[24]：設(shè)F(x,y)=(x3+y3,(x+y)3+y3)，其中r是奇數(shù)，x,y∈F2r，則F(x,y)是一個(gè)4差分均勻度置換，它的任意一個(gè)組合函數(shù)具有非線性度22r-1-2r。

注意，任意兩個(gè)仿射等價(jià)的函數(shù)具有相同的差分均勻度和非線性度（見文獻(xiàn)[3]）。因此，根據(jù)定理4和文獻(xiàn)[18]的引理7，有如下推論。

推論1：設(shè)F(x,y)=(x3+y3+x,(x+y)3+y3+y)，其中r是奇數(shù)，x, y∈F2r，則F(x,y)是一個(gè)4-差分置換，它的任意一個(gè)組合函數(shù)具有非線性度22r-1-2r。

下面給出并證明這一節(jié)的主要結(jié)果。

定理5：設(shè)f∈Bn是由式（33）所定義的函數(shù)，有：

證明：由文獻(xiàn)[18]，可知f仿射等價(jià)于由式（34）所定義的函數(shù)f '，因此f和f '具有相同的二階非線性度（參見文獻(xiàn)[3]）。所以，為了得到f的一個(gè)二階非線性度下界，只需要得到f '的一個(gè)二階非線性度下界。由推論1可知，置換π(x1,x3)在F2r×F2r上是4-差分的，且其任意一個(gè)組合函數(shù)具有非線性度22r-1-2r。因此，通過定理1可以很容易得到：

5 結(jié) 語

本文給出了MM類Bent函數(shù)的一個(gè)二階非線性度下界，其主要依賴于MM類Bent函數(shù)構(gòu)造中所使用的置換的非線性度和差分均勻度。所有已知的MM類Bent函數(shù)的二階非線性度下界均可看作是該下界結(jié)果的一個(gè)推論，從而極大地簡化了已知MM類Bent函數(shù)的二階非線性度下界的證明。此外，還得到了一類由Canteaut猜想、后被Leander證明的一類Bent函數(shù)的一個(gè)二階非線性度的下界。