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

布爾函數(shù)的密碼學(xué)性質(zhì)及其相互關(guān)系摘要：本文的主要工作是對布爾函數(shù)的密碼學(xué)性質(zhì)進行簡單的介紹以及整理，并將近期密碼函數(shù)平安性領(lǐng)域里面的主要結(jié)論進行歸納和比擬，通過各種性質(zhì)及之間相互關(guān)系找出一種構(gòu)造具有“優(yōu)秀〞密碼學(xué)性質(zhì)的函數(shù)的方法。本文第一局部為根本概念，主要內(nèi)容是布爾函數(shù)的根本知識以及文章中將會用到的相關(guān)符號和語言。這一局部還簡單介紹了布爾函數(shù)的兩個根本性質(zhì)：均衡性、代數(shù)次數(shù)。這兩個性質(zhì)對函數(shù)的平安性具有十分重要的意義。第二局部介紹了布爾函數(shù)的相關(guān)免疫性以及彈性的有關(guān)內(nèi)容，末尾簡單地介紹了幾種構(gòu)造具有特定相關(guān)免疫階的布爾函數(shù)的方法。第三局部介紹了布爾函數(shù)的非線性度以及具有最高非線性度的Bent函數(shù)的相關(guān)內(nèi)容。這一局部最后還給出了兩個完善Bent函數(shù)以使其均衡的方法。第四局部簡單地介紹了布爾函數(shù)差分均勻度和PN函數(shù)的相關(guān)內(nèi)容，并且給出了一個PN函數(shù)的等價定義。第五局部簡單介紹了布爾函數(shù)的代數(shù)免疫度的概念。第六局部給出了許多重要的結(jié)論，這些結(jié)論揭示了各種密碼函數(shù)性質(zhì)之間的內(nèi)在聯(lián)系.這一局部主要以總結(jié)歸納為主，適當(dāng)參加筆者對結(jié)論的一些觀點.第一局部：根本概念定義1.1設(shè)是二元有限域，為正整數(shù)，稱映射為布爾函數(shù).假設(shè)記全體維布爾函數(shù)的集合為.使得且的的個數(shù)稱為函數(shù)的Hamming重量，記為.如果一個維布爾函數(shù)滿足，那么稱這個函數(shù)是均衡的.設(shè),和的Hamming距離定義為其中，表示集合中元素的個數(shù).容易發(fā)現(xiàn):.維布爾函數(shù)的代數(shù)正規(guī)型：為了方便書寫，記表示的冪集，其中，那么其中，，，.這種表示方法稱為布爾函數(shù)的小項表示.在維布爾函數(shù)的代數(shù)正規(guī)型中，系數(shù)不為0的項的最高次數(shù)稱為該函數(shù)的代數(shù)次數(shù)，記為.特殊地，代數(shù)次數(shù)為1的布爾函數(shù)稱為仿射函數(shù).常數(shù)項為0的仿射函數(shù)稱為線性函數(shù).含有高于1次的項的布爾函數(shù)稱為非線性函數(shù).易證：仿射函數(shù)都是均衡的.從布爾函數(shù)的代數(shù)正規(guī)型中可以發(fā)現(xiàn)：代數(shù)次數(shù)越低的布爾函數(shù)越容易被確定，這是因為我們可以將看成未知數(shù)，代數(shù)次數(shù)越低的函數(shù)未知數(shù)越少，那么我們就可以用越少的真值對將其確定出來.因此，代數(shù)次數(shù)越低的布爾函數(shù)越不適合用作密碼函數(shù).在上面的介紹中，有兩個性質(zhì)對于一個布爾函數(shù)能否“勝任〞密碼函數(shù)來說有著十分重要的意義：均衡性、代數(shù)次數(shù)：均衡性：序列密碼體制產(chǎn)生的密鑰流是否具有高的平安強度，取決于它們是否具有良好的偽隨機性.均衡性就是序列偽隨機性的一個重要指標(biāo).一條序列稱為均衡的是指該序列中不同元素出現(xiàn)的次數(shù)至多只相差一個.代數(shù)次數(shù)：密碼體制中所使用的布爾函數(shù)通常具有高的代數(shù)次數(shù)，低代數(shù)次數(shù)的密碼體制容易遭到Berlekamp-Massey算法攻擊、插值攻擊、代數(shù)攻擊以及高階差分攻擊.以上為第一局部的主要內(nèi)容，即布爾函數(shù)的根本內(nèi)容.從第二局部開始，我們將對布爾函數(shù)的多種密碼性質(zhì)進行整理、歸納和總結(jié)，并將近期密碼學(xué)界的相關(guān)結(jié)論呈現(xiàn)出來.第二局部：布爾函數(shù)的相關(guān)免疫性這一局部主要介紹了布爾函數(shù)相關(guān)免疫性的內(nèi)容，包括相關(guān)免疫的定義以及它的一些等價刻畫、布爾函數(shù)的Walsh變換與其相關(guān)免疫性的關(guān)系、如何構(gòu)造具有特定階的相關(guān)免疫函數(shù)及其記數(shù).下面先給出相關(guān)免疫性的定義：定義2.1設(shè)有布爾函數(shù).如果①維隨機變量在上均勻分布；②對下標(biāo)集中任意個下標(biāo)，隨機變量與個隨機變量相互獨立,即對于任意的及就稱為階相關(guān)免疫布爾函數(shù).如果是階相關(guān)免疫布爾函數(shù)但不是階相關(guān)免疫函數(shù)，那么稱函數(shù)的相關(guān)免疫階為.下面的結(jié)論是維布爾函數(shù)相關(guān)免疫性的等價刻畫：定理2.1以下四個表達等價：①維布爾函數(shù)是階相關(guān)免疫函數(shù).②對任意的，令的任意個分量取任意定值，維布爾函數(shù)是階相關(guān)免疫函數(shù).③對任意的，，隨機變量與變量相互獨立.④對任意的，,函數(shù)是平衡函數(shù).以上對于相關(guān)免疫性的描述對于理解布這個性質(zhì)的本質(zhì)還具有一定的困難.布爾函數(shù)的Walsh變換對于理解其本質(zhì)有著至關(guān)重要的作用：定義2.2設(shè)是一個維布爾函數(shù).取，令.稱為的循環(huán)Walsh變換.其中，定理2.2設(shè)維布爾函數(shù).假設(shè)，那么是階相關(guān)免疫函數(shù)的充要條件是對于所有且，.上面的定理刻畫了階相關(guān)免疫函數(shù)的譜特征，對理解相關(guān)免疫性的實質(zhì)有著非常大的幫助.下面介紹具有均衡性的相關(guān)免疫函數(shù)——彈性函數(shù)：定義2.3設(shè)維布爾函數(shù)，假設(shè)函數(shù)既是一個階相關(guān)免疫函數(shù)又是均衡函數(shù)，那么稱是一個階彈性函數(shù).注意到布爾函數(shù)是均衡的當(dāng)且僅當(dāng)，于是定理2.3布爾函數(shù)是一個階彈性函數(shù)的充要條件是對于所有的且，均有.在密碼學(xué)研究中，密碼函數(shù)的均衡性是密碼函數(shù)的最根本的性質(zhì)，所以一下討論都將圍繞彈性函數(shù)展開.下面將簡單地介紹一下彈性函數(shù)的構(gòu)造.由于一階彈性函數(shù)的構(gòu)造方法比擬復(fù)雜，而且方法種類繁多，這里將省略介紹之.參考文獻[1]中有比擬詳細的關(guān)于一階彈性函數(shù)的構(gòu)造方法.這里介紹一下如何通過的彈性函數(shù)構(gòu)造新的彈性函數(shù).定理2.4設(shè)是維階彈性函數(shù)，那么是維階彈性函數(shù).定理2.5設(shè)是維階彈性函數(shù)，是維階彈性函數(shù)，那么是維階彈性函數(shù).定理2.6假設(shè)函數(shù)均是維階彈性函數(shù)，那么函數(shù)也是階彈性函數(shù)的充要條件是是階彈性函數(shù).這一局部最后將給出幾個關(guān)于循環(huán)Wlash變換的結(jié)論，循環(huán)Wlash變換的定義已經(jīng)由定義2.2給出.定義2.4設(shè)是一個維布爾函數(shù).稱為的線性Walsh變換.其中，的定義如上.稱為的線性Walsh反變換，容易驗證，線性Walsh變換與循環(huán)Wlash變換之間存在著如下關(guān)系：由此可知兩種Walsh變換可以相互唯一確定，所以以后不加說明的話布爾函數(shù)的Walsh變換指的就是循環(huán)Walsh變換.容易驗證布爾函數(shù)的循環(huán)Walsh變換有如下性質(zhì)：定理2.7假設(shè)為的循環(huán)Walsh變換，即，那么，①稱為的循環(huán)Walsh逆變換，且.②能量守恒公式：.③卷積公式：對于任意的，.第三局部：布爾函數(shù)的非線性度布爾函數(shù)的非線性度從形象上說指的是布爾函數(shù)與仿射函數(shù)之間的“距離〞.為了抵抗線性密碼攻擊，密碼體制中所使用的布爾函數(shù)應(yīng)該離所有的仿射函數(shù)的“距離〞盡可能大.所以布爾函數(shù)的非線性度定義為和所有仿射函數(shù)的最小Hamming距離.定義3.1設(shè)是一個維布爾函數(shù)，稱如下的為的非線性度，其中表示所有維仿射函數(shù)的集合.定理3.1設(shè)是一個維布爾函數(shù)，那么其中，是的循環(huán)Walsh變換.這個定理給出了布爾函數(shù)非線性度的計算方法，下面的定理給出一個布爾函數(shù)的非線性度緊的上界.定理3.2設(shè)是一個維布爾函數(shù)，那么它的非線性度滿足定理3.2中的上界是可達的.定義3.2設(shè)是一個維布爾函數(shù)，如果的非線性度到達，那么稱為Bent函數(shù)定理3.3設(shè)是一個維布爾函數(shù)，那么是Bent函數(shù)當(dāng)且僅當(dāng)對任意的，的取值只能是.容易發(fā)現(xiàn)，Bent函數(shù)的維數(shù)必定為偶數(shù).定義3.2和定理3.3都可以作為Bent的定義，其本質(zhì)是相同的.Bent函數(shù)是非線性度最高的布爾函數(shù)，下面給出一些關(guān)于Bent函數(shù)的結(jié)論.定理3.4〔存在性〕設(shè)為任意正偶數(shù)，令那么是一個元Bent函數(shù).定理3.5設(shè)是維Bent函數(shù)，是上的階可逆方陣，，令，那么也是維Bent函數(shù).定理3.6設(shè)是任意一個維布爾函數(shù)數(shù)，那么是維Bent函數(shù).雖然Bent函數(shù)擁有最高的非線性度，但是Bent函數(shù)卻沒有作為密碼函數(shù)最根本的性質(zhì)——均衡性.下面簡單地給出兩個構(gòu)造方式，可以通過對Bent函數(shù)進行改造，使其具有均衡性.定理3.7高非線性度均衡布爾函數(shù)構(gòu)造方法構(gòu)造方法1.取定個維Bent函數(shù)，其中.其中的個函數(shù)滿足另外個函數(shù)形狀為定義維布爾函數(shù)，那么且均衡.構(gòu)造方法2.設(shè)有維Bent函數(shù)，定義維布爾函數(shù)如下：那么，且均衡.第四局部：布爾函數(shù)的差分均勻度以及完全非線性函數(shù)差分分布的均勻性是密碼函數(shù)的一個重要的平安性指標(biāo)，差分密碼分析方法的成功正是通過布爾函數(shù)差分分布的不均勻性實現(xiàn)的.函數(shù)的差分均勻性越好，那么函數(shù)抵抗差分攻擊的能力就越強.用來刻畫布爾函數(shù)查分分布均勻性的指標(biāo)是差分均勻度.定義4.1設(shè)是從有限群到有限群的函數(shù)，令那么稱為函數(shù)的差分均勻度.定理4.1設(shè)是從有限群到有限群的函數(shù)，那么由之前的談?wù)撝罘志鶆蚨仍叫?，布爾函?shù)的平安性就越高.定理4.1給出了差分均勻度的一個下界，由此引出完全非線性函數(shù)的概念：定義4.2設(shè)是從有限群到有限群的函數(shù)，且，如果，那么稱為完全非線性函數(shù)，簡稱PN函數(shù).為了給出一個完全非線性函數(shù)的等價定義，首先引入一個概念——平衡函數(shù)：定義4.3設(shè)是從有限群到有限群的函數(shù)，稱為平衡函數(shù)是指，對于任意的，集合中所含的元素個數(shù)相等.也即如群的階是，群的階是，那么.下面給出PN函數(shù)的等價刻畫：定理4.2設(shè)是從有限群到有限群的函數(shù)，且.那么是PN函數(shù)當(dāng)且僅當(dāng)對任意的非零，函數(shù)為平衡函數(shù).這個定理反映了PN函數(shù)的本質(zhì)特征，即它的差分分布的均勻性已經(jīng)到達最優(yōu)，對于差分均勻度和完全非線性函數(shù)的介紹也就到此為止.第五局部：布爾函數(shù)的代數(shù)免疫度布爾函數(shù)的代數(shù)免疫度是對一個布爾函數(shù)抵抗代數(shù)攻擊能力的衡量標(biāo)準(zhǔn)，也是密碼函數(shù)平安性的一個重要指標(biāo).代數(shù)免疫度低的布爾函數(shù)容易遭到代數(shù)攻擊，代數(shù)攻擊所利用的理論依據(jù)與差分攻擊和線性攻擊等攻擊手段不一樣.前者是利用密碼算法的內(nèi)部代數(shù)結(jié)構(gòu)實施攻擊，而后者那么是利用密碼算法的統(tǒng)計性質(zhì)實施攻擊.然而，對布爾函數(shù)實施代數(shù)攻擊能否成功的關(guān)鍵在于是否存在一個低次的函數(shù)，使得.定義5.1設(shè)維布爾函數(shù)，稱滿足的布爾函數(shù)為布爾函數(shù)的零化子.對任意的維布爾函數(shù)，記其零化子的集合為定義5.2設(shè)維布爾函數(shù)，使得或成立的非零布爾函數(shù)的最小代數(shù)次數(shù)稱為的代數(shù)免疫度，記為.即下面的定理給出了代數(shù)免疫度的上界.定理5.1設(shè)是維布爾函數(shù)，那么的代數(shù)免疫度滿足：定義5.3假設(shè)一個維布爾函數(shù)的代數(shù)免疫度到達，那么稱該函數(shù)具有最優(yōu)代數(shù)免疫度.有關(guān)代數(shù)免疫度的結(jié)論，更多的是與其他密碼性質(zhì)放在一起討論的.如具有固定代數(shù)免疫度是函數(shù)的非線性度具有一個緊的下界，代數(shù)免疫度確定是函數(shù)的相關(guān)免疫階和彈性階的取值規(guī)律，代數(shù)免疫度與函數(shù)的重量也有密切的關(guān)系.如此多的性質(zhì)和結(jié)論將在第六局部給出.第六局部：布爾函數(shù)密碼性質(zhì)之間的相互關(guān)系構(gòu)造一個具有好的密碼學(xué)性質(zhì)的密碼函數(shù)是密碼學(xué)研究者們夢寐以求的事情，然而大量的結(jié)果說明這些密碼學(xué)性質(zhì)之間存在著相互制約的關(guān)系.一種性質(zhì)好了另一種性質(zhì)就會受到制約而變差.正是因為如此，構(gòu)造一個性質(zhì)“兼顧〞的布爾函數(shù)也成了比擬困難的事.這一局部將給出各性質(zhì)之間相互的關(guān)系，以便從中找到一種構(gòu)造“優(yōu)質(zhì)〞密碼函數(shù)的方法.密碼函數(shù)的平安性指標(biāo)在第一、二、三、四、五局部中均已介紹，指的是布爾函數(shù)的均衡性、代數(shù)次數(shù)、相關(guān)免疫性和彈性、非線性度、差分均勻度以及代數(shù)免疫度.1.相關(guān)免疫性與其他性質(zhì)的關(guān)系定理6.1設(shè)維布爾函數(shù)，假設(shè)是階相關(guān)免疫函數(shù)，那么；假設(shè)是階彈性函數(shù)，那么.這個定理說明了布爾函數(shù)的相關(guān)免疫性和彈性與函數(shù)的代數(shù)次數(shù)相互制約.定理6.2給定維布爾函數(shù)，假設(shè)是階相關(guān)免疫函數(shù)，，那么假設(shè)是階彈性函數(shù)，，那么這個定理揭示了布爾函數(shù)相關(guān)免疫性和彈性與非線性度的相互制約關(guān)系.定理中的非線性度的上限被稱作Sarkar限.2.非線性度與其他性質(zhì)的關(guān)系由第三局部我們知道Bent函數(shù)具有最高的非線性度，下面的定理說明了Bent函數(shù)的一些其他密碼學(xué)性質(zhì).定義6.1設(shè)是一個維布爾函數(shù)，其自相關(guān)函數(shù)定義為自相關(guān)函數(shù)刻畫了布爾函數(shù)的自相關(guān)性，這個概念可以與序列的自相關(guān)性類比理解.定理6.3設(shè)是一個維布爾函數(shù)，那么是Bent函數(shù)當(dāng)且僅當(dāng)這個定理說明Bent函數(shù)是具有最有自相關(guān)性的布爾函數(shù).定理6.4設(shè)是一個維布爾函數(shù)，，假設(shè)是Bent函數(shù)，那么它的代數(shù)次數(shù)不超過.這個定理說明了函數(shù)的非線性度與函數(shù)的代數(shù)次數(shù)之間存在著相互制約的關(guān)系.定理6.5設(shè)維布爾函數(shù)，其非線性度與其相關(guān)免疫階有如下的關(guān)系：有這個定理知道布爾函數(shù)的非線性度與相關(guān)免疫階呈負相關(guān).3.代數(shù)免疫度與其他性質(zhì)的關(guān)系第五局部定理5.1給出了布爾函數(shù)的代數(shù)免疫度與代數(shù)次數(shù)的關(guān)系：設(shè)是維布爾函數(shù)，那么的代數(shù)免疫度滿足：定理6.6設(shè)維布爾函數(shù)，的代數(shù)免疫度，那么特別地，意味著〔1〕當(dāng)為奇數(shù)時，必為平衡函數(shù)；〔2〕當(dāng)為奇數(shù)時，這個定理沒有揭示代數(shù)免疫度與其他性質(zhì)的關(guān)系，它是聯(lián)系代數(shù)免疫度和函數(shù)Hamming重量的重要事實.定理6.7設(shè)維布爾函數(shù)，，那么定理6.8對于任意的正整數(shù)和，定理6.7中的界是緊的.這兩個定理告訴我們函數(shù)的代數(shù)免疫度和函數(shù)的非線性度存在著相互制約的關(guān)系，但是這種制約關(guān)系是可以被估計的，并且這個界可以到達.定理6.9設(shè)為維階相關(guān)免疫函數(shù)，那么；假設(shè)還是均衡的，即是階彈性函數(shù)，那么這個定理是定理6.1的直接推論.聯(lián)合定理6.5，可以馬上得到一個新的結(jié)果：定理6.10設(shè)為維布爾函數(shù)，，假設(shè)是階相關(guān)免疫函數(shù)，那么假設(shè)是階彈性函數(shù)，那么這兩個定理都說明了布爾函數(shù)的代數(shù)免疫度與相關(guān)免疫性之間的關(guān)系，可以發(fā)現(xiàn)這兩者之間也存在著負相關(guān)性.可以發(fā)現(xiàn)布爾函數(shù)的各項密碼學(xué)性質(zhì)均存在著相互的制約關(guān)系，如何構(gòu)造一個性質(zhì)中庸、抗攻擊性強的布爾函數(shù)依然是現(xiàn)今比擬流行的話題.參考文獻[1]李超,屈龍江，周悅.密碼函數(shù)的平安性指標(biāo)分析[M].第一版.科學(xué)出版社，2023.[2]馮國登.頻譜理論及其在密碼學(xué)中的應(yīng)用[M].科學(xué)出版社，2000.[3]CarletC.Onbentandhighly