布爾函數(shù)的密碼性質(zhì)及其相互關(guān)系

1、布爾函數(shù)的密碼學(xué)性質(zhì)及其相互關(guān)系摘要：本文的主要工作是對(duì)布爾函數(shù)的密碼學(xué)性質(zhì)進(jìn)行簡(jiǎn)單的介紹以及整理，并將近期密碼函數(shù)安全性領(lǐng)域里面的主要結(jié)論進(jìn)行歸納和比較，通過(guò)各種性質(zhì)及之間相互關(guān)系找出一種構(gòu)造具有“優(yōu)秀”密碼學(xué)性質(zhì)的函數(shù)的方法。本文第一部分為基本概念，主要內(nèi)容是布爾函數(shù)的基本知識(shí)以及文章中將會(huì)用到的相關(guān)符號(hào)和語(yǔ)言。這一部分還簡(jiǎn)單介紹了布爾函數(shù)的兩個(gè)基本性質(zhì)：均衡性、代數(shù)次數(shù)。這兩個(gè)性質(zhì)對(duì)函數(shù)的安全性具有十分重要的意義。第二部分介紹了布爾函數(shù)的相關(guān)免疫性以及彈性的有關(guān)內(nèi)容，末尾簡(jiǎn)單地介紹了幾種構(gòu)造具有特定相關(guān)免疫階的布爾函數(shù)的方法。第三部分介紹了布爾函數(shù)的非線(xiàn)性度以及具有最高非線(xiàn)性度的Bent

2、函數(shù)的相關(guān)內(nèi)容。這一部分最后還給出了兩個(gè)完善Bent函數(shù)以使其均衡的方法。第四部分簡(jiǎn)單地介紹了布爾函數(shù)差分均勻度和PN函數(shù)的相關(guān)內(nèi)容，并且給出了一個(gè)PN函數(shù)的等價(jià)定義。第五部分簡(jiǎn)單介紹了布爾函數(shù)的代數(shù)免疫度的概念。第六部分給出了許多重要的結(jié)論，這些結(jié)論揭示了各種密碼函數(shù)性質(zhì)之間的內(nèi)在聯(lián)系. 這一部分主要以總結(jié)歸納為主，適當(dāng)加入筆者對(duì)結(jié)論的一些觀點(diǎn). 第一部分：基本概念定義1.1 設(shè)是二元有限域，為正整數(shù)，稱(chēng)映射為布爾函數(shù). 若記全體維布爾函數(shù)的集合為. 使得且的的個(gè)數(shù)稱(chēng)為函數(shù)的Hamming重量，記為. 如果一個(gè)維布爾函數(shù)滿(mǎn)足，則稱(chēng)這個(gè)函數(shù)是均衡的. 設(shè),和的Hamming距離定義為其中，表示

3、集合中元素的個(gè)數(shù). 容易發(fā)現(xiàn):. 維布爾函數(shù)的代數(shù)正規(guī)型：為了方便書(shū)寫(xiě)，記表示的冪集，其中，則其中，.這種表示方法稱(chēng)為布爾函數(shù)的小項(xiàng)表示.在維布爾函數(shù)的代數(shù)正規(guī)型中，系數(shù)不為0的項(xiàng)的最高次數(shù)稱(chēng)為該函數(shù)的代數(shù)次數(shù)，記為. 特殊地， 代數(shù)次數(shù)為1的布爾函數(shù)稱(chēng)為仿射函數(shù). 常數(shù)項(xiàng)為0的仿射函數(shù)稱(chēng)為線(xiàn)性函數(shù). 含有高于1次的項(xiàng)的布爾函數(shù)稱(chēng)為非線(xiàn)性函數(shù). 易證：仿射函數(shù)都是均衡的. 從布爾函數(shù)的代數(shù)正規(guī)型中可以發(fā)現(xiàn)：代數(shù)次數(shù)越低的布爾函數(shù)越容易被確定，這是因?yàn)槲覀兛梢詫⒖闯晌粗獢?shù)，代數(shù)次數(shù)越低的函數(shù)未知數(shù)越少，那么我們就可以用越少的真值對(duì)將其確定出來(lái). 因此，代數(shù)次數(shù)越低的布爾函數(shù)越不適合用作密碼函數(shù).

4、 在上面的介紹中，有兩個(gè)性質(zhì)對(duì)于一個(gè)布爾函數(shù)能否“勝任”密碼函數(shù)來(lái)說(shuō)有著十分重要的意義：均衡性、代數(shù)次數(shù)：均衡性：序列密碼體制產(chǎn)生的密鑰流是否具有高的安全強(qiáng)度，取決于它們是否具有良好的偽隨機(jī)性. 均衡性就是序列偽隨機(jī)性的一個(gè)重要指標(biāo). 一條序列稱(chēng)為均衡的是指該序列中不同元素出現(xiàn)的次數(shù)至多只相差一個(gè). 代數(shù)次數(shù)：密碼體制中所使用的布爾函數(shù)通常具有高的代數(shù)次數(shù)，低代數(shù)次數(shù)的密碼體制容易遭到Berlekamp-Massey算法攻擊、插值攻擊、代數(shù)攻擊以及高階差分攻擊. 以上為第一部分的主要內(nèi)容，即布爾函數(shù)的基本內(nèi)容. 從第二部分開(kāi)始，我們將對(duì)布爾函數(shù)的多種密碼性質(zhì)進(jìn)行整理、歸納和總結(jié)，并將近期密碼學(xué)

5、界的相關(guān)結(jié)論呈現(xiàn)出來(lái). 第二部分：布爾函數(shù)的相關(guān)免疫性 這一部分主要介紹了布爾函數(shù)相關(guān)免疫性的內(nèi)容，包括相關(guān)免疫的定義以及它的一些等價(jià)刻畫(huà)、布爾函數(shù)的Walsh變換與其相關(guān)免疫性的關(guān)系、如何構(gòu)造具有特定階的相關(guān)免疫函數(shù)及其記數(shù). 下面先給出相關(guān)免疫性的定義：定義2.1 設(shè)有布爾函數(shù). 如果維隨機(jī)變量在上均勻分布；對(duì)下標(biāo)集中任意個(gè)下標(biāo)，隨機(jī)變量與個(gè)隨機(jī)變量相互獨(dú)立,即對(duì)于任意的及就稱(chēng)為階相關(guān)免疫布爾函數(shù). 如果是階相關(guān)免疫布爾函數(shù)但不是階相關(guān)免疫函數(shù)，則稱(chēng)函數(shù)的相關(guān)免疫階為. 下面的結(jié)論是維布爾函數(shù)相關(guān)免疫性的等價(jià)刻畫(huà)：定理2.1 以下四個(gè)敘述等價(jià)：維布爾函數(shù)是階相關(guān)免疫函數(shù). 對(duì)任意的，令的任

6、意個(gè)分量取任意定值，維布爾函數(shù)是階相關(guān)免疫函數(shù). 對(duì)任意的，隨機(jī)變量與變量相互獨(dú)立. 對(duì)任意的，, 函數(shù)是平衡函數(shù). 以上對(duì)于相關(guān)免疫性的描述對(duì)于理解布這個(gè)性質(zhì)的本質(zhì)還具有一定的困難. 布爾函數(shù)的Walsh變換對(duì)于理解其本質(zhì)有著至關(guān)重要的作用：定義2.2 設(shè)是一個(gè)維布爾函數(shù). 取，令. 稱(chēng)為的循環(huán)Walsh變換. 其中，定理2.2 設(shè)維布爾函數(shù). 若，則是階相關(guān)免疫函數(shù)的充要條件是對(duì)于所有且，. 上面的定理刻畫(huà)了階相關(guān)免疫函數(shù)的譜特征，對(duì)理解相關(guān)免疫性的實(shí)質(zhì)有著非常大的幫助. 下面介紹具有均衡性的相關(guān)免疫函數(shù)彈性函數(shù)：定義2.3 設(shè)維布爾函數(shù)，若函數(shù)既是一個(gè)階相關(guān)免疫函數(shù)又是均衡函數(shù)，則稱(chēng)是一

7、個(gè)階彈性函數(shù). 注意到布爾函數(shù)是均衡的當(dāng)且僅當(dāng)，于是定理2.3 布爾函數(shù)是一個(gè)階彈性函數(shù)的充要條件是對(duì)于所有的且，均有. 在密碼學(xué)研究中，密碼函數(shù)的均衡性是密碼函數(shù)的最基本的性質(zhì)，所以一下討論都將圍繞彈性函數(shù)展開(kāi). 下面將簡(jiǎn)單地介紹一下彈性函數(shù)的構(gòu)造. 由于一階彈性函數(shù)的構(gòu)造方法比較復(fù)雜，而且方法種類(lèi)繁多，這里將省略介紹之. 參考文獻(xiàn)1中有比較詳細(xì)的關(guān)于一階彈性函數(shù)的構(gòu)造方法. 這里介紹一下如何通過(guò)已知的彈性函數(shù)構(gòu)造新的彈性函數(shù). 定理2.4 設(shè)是維階彈性函數(shù)，則是維階彈性函數(shù). 定理2.5 設(shè)是維階彈性函數(shù)，是維階彈性函數(shù)，則是維階彈性函數(shù). 定理2.6 若函數(shù)均是維階彈性函數(shù)，則函數(shù)也是階

8、彈性函數(shù)的充要條件是是階彈性函數(shù). 這一部分最后將給出幾個(gè)關(guān)于循環(huán)Wlash變換的結(jié)論，循環(huán)Wlash變換的定義已經(jīng)由定義2.2給出. 定義2.4設(shè)是一個(gè)維布爾函數(shù). 稱(chēng)為的線(xiàn)性Walsh變換. 其中，的定義如上. 稱(chēng)為的線(xiàn)性Walsh反變換，容易驗(yàn)證，線(xiàn)性Walsh變換與循環(huán)Wlash變換之間存在著如下關(guān)系：由此可知兩種Walsh變換可以相互唯一確定，所以以后不加說(shuō)明的話(huà)布爾函數(shù)的Walsh變換指的就是循環(huán)Walsh變換. 容易驗(yàn)證布爾函數(shù)的循環(huán)Walsh變換有如下性質(zhì)：定理2.7 若為的循環(huán)Walsh變換，即，那么，稱(chēng)為的循環(huán)Walsh逆變換，且. 能量守恒公式：. 卷積公式：對(duì)于任意的，

9、 . 第三部分：布爾函數(shù)的非線(xiàn)性度 布爾函數(shù)的非線(xiàn)性度從形象上說(shuō)指的是布爾函數(shù)與仿射函數(shù)之間的“距離”. 為了抵抗線(xiàn)性密碼攻擊，密碼體制中所使用的布爾函數(shù)應(yīng)該離所有的仿射函數(shù)的“距離”盡可能大. 所以布爾函數(shù)的非線(xiàn)性度定義為和所有仿射函數(shù)的最小Hamming距離. 定義 3.1 設(shè)是一個(gè)維布爾函數(shù)，稱(chēng)如下的為的非線(xiàn)性度，其中表示所有維仿射函數(shù)的集合. 定理3.1 設(shè)是一個(gè)維布爾函數(shù)，則其中，是的循環(huán)Walsh變換. 這個(gè)定理給出了布爾函數(shù)非線(xiàn)性度的計(jì)算方法，下面的定理給出一個(gè)布爾函數(shù)的非線(xiàn)性度緊的上界. 定理3.2 設(shè)是一個(gè)維布爾函數(shù)，則它的非線(xiàn)性度滿(mǎn)足定理3.2中的上界是可達(dá)的. 定義3.2

10、設(shè)是一個(gè)維布爾函數(shù)，如果的非線(xiàn)性度達(dá)到，那么稱(chēng)為Bent函數(shù) 定理3.3 設(shè)是一個(gè)維布爾函數(shù)，則是Bent函數(shù)當(dāng)且僅當(dāng)對(duì)任意的，的取值只能是. 容易發(fā)現(xiàn)，Bent函數(shù)的維數(shù)必定為偶數(shù). 定義3.2和定理3.3都可以作為Bent的定義，其本質(zhì)是相同的. Bent函數(shù)是非線(xiàn)性度最高的布爾函數(shù)，下面給出一些關(guān)于Bent函數(shù)的結(jié)論. 定理3.4 （存在性）設(shè)為任意正偶數(shù)，令則是一個(gè)元Bent函數(shù). 定理3.5 設(shè)是維Bent函數(shù)，是上的階可逆方陣，令，則也是維Bent函數(shù). 定理3.6 設(shè)是任意一個(gè)維布爾函數(shù)數(shù)，則是維Bent函數(shù). 雖然Bent函數(shù)擁有最高的非線(xiàn)性度，但是Bent函數(shù)卻沒(méi)有作為密碼函

11、數(shù)最基本的性質(zhì)均衡性. 下面簡(jiǎn)單地給出兩個(gè)構(gòu)造方式，可以通過(guò)對(duì)Bent函數(shù)進(jìn)行改造，使其具有均衡性. 定理3.7 高非線(xiàn)性度均衡布爾函數(shù)構(gòu)造方法構(gòu)造方法1. 取定個(gè)維Bent函數(shù)，其中. 其中的個(gè)函數(shù)滿(mǎn)足另外個(gè)函數(shù)形狀為定義維布爾函數(shù)，則且均衡. 構(gòu)造方法2. 設(shè)有維Bent函數(shù)，定義維布爾函數(shù)如下：則，且均衡. 第四部分：布爾函數(shù)的差分均勻度以及完全非線(xiàn)性函數(shù) 差分分布的均勻性是密碼函數(shù)的一個(gè)重要的安全性指標(biāo)，差分密碼分析方法的成功正是通過(guò)布爾函數(shù)差分分布的不均勻性實(shí)現(xiàn)的. 函數(shù)的差分均勻性越好，那么函數(shù)抵抗差分攻擊的能力就越強(qiáng). 用來(lái)刻畫(huà)布爾函數(shù)查分分布均勻性的指標(biāo)是差分均勻度. 定義4.

12、1 設(shè)是從有限群到有限群的函數(shù)，令則稱(chēng)為函數(shù)的差分均勻度. 定理4.1 設(shè)是從有限群到有限群的函數(shù)，則 由之前的談?wù)撝罘志鶆蚨仍叫?，布爾函?shù)的安全性就越高. 定理4.1給出了差分均勻度的一個(gè)下界，由此引出完全非線(xiàn)性函數(shù)的概念： 定義4.2 設(shè)是從有限群到有限群的函數(shù)，且，如果，則稱(chēng)為完全非線(xiàn)性函數(shù)，簡(jiǎn)稱(chēng)PN函數(shù). 為了給出一個(gè)完全非線(xiàn)性函數(shù)的等價(jià)定義，首先引入一個(gè)概念平衡函數(shù)： 定義4.3 設(shè)是從有限群到有限群的函數(shù)，稱(chēng)為平衡函數(shù)是指，對(duì)于任意的，集合中所含的元素個(gè)數(shù)相等. 也即如群的階是，群的階是，則. 下面給出PN函數(shù)的等價(jià)刻畫(huà)： 定理4.2 設(shè)是從有限群到有限群的函數(shù)，且.那么是PN函

13、數(shù)當(dāng)且僅當(dāng)對(duì)任意的非零，函數(shù)為平衡函數(shù). 這個(gè)定理反映了PN函數(shù)的本質(zhì)特征，即它的差分分布的均勻性已經(jīng)達(dá)到最優(yōu)，對(duì)于差分均勻度和完全非線(xiàn)性函數(shù)的介紹也就到此為止. 第五部分：布爾函數(shù)的代數(shù)免疫度 布爾函數(shù)的代數(shù)免疫度是對(duì)一個(gè)布爾函數(shù)抵抗代數(shù)攻擊能力的衡量標(biāo)準(zhǔn)，也是密碼函數(shù)安全性的一個(gè)重要指標(biāo). 代數(shù)免疫度低的布爾函數(shù)容易遭到代數(shù)攻擊，代數(shù)攻擊所利用的理論依據(jù)與差分攻擊和線(xiàn)性攻擊等攻擊手段不一樣. 前者是利用密碼算法的內(nèi)部代數(shù)結(jié)構(gòu)實(shí)施攻擊，而后者則是利用密碼算法的統(tǒng)計(jì)性質(zhì)實(shí)施攻擊. 然而，對(duì)布爾函數(shù)實(shí)施代數(shù)攻擊能否成功的關(guān)鍵在于是否存在一個(gè)低次的函數(shù)，使得. 定義5.1 設(shè)維布爾函數(shù)，稱(chēng)滿(mǎn)足的布

14、爾函數(shù)為布爾函數(shù)的零化子. 對(duì)任意的維布爾函數(shù)，記其零化子的集合為 定義5.2 設(shè)維布爾函數(shù)，使得或成立的非零布爾函數(shù)的最小代數(shù)次數(shù)稱(chēng)為的代數(shù)免疫度，記為. 即 下面的定理給出了代數(shù)免疫度的上界. 定理5.1設(shè)是維布爾函數(shù)，則的代數(shù)免疫度滿(mǎn)足： 定義5.3 若一個(gè)維布爾函數(shù)的代數(shù)免疫度達(dá)到，則稱(chēng)該函數(shù)具有最優(yōu)代數(shù)免疫度. 有關(guān)代數(shù)免疫度的結(jié)論，更多的是與其他密碼性質(zhì)放在一起討論的. 如具有固定代數(shù)免疫度是函數(shù)的非線(xiàn)性度具有一個(gè)緊的下界，代數(shù)免疫度確定是函數(shù)的相關(guān)免疫階和彈性階的取值規(guī)律，代數(shù)免疫度與函數(shù)的重量也有密切的關(guān)系. 如此多的性質(zhì)和結(jié)論將在第六部分給出. 第六部分：布爾函數(shù)密碼性質(zhì)之間

15、的相互關(guān)系 構(gòu)造一個(gè)具有好的密碼學(xué)性質(zhì)的密碼函數(shù)是密碼學(xué)研究者們夢(mèng)寐以求的事情，然而大量的結(jié)果表明這些密碼學(xué)性質(zhì)之間存在著相互制約的關(guān)系.一種性質(zhì)好了另一種性質(zhì)就會(huì)受到制約而變差. 正是因?yàn)槿绱?，?gòu)造一個(gè)性質(zhì)“兼顧”的布爾函數(shù)也成了比較困難的事. 這一部分將給出各性質(zhì)之間相互的關(guān)系，以便從中找到一種構(gòu)造“優(yōu)質(zhì)”密碼函數(shù)的方法. 密碼函數(shù)的安全性指標(biāo)在第一、二、三、四、五部分中均已介紹，指的是布爾函數(shù)的均衡性、代數(shù)次數(shù)、相關(guān)免疫性和彈性、非線(xiàn)性度、差分均勻度以及代數(shù)免疫度. 1. 相關(guān)免疫性與其他性質(zhì)的關(guān)系 定理6.1 設(shè)維布爾函數(shù)，若是階相關(guān)免疫函數(shù)，則；若是階彈性函數(shù)，則. 這個(gè)定理說(shuō)明了布

16、爾函數(shù)的相關(guān)免疫性和彈性與函數(shù)的代數(shù)次數(shù)相互制約. 定理6.2 給定維布爾函數(shù)，若是階相關(guān)免疫函數(shù)，則若是階彈性函數(shù)，則 這個(gè)定理揭示了布爾函數(shù)相關(guān)免疫性和彈性與非線(xiàn)性度的相互制約關(guān)系. 定理中的非線(xiàn)性度的上限被稱(chēng)作Sarkar限. 2. 非線(xiàn)性度與其他性質(zhì)的關(guān)系 由第三部分我們知道Bent函數(shù)具有最高的非線(xiàn)性度，下面的定理說(shuō)明了Bent函數(shù)的一些其他密碼學(xué)性質(zhì). 定義6.1 設(shè)是一個(gè)維布爾函數(shù)，其自相關(guān)函數(shù)定義為自相關(guān)函數(shù)刻畫(huà)了布爾函數(shù)的自相關(guān)性，這個(gè)概念可以與序列的自相關(guān)性類(lèi)比理解. 定理6.3 設(shè)是一個(gè)維布爾函數(shù)，則是Bent函數(shù)當(dāng)且僅當(dāng)這個(gè)定理表明Bent函數(shù)是具有最有自相關(guān)性的布爾函

17、數(shù). 定理6.4 設(shè)是一個(gè)維布爾函數(shù)，若是Bent函數(shù)，則它的代數(shù)次數(shù)不超過(guò). 這個(gè)定理表明了函數(shù)的非線(xiàn)性度與函數(shù)的代數(shù)次數(shù)之間存在著相互制約的關(guān)系. 定理6.5 設(shè)維布爾函數(shù)，其非線(xiàn)性度與其相關(guān)免疫階有如下的關(guān)系： 有這個(gè)定理知道布爾函數(shù)的非線(xiàn)性度與相關(guān)免疫階呈負(fù)相關(guān). 3. 代數(shù)免疫度與其他性質(zhì)的關(guān)系第五部分定理5.1給出了布爾函數(shù)的代數(shù)免疫度與代數(shù)次數(shù)的關(guān)系：設(shè)是維布爾函數(shù)，則的代數(shù)免疫度滿(mǎn)足： 定理6.6 設(shè)維布爾函數(shù)，的代數(shù)免疫度，則特別地，意味著（1）當(dāng)為奇數(shù)時(shí)，必為平衡函數(shù)；（2）當(dāng)為奇數(shù)時(shí)， 這個(gè)定理沒(méi)有揭示代數(shù)免疫度與其他性質(zhì)的關(guān)系，它是聯(lián)系代數(shù)免疫度和函數(shù)Hamming重量

18、的重要事實(shí). 定理6.7 設(shè)維布爾函數(shù)，則 定理6.8 對(duì)于任意的正整數(shù)和，定理6.7中的界是緊的. 這兩個(gè)定理告訴我們函數(shù)的代數(shù)免疫度和函數(shù)的非線(xiàn)性度存在著相互制約的關(guān)系，但是這種制約關(guān)系是可以被估計(jì)的，并且這個(gè)界可以達(dá)到. 定理6.9 設(shè)為維階相關(guān)免疫函數(shù)，則；若還是均衡的，即是階彈性函數(shù)，則 這個(gè)定理是定理6.1的直接推論. 聯(lián)合定理6.5，可以馬上得到一個(gè)新的結(jié)果： 定理6.10 設(shè)為維布爾函數(shù)，若是階相關(guān)免疫函數(shù)，則若是階彈性函數(shù)，則 這兩個(gè)定理都說(shuō)明了布爾函數(shù)的代數(shù)免疫度與相關(guān)免疫性之間的關(guān)系，可以發(fā)現(xiàn)這兩者之間也存在著負(fù)相關(guān)性. 可以發(fā)現(xiàn)布爾函數(shù)的各項(xiàng)密碼學(xué)性質(zhì)均存在著相互的制約關(guān)系，如何構(gòu)造一個(gè)性質(zhì)中庸、抗攻擊性強(qiáng)的布爾函數(shù)依然是現(xiàn)今比較流行的話(huà)題. 參考文獻(xiàn)1 李超,屈龍江，周悅. 密碼函數(shù)的安全性指標(biāo)分析 M. 第一版. 科學(xué)出版社，2011. 2 馮國(guó)登. 頻譜理論及其在密碼學(xué)中的應(yīng)用 M. 科學(xué)出版社，2000. 3 Carlet C. On bent and highly nonlinear balanced/resilient functions and their algebraic immunitiesC. AAECC 16,LNCS 3857. Springe