《現(xiàn)代密碼學(xué)》課件第3章

3.1頻譜理論簡介

3.2布爾函數(shù)的非線性準(zhǔn)則

3.3相關(guān)免疫函數(shù)

3.4Bent函數(shù)及其性質(zhì)第3章密碼函數(shù)3.1頻譜理論簡介頻譜理論被廣泛地應(yīng)用于數(shù)字信號處理、邏輯設(shè)計、模式識別、編碼理論以及生物醫(yī)學(xué)等領(lǐng)域。20世紀(jì)80年代，肖國鎮(zhèn)和Massey首先將頻譜技術(shù)應(yīng)用于密碼學(xué)的研究中[1]，證明了布爾函數(shù)的相關(guān)免疫性的特征化定理；Rupple利用Walsh譜給出了最佳仿射逼近的方法，并用該方法分析了DES密碼中的S盒[2]；Blahut利用有限域上的離散傅立葉變換(DFT)證明了周期序列的線性復(fù)雜度等于它的一個周期的DFT的漢明重量[3]，該定理在分析碼的最小重量和碼的最小距離限時起重要作用。20世紀(jì)80年代末，肖國鎮(zhèn)和丁存生等系統(tǒng)地提出了基于頻譜技術(shù)的序列密碼的穩(wěn)定性理論，對序列密碼的分析與設(shè)計提出了一系列全新的概念[4]。馮登國的博士論文《頻譜理論及其在通信保密技術(shù)中的應(yīng)用》較全面地探討了頻譜理論在密碼學(xué)中的應(yīng)用[6]。近年來，國內(nèi)外不少學(xué)者在頻譜理論及其應(yīng)用方面做了大量研究工作，從單輸出函數(shù)到多輸出函數(shù)，從布爾函數(shù)到多值函數(shù)，從線性逼近到高階逼近等方面都有很好的成果。頻譜技術(shù)在對密碼函數(shù)的特征刻畫以及密碼分析方面顯示出了獨特的優(yōu)越性。3.1.1布爾函數(shù)

n個變元的布爾函數(shù)f(x)是從GF(2)n到GF(2)的一個函數(shù)或映射，記作f(x)：GF(2)n→GF(2)。由于此函數(shù)的輸出只有兩種取值，因此又被稱為開關(guān)函數(shù)。

通常意義上的密碼函數(shù)有多個取值，因此又稱為多輸出函數(shù)f(x)：GF(2)n→GF(2)m，m∈Z+。它可以用一組布爾函數(shù)來表示，即

f(x)=(f1(x)，f2(x)，…，fm(x))

其中，每個fi(x)(i=1，2，…，m)是一個n元布爾函數(shù)。

布爾函數(shù)有多種表示形式，本節(jié)主要介紹真值表表示、小項表示和多項式表示。

1.真值表表示

n元函數(shù)的取值由自變量x=(x1，x2，…，xn)唯一確定。函數(shù)的真值表是指由函數(shù)自變量所有可能的取值及其對應(yīng)的函數(shù)值所構(gòu)成的表格。習(xí)慣上將自變量用二進(jìn)制表示，并由小到大排列。此時將所有函數(shù)值構(gòu)成的向量記作f，稱為函數(shù)值矢量。f中1的個數(shù)稱為函數(shù)f的漢明重量(HammingWeight)，記作WH(f)。如果自變量取遍所有可能的2n個輸入時，函數(shù)輸出0與1的個數(shù)相等，即WH(f)=2n－1，則稱f為平衡函數(shù)。

【例3-1】設(shè)f(x)：GF(2)3→GF(2)，其真值表如表3-1所示。表3-1中所表示的三元函數(shù)的函數(shù)值矢量為f＝(01010110)，重量WH(f)=4，是一個平衡函數(shù)。

2.小項表示對于xi，ci∈GF(2)，定義

，則有

設(shè)整數(shù)c(0≤c≤2n－1)的二進(jìn)制表示為c1c2…cn，約定

，則xc具有“正交性”，即：

因而有

(3-1)

式(3-1)稱為函數(shù)f的小項表示，其中每一項f(c1，c2，…，cn)稱為一個小項，這里的加指模2加。

【例3-2】表3-1中的布爾函數(shù)f(x)的小項表示為

(3-2)

3.多項式表示除了真值表表示和小項表示之外，布爾函數(shù)更為常見的表示方法是多項式表示。我們給n個變元所有可能的乘積項乘以GF(2)上的系數(shù)并相加，再按變元的升冪及下標(biāo)的詞典序?qū)懗?，便可得到布爾函?shù)多項式表示的一般形式如下：

或

(3-3)

式(3-3)稱為f(x)的代數(shù)正規(guī)型，任一確定的布爾函數(shù)的代數(shù)正規(guī)型是唯一的。其中，乘積項

的次數(shù)為r，非零常數(shù)項的次數(shù)定義為0，而常數(shù)項0的次數(shù)定義為－∞。布爾函數(shù)f(x)的次數(shù)定義為f(x)的代數(shù)正規(guī)型中非零項的最大次數(shù)，記作f或deg(f)。當(dāng)f=1時，稱f為線性布爾函數(shù)；當(dāng)f≥2時，稱f為非線性布爾函數(shù)。在n元布爾函數(shù)f(x)的代數(shù)正規(guī)型的每一項中，變量xi(1≤i≤n)可能出現(xiàn)，也可能不出現(xiàn)，因而總共有2n種可能的項，而每一項的系數(shù)可以取值0或1，所以，n個變元的布爾函數(shù)共有個。

【例3-3】如果將代入式(3-2)，則可將例3-2中的函數(shù)f(x)變形為GF(2)上的多項式。

3.1.2Walsh變換

1.Walsh變換的定義

定義3-1(Walsh變換)

設(shè)f(x)：GF(2)n→GF(2)，x=(x1，x2，…，xn)，ω=(ω1,ω2,…,ωn)∈GF(2n)，x與ω的點積定義為x·ω=ω1x1+ω2x2+…+ωnxn，簡記作ω·x。則n個變元的布爾函數(shù)f(x)在點ω的第一種Walsh變換(線性Walsh譜)定義為

第二種Walsh變換(循環(huán)Walsh譜)定義為

定理3-1(反演公式)

兩種Walsh變換的逆變換分別為

和

根據(jù)兩種譜的定義以及(－1)f(x)=1－2f(x)，易證明兩種Walsh譜之間存在定理3-2所述的關(guān)系。

定理3-2

兩種Walsh譜值之間滿足：

2.Walsh譜的性質(zhì)

1)平移性設(shè)f(x)：GF(2)n→GF(2)，對α∈GF(2)n，有

2)線性性設(shè)f(x)：GF(2)n→GF(2)，g(x)：GF(2)n→GF(2)，則

3)Parseval公式設(shè)f(x)是n元布爾函數(shù)，則

這個公式有時又被稱為能量守恒定理。證明：

4)Plancheral公式

其中，WH(f)表示f的漢明重量，即集合{x∈GF(2)n|f(x)=1}中元素的個數(shù)。證明：

5)卷積性質(zhì)設(shè)f(x)：GF(2)n→GF(2)，g(x)：GF(2)n→GF(2)，則

(3-4)

根據(jù)式(3-4)以及反演公式，可以得到如下的卷積定理。定理3-3

其中，f*f表示f與自身的卷積，即。

6)Wiener-Khinchin公式定義3-2設(shè)f(x)：GF(2)n→GF(2)，則稱為函數(shù)f(x)的自相關(guān)函數(shù)。函數(shù)的Walsh譜值與自相關(guān)函數(shù)間存在如下關(guān)系：

(3-5)式(3-5)又被稱為Wiener-Khinchin公式。以上結(jié)論的證明是比較容易的，這里只給出了Parseval公式和Plancheral公式的證明，其余留給讀者作為練習(xí)。設(shè)f(x)：GF(2)n→GF(2)在點ω的循環(huán)譜為S〈f〉(ω)，則根據(jù)定義，有

即

從而

(3-6)

(3-7)這里，形式|{A}|表示集合A中的元素個數(shù)；P(f(x)=ω·x)表示f(x)與ω·x相等的概率。式(3-6)及(3-7)表明，Walsh譜本質(zhì)上反映了布爾函數(shù)與線性函數(shù)之間的相關(guān)程度。

3．Walsh函數(shù)系

定義3-3(特征函數(shù))

設(shè)G為有限Abel群，I為其單位元，U是所有模數(shù)為1的復(fù)數(shù)構(gòu)成的乘法群。函數(shù)Φ：G→U，如果對g1，g2∈G，Φ滿足則稱Φ是G的一個特征函數(shù)。定義函數(shù)的乘法運算“·”為

(Φ1·Φ2)(g)=Φ1(g)Φ2(g)易驗證G的所有特征函數(shù)的集合在函數(shù)的乘法運算下構(gòu)成另一個Abel群，且。如果G=(g)為n階循環(huán)群，則由下列函數(shù)組成：其中，，k=0，1，…，n-1，0≤j≤n－1。定義3-4(Walsh函數(shù)系)

設(shè)x=(x1，x2，…，xn)，ω=(ω1，ω2，…，ωn)∈GF(2)n，x與ω的點積為ω·x，則函數(shù)系

Qω(x)=(－1)ω·x構(gòu)成向量空間GF(2)n上的特征函數(shù)系，稱為Walsh函數(shù)系。

Walsh函數(shù)系具有如下性質(zhì):

(1)對稱性：Qω(x)=Qx(ω)(2)正交性：

上節(jié)介紹的反演公式實際上是將函數(shù)用Walsh函數(shù)系展開的結(jié)果。事實上，可以將函數(shù)的線性Walsh譜和循環(huán)Walsh譜用Walsh函數(shù)系分別表示為相應(yīng)的反演公式分別為

(3-8)和

由式(3-8)可導(dǎo)出下列矩陣方程：矩陣方程右邊的2n×2n階矩陣稱為n階Hadamard矩陣，記作H(n)。它表示當(dāng)x與ω取遍GF(2)n中的所有值時，Qω(x)的所有取值排列成的矩陣。

【例3-4】設(shè)，

則Hadamard矩陣可以用矩陣的Kronecher積“”迭代地定義為

Hadamard矩陣具有如下性質(zhì)：

(1)根據(jù)Walsh函數(shù)系的對稱性易知，H(n)是2n×2n階對稱矩陣。

(2)引入Hadamard矩陣后，Walsh函數(shù)系的正交性可表示為其中，為2n×2n階單位陣。

(3)H(n)－1=2－nH(n)。3.1.3Chrestenson譜簡介上節(jié)中介紹的Walsh譜是對布爾函數(shù)進(jìn)行Walsh變換的結(jié)果，如果將函數(shù)的定義域和值域擴展到整數(shù)剩余類環(huán)，則需要引入Walsh的推廣形式，即Chrestenson譜，簡稱柯氏譜。

定義3-5

設(shè)f(x)：是從到ZN的多值邏輯函數(shù)，則f(x)在ω點的第一種柯氏譜(線性譜)定義為

(3-9)第二種柯氏譜(循環(huán)譜)定義為

(3-10)其中，ω，x∈

;ω·x表示ω與x的點積;

的共軛。式(3-9)和式(3-10)的反演公式分別為和

Walsh變換是柯氏變換的特殊情形，事實上，當(dāng)N=2時，Chrestenson譜就是Walsh譜?？率献V具有與Walsh譜類似的性質(zhì)：

(1)設(shè)f(x)：，則這里|S〈f〉(ω)|表示復(fù)數(shù)S〈f〉(ω)的模。

(2)設(shè)V是的一個子空間，則其中，。

(3)設(shè)f1，f2：，f1*f2表示f1和f2的卷積，則

(4)設(shè)f1，f2：，則對任意的

，當(dāng)且僅當(dāng)f1=f2時，；當(dāng)且僅當(dāng)f1=f2時，。3.2布爾函數(shù)的非線性準(zhǔn)則

研究并設(shè)計具有較好密碼學(xué)性質(zhì)的邏輯函數(shù)是對稱密碼學(xué)研究中的重要問題。序列密碼設(shè)計的關(guān)鍵是利用非線性組合部分生成滿足某些要求的好的密鑰流序列，為了能使密鑰流生成器抵抗已知的攻擊方法，必須對非線性組合部分提出一些明確的安全性要求。非線性組合部分可以用邏輯函數(shù)實現(xiàn)，因此，序列密碼的研究可以歸結(jié)為邏輯函數(shù)的研究。在分組密碼中，非線性部件S盒的設(shè)計是算法中最重要的部分。S盒本質(zhì)上是一個非線性的代替表，也可以表示為非線性的邏輯函數(shù)。邏輯函數(shù)的密碼學(xué)性質(zhì)主要包括：非線性次數(shù)、非線性度(或相干度)、線性結(jié)構(gòu)及退化性、相關(guān)免疫性、嚴(yán)格雪崩準(zhǔn)則和擴散準(zhǔn)則等幾個方面。這些準(zhǔn)則統(tǒng)稱為函數(shù)的非線性準(zhǔn)則。本節(jié)重點介紹非線性度、線性結(jié)構(gòu)和嚴(yán)格雪崩準(zhǔn)則，下一節(jié)詳細(xì)討論函數(shù)的相關(guān)免疫性。3.2.1函數(shù)的非線性度

定義3-6

設(shè)f(x)：GF(2)n→GF(2)，表示GF(2)上的所有線性布爾函數(shù)所組成的集合，布爾函數(shù)的非線性度定義為一個非負(fù)整數(shù)Nf:相應(yīng)地，函數(shù)的線性度(或相關(guān)度)定義為非負(fù)整數(shù)Cf:其中，dH(f(x)，l(x))表示f(x)與l(x)的漢明距離，在二元域中，有dH(f(x)，l(x))=WH(f(x)+l(x))

由定義易知Nf+Cf=2n。函數(shù)的非線性度可以用其Walsh譜表示。定理3-4設(shè)f(x)：GF(2)n→GF(2)的非線性度為Nf，則證明：設(shè)v∈GF(2)，由于因此因而

推論3-1定理3-5任意n元布爾函數(shù)f(x)的非線性度Nf滿足

。證明：由Parseval公式有

，從而，所以。當(dāng)取最小值時，Nf達(dá)到最大值，此時對任意ω∈GF(2)n，均有，這類函數(shù)的非線性度最大，稱為Bent函數(shù)。

定義3-7

設(shè)f(x)：GF(2)n→GF(2)，如果存在線性函數(shù)ω·x+v，ω∈GF(2)n，v∈GF(2)，使得

取得最小值，則稱ω·x+v是f(x)的一個最佳線性逼近。布爾函數(shù)的最佳線性逼近可能不是唯一的，在密碼分析中人們需要的是漢明重量盡可能小的線性逼近。

Walsh譜值為函數(shù)的非線性度量提供了依據(jù)，利用Walsh譜也可以計算出布爾函數(shù)的最佳線性逼近，從而為密碼分析提供幫助。Rueppel用信息論的方法推導(dǎo)出了用Walsh譜值描述的最佳逼近定理［2］。參考文獻(xiàn)［7］中給出了用循環(huán)譜描述的逼近定理，并提出了利用循環(huán)譜求最佳線性逼近的方法。

定理3-6

令Pf(ω·x)為函數(shù)f(x)與線性函數(shù)ω·x相等的概率，則有

(3-11)

(3-12)

證明：根據(jù)循環(huán)Walsh譜的定義，有從而得到式(3-11)，再由兩種譜值的關(guān)系，可證明式(3-12)成立。由定理3-6易得到如下結(jié)論。

定理3-7

令則有:

(1)如果S〈f〉(ω)≥0，則ω·x為f(x)的最佳線性逼近，且符合(與f(x)相等)的概率為

(2)如果S〈f〉(ω)<0，則ω·x+1為f(x)的最佳線性逼近，且符合的概率為定理3-7事實上給出了求最佳線性逼近的算法。3.2.2線性結(jié)構(gòu)與函數(shù)的退化性非線性度描述了布爾函數(shù)與線性函數(shù)的相似程度，線性函數(shù)是密碼學(xué)意義上較弱的一類函數(shù)。另一類密碼學(xué)意義上較弱的函數(shù)是具有線性結(jié)構(gòu)的函數(shù)。

定義3-8

設(shè)f(x)：GF(2)n→GF(2)，α∈GF(2)n，如果對任意x∈GF(2)n，均有f(x+α)+f(x)=f(α)+f(0)則稱α是f(x)的一個線性結(jié)構(gòu)。當(dāng)f(α)+f(0)=0時，稱α為不變線性結(jié)構(gòu)；當(dāng)f(α)+f(0)=1時，稱α為恒變線性結(jié)構(gòu)。設(shè)f(x)的全體線性結(jié)構(gòu)集為Uf，

表示不變線性結(jié)構(gòu)全體，

表示恒變線性結(jié)構(gòu)全體，則，且易驗證Uf構(gòu)成GF(2)n的一個線性子空間，而

構(gòu)成Uf的線性子空間。對，有f(x+α+β)+f(x)=f(x+α+β)+1+f(x+α)=1所以

，

，從而有

。定理3-8

設(shè)α∈GF(2)n，則(i=0或1)當(dāng)且僅當(dāng)對任意ω∈GF(2)n且ω·α=i+1，有S〈f〉(ω)=0。證明：設(shè)，則由定義f(x+α)=f(x)+i，有當(dāng)ω·α+i≠0，即ω·α=i+1時，有S〈f〉(ω)=0。反之，對任意α∈GF(2)n，由Walsh譜值的平移性，有S〈f(x+α)〉(ω)=(－1)ω·αS〈f〉(ω)，而S〈f+i〉(ω)=(－1)iS〈f〉(ω)。當(dāng)ω·α=i時，有S〈f(x+α)〉(ω)=S〈f+i〉(ω)。當(dāng)ω·α≠i，即ω·α=i+1時，如果S〈f〉(ω)=0，則有S〈f(x+α)〉(ω)=S〈f+i〉(ω)=0，因此對一切ω∈GF(2)n，有S〈f(x+α)〉(ω)=S〈f+i〉(ω)。根據(jù)Walsh譜值的反演公式知，對任意x∈GF(2)n，f(x+α)=f(x)+i，所以。以下定理描述了

的結(jié)構(gòu)，這里用〈A〉表示由集合A生成的線性子空間，〈A〉⊥表示A的正交子空間。

定理3-9

是由GF(2)n中循環(huán)Walsh譜值非零的元素構(gòu)成的線性子空間的正交空間，即

證明：設(shè)，對ω∈GF(2)n，如果ω·α=1，則由定理3-8和S〈f〉(ω)=0，故對任意ω∈{ω∈GF(2)n|S〈f〉(ω)≠0}，均有ω·α=0，所以α∈〈{ω∈GF(2)n|S〈f〉(ω)≠0}〉⊥由α的任意性知:反之，設(shè)α∈〈{ω∈GF(2)n|S〈f〉(ω)≠0}〉⊥，則對，均有ω·α=0，從而所以，對，即ω·α≠0，有而所以

，即S〈f〉(ω)=0，由定理3-8可知

。

引理3-1

設(shè)f(x)：GF(2)n→GF(2)的非線性度為Nf，記NS(f)=|{ω∈GF(2)n|S〈f〉(ω)=0}|則證明：根據(jù)Parseval公式，有因而變形得由定理3-4知，，故

引理3-1表明，Nf越大，則非零譜值個數(shù)2n－NS(f)越多，因此從密碼學(xué)意義上講，應(yīng)該盡量選擇非線性度較大，或者非零譜值數(shù)目較多的函數(shù)。

定理3-10

設(shè)f(x)：GF(2)n→GF(2)的線性結(jié)構(gòu)集

，非線性度為Nf，記dimUf=k，則其中，dimUf表示向量空間Uf的維數(shù)。證明：由引理3-1知，證明上式等價于證明2n－NS(f)≤2n－k。由于

是k維線性子空間，若

，則

是一個k－1維線性子空間。在

中取線性無關(guān)的向量β1，β2，…，βk－1，再取

，易驗證β1，β2，…，βk－1，βk在GF(2)上線性無關(guān)。又f(x)=f(x+β1)=f(x+β2)=…=f(x+βk－1)=1+f(x+βk)則因此，如果S〈f〉(ω)≠0，則β1·ω=…=βk－1·ω=1+βk·ω=0。由于β1，β2，…，βk－1，βk線性無關(guān)，因而此方程組有2n－k個解，從而|{ω∈GF(2)n|S〈f〉(ω)≠0}|=2n－NS(f)≤2n－k若

，則

。用類似方法可證明2n－NS(f)≤2n－k。定理3-10表明了線性結(jié)構(gòu)和非線性度之間存在著一種制約關(guān)系。在密碼函數(shù)的設(shè)計中，常常會考慮到函數(shù)與其變元之間的代數(shù)無關(guān)性，對于布爾函數(shù)f(x)：GF(2)n→GF(2)，若存在變元

，使得對一切α1，α2，…，αr∈GF(2)，有則稱f(x)與變元

代數(shù)無關(guān)，此時可以認(rèn)為一個n元函數(shù)退化成為n－r元函數(shù)。函數(shù)退化性的精確定義如定義3-9。

定義3-9

設(shè)f(x)：GF(2)n→GF(2)，如果存在GF(2)上的一個k×n(k<n)階矩陣D和GF(2)k到GF(2)上的一個函數(shù)g(y)，使得f(x)=g(Dx)=g(y)，則稱f(x)是退化的，其中y=Dx。布爾函數(shù)的退化性對密碼分析有著重要意義，可以減少密碼分析的難度。下面是關(guān)于退化性的一些結(jié)論。

引理3-2

設(shè)f(x)：GF(2)n→GF(2)，若，則f(x)能退化為n－r元函數(shù)。證明：由于

是GF(2)n的線性子空間，進(jìn)而是GF(2)n的加法子群，故GF(2)n可分解為其中，S為代表元集，|S|=2n－r。直接可驗證f(x)在

的每個陪集上取值為常數(shù)。定義映射φ：S→GF(2)n－r，φ(β)=Dβ，其中D是由

的正交空間的一組基所構(gòu)成的(n－k)×n階矩陣，設(shè)β1，β2∈S，若φ(β1)=φ(β2)，則D(β1－β2)=0，即，說明β1=β2，從而φ是單射，又|S|=2n－r=|GF(2)n－r|，故φ是雙射。定義函數(shù)g(y)：GF(2)n－r→GF(2)，g(y)=f(φ－1(y))，則對任意的β∈S，有g(shù)(Dβ)=f(φ－1(Dβ))=f(β)。對任意的x∈GF(2)n，存在β∈S和使x=β+d，因此Dx=D(β+d)=Dβ。又f(x)在的每個陪集上取值為常數(shù)，所以f(x)=f(β)=g(Dβ)=g(Dx)，即f(x)能退化為n－r元函數(shù)。

定理3-11

設(shè)f(x)：GF(2)n→GF(2)，f(x)的線性結(jié)構(gòu)集為

，則

當(dāng)且僅當(dāng)f(x)能且至多能退化為n－k元函數(shù)。證明：設(shè)f(x)能且至多能退化為n－k元函數(shù)，則由定義3-9知，存在(n－k)×n階矩陣D和函數(shù)g(y)：GF(2)n－k→GF(2)，使得對一切x∈GF(2)n，f(x)=g(Dx)=g(y)，D的秩為n－k。令kerD={x∈GF(2)n|Dx=0}，顯然kerD是GF(2)n的一個線性子空間，且dim(kerD)=k。下證

。設(shè)

，則對任意的x∈GF(2)n，有f(x+α)=f(x)，又f(x+α)=g(D(x+α))=g(y+Dα)，f(x)=g(y)所以g(y+Dα)=g(y)。由于g(y)不能再退化，因此由引理3-2得Dα=0，即α∈kerD，故

反之，設(shè)，則由引理3-2知f(x)能退化為n－k元函數(shù)。再由充分性知，f(x)能且至多能退化為n－k元函數(shù)。定理3-11表明，布爾函數(shù)的退化性與線性結(jié)構(gòu)有關(guān)。事實上，退化性的研究可以歸結(jié)為線性結(jié)構(gòu)的研究。3.2.3嚴(yán)格雪崩準(zhǔn)則及擴散準(zhǔn)則定義3-10設(shè)f(x)：GF(2)n→GF(2)，對于α∈GF(2)n，f(x)在α點的差分函數(shù)定義為Δf(x，α)=f(x+α)－f(x)其中，Δf(x，α)的取值分布稱為f(x)在α點的差分分布；f(x)在所有點的差分函數(shù)值的分布統(tǒng)稱為f(x)的差分分布。為了抵御差分分析，要求差分函數(shù)在其值域中取每個值的概率相等，對于布爾函數(shù)，即要求對任意的α∈GF(2)n，有或Δf(x，α)為平衡函數(shù)。這稱為差分分布的均勻性。滿足差分均勻性的函數(shù)又被稱為完全非線性函數(shù)。

例3-5

設(shè)f(x)：GF(2)3→GF(2)，f(x)=x1x2+x3，令α=(011)，則Δf(x，α)=x1+1是平衡函數(shù)，故f(x)在α點的差分分布是均勻的。差分分布的均勻性是一個過于強的性質(zhì)，對于較復(fù)雜的函數(shù)，常常難以滿足。下面我們對這一概念稍作弱化，考慮一類特殊差分分布的均勻性，稱為雪崩與擴散。

定義3-11

設(shè)f(x)：GF(2)n→GF(2)，如果對任意e∈GF(2)n，且WH(e)=1，Δf(x，e)=f(x+e)+f(x)均為平衡布爾函數(shù)，則稱f(x)滿足嚴(yán)格雪崩準(zhǔn)則SAC(StrictAvalancheCriterion)。如果一個函數(shù)滿足嚴(yán)格雪崩準(zhǔn)則，則當(dāng)其輸入改變一比特時，輸出將有一半發(fā)生變化，這正是分組密碼中S盒的設(shè)計準(zhǔn)則之一。由定義知，函數(shù)f(x)滿足嚴(yán)格雪崩準(zhǔn)則，當(dāng)且僅當(dāng)對

e∈GF(2)n，WH(e)=1，自相關(guān)函數(shù)Rf(e)=0，又根據(jù)式(3-5)，當(dāng)且僅當(dāng)。

定義3-12

設(shè)f(x)：GF(2)n→GF(2)，如果存在α∈GF(2)n，使得Δf(x，α)=f(x+α)－f(x)是一個平衡布爾函數(shù)，則稱f(x)關(guān)于α滿足擴散準(zhǔn)則。如果對α∈GF(2)n，1≤WH(α)≤k，f(x)關(guān)于α滿足擴散準(zhǔn)則，則稱f(x)滿足k次擴散準(zhǔn)則。

f(x)關(guān)于α滿足擴散準(zhǔn)則當(dāng)且僅當(dāng)Rf(α)=0或。

f(x)滿足k次擴散準(zhǔn)則當(dāng)且僅當(dāng)對任意的α∈GF(2)n，1≤WH(α)≤k，有Rf(α)=0或。由上述定義可見，差分均勻性是最強的條件，嚴(yán)格雪崩準(zhǔn)則和擴散準(zhǔn)則分別對差分函數(shù)Δf(x，α)中的α進(jìn)行了不同程度的限制。嚴(yán)格雪崩準(zhǔn)則實際上就是１次擴散準(zhǔn)則，而滿足k+1次擴散準(zhǔn)則的函數(shù)一定滿足k次擴散準(zhǔn)則。若一個n元函數(shù)滿足n次擴散準(zhǔn)則，則它就是差分均勻函數(shù)，或完全非線性函數(shù)。下面的定理給出了函數(shù)滿足嚴(yán)格雪崩準(zhǔn)則的判別方法及構(gòu)造方法。

定理3-12

設(shè)f(x)：GF(2)n→GF(2)，f(x)滿足嚴(yán)格雪崩準(zhǔn)則當(dāng)且僅當(dāng)對任意j∈{1，2，…，n}，如果可將f(x)表示為其中，gj：GF(2)n－1→GF(2)，hj：GF(2)n－1→GF(2)為n－1元布爾函數(shù)，則hj，j∈{1，2，…，n}都是平衡函數(shù)。證明：由于f(x)滿足嚴(yán)格雪崩準(zhǔn)則當(dāng)且僅當(dāng)對任意j∈{1，2，…，n}，是平衡函數(shù)，故定理成立。

定理3-13

若f(x)滿足嚴(yán)格雪崩準(zhǔn)則(或k次擴散準(zhǔn)則)，l(x)為仿射函數(shù)，則f(x)+l(x)也滿足嚴(yán)格雪崩準(zhǔn)則(或k次擴散準(zhǔn)則)。有關(guān)嚴(yán)格雪崩準(zhǔn)則和擴散準(zhǔn)則的進(jìn)一步研究請參閱參考文獻(xiàn)［10］和［11］。3.3相關(guān)免疫函數(shù)3.3.1定義定義3-13設(shè)f(x)：GF(2)n→GF(2)，x1，x2，…，xn是取值在GF(2)上的獨立、均勻分布的隨機變量，如果對(a1，a2，…，am)∈GF(2)m，m≤n及a∈GF(2)，均有則稱f(x)與變元

統(tǒng)計無關(guān)。如果f(x)與x1，x2，…，xn中的任意m個都統(tǒng)計無關(guān)，則稱f(x)是m階相關(guān)免疫函數(shù)。如果f(x)是t階相關(guān)免疫函數(shù)，但不是t+1階相關(guān)免疫函數(shù)，則稱f(x)的相關(guān)免疫階為t。研究相關(guān)免疫函數(shù)的方法主要有三種：頻譜方法[1]、代數(shù)方法[12]和重量分析法[13]。本節(jié)介紹頻譜方法的主要結(jié)論。以下定理給出了函數(shù)f(x)與其變元

統(tǒng)計無關(guān)的一些等價條件。

定理3-14

設(shè)f(x)如定義3-13中所述，則下列三個條件等價：

(1)f(x)與

統(tǒng)計無關(guān)；

(2)

，1≤WH(ω)≤m，f(x)與ω·x統(tǒng)計無關(guān)；

(3)

，1≤WH(ω)≤m，f(x)+ω·x是平衡函數(shù)。證明：

(1)→(2)，由相關(guān)免疫函數(shù)的定義直接可證。

(2)→(3)，設(shè)對

，1≤WH(ω)≤m，f(x)與ω·x統(tǒng)計無關(guān)，則對i∈GF(2)，從而故f(x)+ω·x是平衡函數(shù)。

(3)→(1)，設(shè)對

，1≤WH(ω)≤m，f(x)+ω·x是平衡函數(shù)，對a，a1，a2，…，am∈GF(2)，記因為由假設(shè)條件知，對于y∈GF(2)m+1，當(dāng)y≠(0，0，…，0)或y≠(1，0，…，0)時，有所以又因而由上述兩式得NA×2m=Na，即因此，f(x)與變元

統(tǒng)計無關(guān)。

定理3-15

設(shè)f(x)如定義3-13中所述，1≤m＜n，則f(x)與變元

統(tǒng)計無關(guān)當(dāng)且僅當(dāng)對任意的

，1≤WH(ω)≤m，S〈f〉(ω)=0。

證明：由定理3-14知，f(x)與變元

統(tǒng)計無關(guān)當(dāng)且僅當(dāng)對任意

，1≤WH(ω)≤m，f(x)+ω·x是平衡函數(shù)，而f(x)+ω·x是平衡函數(shù)當(dāng)且僅當(dāng)S〈f〉(ω)=0，從而證明了定理。由以上兩定理直接可得到如下結(jié)論。

定理3-16

設(shè)f(x)如定義3-13中所述，則下列三個條件等價：

(1)f(x)是m階相關(guān)免疫函數(shù)；

(2)對任意的ω∈GF(2)n，1≤WH(ω)≤m，f(x)與ω·x統(tǒng)計無關(guān)；

(3)對任意的ω∈GF(2)n，1≤WH(ω)≤m，f(x)+ω·x是平衡函數(shù)。

定理3-17

設(shè)f(x)如定義3-13中所述，則f(x)是m階相關(guān)免疫函數(shù)當(dāng)且僅當(dāng)對任意的ω∈GF(2)n，1≤WH(ω)≤m，S〈f〉(ω)=0。由定理3-17及兩種譜值的關(guān)系易證得以下定理［1］。

定理3-18(Xiao-Massey)

設(shè)f(x)如定義3-13中所述，則f(x)是m階相關(guān)免疫函數(shù)當(dāng)且僅當(dāng)對任意的ω∈GF(2)n，1≤WH(ω)≤m，Sf(ω)=0。

定理3-19

設(shè)f(x)：GF(2)n→GF(2)，f(x)=k，如果f(x)是m階相關(guān)免疫的，則k+m≤n。定理3-19表明函數(shù)的相關(guān)免疫階與其代數(shù)次數(shù)之間存在相互制約的關(guān)系。此外，相關(guān)免疫階與函數(shù)的非線性度間也存在著制約關(guān)系，如下述定理。

定理3-20

設(shè)f(x)：GF(2)n→GF(2)，f(x)的相關(guān)免疫階為m，非線性度為Nf，f(x)的漢明重量為WH(f(x))=2mk0(k0為非負(fù)整數(shù))，則存在正整數(shù)a，使得當(dāng)k0為偶數(shù)時，a可取為偶數(shù)；k0為奇數(shù)時，a可取為奇數(shù)。3.3.2相關(guān)免疫函數(shù)的構(gòu)造相關(guān)免疫函數(shù)主要有兩種構(gòu)造方法：頻譜方法和代數(shù)方法。本節(jié)只討論一階相關(guān)免疫布爾函數(shù)的構(gòu)造方法，主要內(nèi)容來自單煒娟用代數(shù)方法研究相關(guān)免疫函數(shù)的結(jié)論［7］。

定理3-21

設(shè)f(x)：GF(2)n→GF(2)和g(x)：GF(2)n→GF(2)均為m階相關(guān)免疫函數(shù)，且g(x)f(x)=0，則f(x)+g(x)也是m階相關(guān)免疫的。證明：利用Walsh譜值的線性性和Xiao-Massey定理易證。以下將布爾函數(shù)用小項表示。設(shè)c∈GF(2)n，如果x=c，則xc=1，否則xc=0。如果n元布爾函數(shù)f(x)的重量為w，f－1(1)={c1，c2，…，cw}，ci∈GF(2)n，i=1，2，…，w，則f(x)的小項表示如下：此時稱w個向量c1，c2，…，cw為f(x)的特征向量，稱w×n階矩陣為f(x)的特征矩陣。

定理3-22

設(shè)f(x)：GF(2)n→GF(2)，則f(x)為m階相關(guān)免疫函數(shù)的必要條件是WH(f)=2mkk≥0

證明：設(shè)WH(f)=w，f(x)的小項表示為其中，x=x1x2…xn；ci=ci1ci2…cin，i=1，2，…，w。

令y=x1…xm，z=xm+1…xn，則可將f(x)的小項表示按y合并同類項，得到f(x)的另一種表示：其中，d∈GF(2)m，ei(d)∈GF(2)n－m。由于如果f(x)是m階相關(guān)免疫的，那么對任一d∈GF(2)m，都有P(f=1)=P(f=1|y=d)，即，這等價于WH(f)=2mh(d)。令h(d)=k為常函數(shù)，則定理得證。由定理3-22易得以下結(jié)論。引理3-3n元函數(shù)f(x)是一階相關(guān)免疫函數(shù)的充要條件是：WH(f)=2k且f(x)的特征矩陣C(f)的每個列向量中0和1各占一半。引理3-4f(x)是重量為2的一階相關(guān)免疫函數(shù)當(dāng)且僅當(dāng)f(x)可表示為

，其中c∈GF(2)n，，1≤i≤n，即是c的共軛向量。

定理3-23

重量為2的n元一階相關(guān)免疫函數(shù)共有2n－1個，且都可表示為

。由定理3-21和定理3-23知，如果從GF(2)n－1中取出所有互不共軛的2n－1個向量，再從這些向量中任取k個，設(shè)其為c1，c2，…，ck，那么函數(shù)是一階相關(guān)免疫的，且重量為2k。由于f=0也是一階相關(guān)免疫的，因此用這種方法可以構(gòu)造出個一階相關(guān)免疫函數(shù)。其中重量為2k的有個。定理3-24n元一階相關(guān)免疫函數(shù)至少有2n－1個。3.4Bent函數(shù)及其性質(zhì)

Bent函數(shù)由Rothaus于1976年提出［14］，最初被用于擴頻通信中的信息保護。由于Bent函數(shù)具有較好的密碼學(xué)性質(zhì)，如差分均勻性、最大非線性度等，因此在密碼領(lǐng)域得到了較為深入的研究，并在密碼設(shè)計和信號檢測等領(lǐng)域有廣泛的應(yīng)用。3.4.1定義及性質(zhì)定義3-14設(shè)f(x)：GF(2)n→GF(2)，如果對任意ω∈GF(2)n，均有，則稱f(x)為Bent函數(shù)。顯然，只有當(dāng)n為偶數(shù)時，f(x)才能成為Bent函數(shù)。根據(jù)3.2.1節(jié)的討論知，n個變元的Bent函數(shù)的非線性度為。

定理3-25

設(shè)f(x)：GF(2)n→GF(2)，Rf(τ)為f(x)的自相關(guān)函數(shù)，則f(x)是Bent函數(shù)當(dāng)且僅當(dāng)由于Rf(τ)=0當(dāng)且僅當(dāng)f(x+τ)+f(x)是一個平衡函數(shù)，因此由定理3-25易得定理3-26。

定理3-26

設(shè)f(x)：GF(2)n→GF(2)，則f(x)是Bent函數(shù)當(dāng)且僅當(dāng)對所有的τ∈GF(2)n，τ≠0，f(x+τ)+f(x)是平衡函數(shù)。下面是Bent函數(shù)研究中常用到的一個基本結(jié)論。

定理3-27

設(shè)f(x)：GF(2)n→GF(2)，Ln為所有GF(2)n→GF(2)的線性函數(shù)集合，則f(x)是Bent函數(shù)當(dāng)且僅當(dāng)對任意l(x)∈Ln，f(x)+l(x)是Bent函數(shù)。證明比較簡單，留給讀者練習(xí)。3.4.2Bent函數(shù)的構(gòu)造

定理3-28(MaioranaMcFarland構(gòu)造)［15］設(shè)n為偶數(shù)，則f(x)=x1x2+x3x4+…+xn－1xn是n個變元的Bent函數(shù)。

定理3-29

設(shè)f(x)：GF(2)n→GF(2)，A是GF(2)上的n×n階可逆矩陣，b∈GF(2)n，令g(x)=f(xA+b)，則g(x)也是n個變元的Bent函數(shù)。

證明：因為所以g(x)是Bent函數(shù)。定理3-29中的f(x)和g(x)稱為相互等價的Bent函數(shù)。

定理3-30

設(shè)f(x)是任意n元布爾函數(shù)，則是2n元Bent函數(shù)。證明：由于因此這就證明了g(x)是2n元Bent函數(shù)。定理3-30實際上給出了一大類Bent函數(shù)，有較強的實際意義。

定理3-31

記

，設(shè)Γ

{1，2，…