密碼學(xué)中的布爾函數(shù)——Bent函數(shù)

摘 要：本文介紹布爾函數(shù)中的Bent函數(shù)及其的密碼性質(zhì)。

關(guān)鍵詞：布爾函數(shù)；Bent函數(shù)；線性；密碼；相關(guān)度

中圖分類號(hào)：G712 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1002-7661（2012）22-368-01

布爾函數(shù)（單輸出和多輸出）在密碼算法的設(shè)計(jì)與分析中占有極其重要的地位.人們對(duì)布爾函數(shù)的平衡性、對(duì)稱性、高非線性、相關(guān)免疫性、擴(kuò)散性等進(jìn)行了深入研究，特別是對(duì)抵抗相關(guān)攻擊的相關(guān)免疫函數(shù)類、抗線性分析的Bent函數(shù)類進(jìn)行了系統(tǒng)的研究，取得了豐富的成果。

本文介紹布爾函數(shù)中的Bent函數(shù)。

抗線性分析是密碼系統(tǒng)必須具備的安全性能，所以非線性性是布爾函數(shù)最重要的密碼學(xué)性質(zhì)之一。由Rothaus 提出的Bent函數(shù)是一類重要的密碼函數(shù)，具有最高非線性度，由于其在密碼、編碼理論、序列以及設(shè)計(jì)理論中的重要應(yīng)用，引起了密碼學(xué)界的極大關(guān)注，取得了一系列的研究成果。

給出了Bent函數(shù)的定義如下：

定義1 如果元布爾函數(shù)的所有譜值都等于，稱為Bent函數(shù)。

另外，Bent函數(shù)還有一些等價(jià)定義：

定理1 設(shè)是元布爾函數(shù)，那么下面說法是等價(jià)的。為Bent函數(shù)。對(duì)每一個(gè)都有，其中：是的第行。。

。。。。其中：為矩陣；為的序列：為的序列，；；為集合中元素的個(gè)數(shù)；；

為的非線性度。

一直以來對(duì)Bent函數(shù)的構(gòu)造都是研究者所關(guān)心的問題。構(gòu)造方法可分為兩種，一種是間接構(gòu)造，即用已有的函數(shù)來構(gòu)造新的Bent函數(shù)；另一種就是直接構(gòu)造。至今所知道的直接構(gòu)造主要有兩類：一種是M（）類，另一類是PS（） 類。

下面再介紹兩個(gè)定理：

定理2 （）：令，則是元Bent函數(shù)，其中是上的任意置換，而是上任意的布爾函數(shù)。

若將的子空間E的指示函數(shù)定義為，而PS類Bent函數(shù)就是將由所有或個(gè)的“不交的”維子空間的指示函數(shù)的模2和所組成的函數(shù)的集合，其中，“不交的”意味著任意兩個(gè)這樣的子空間只交于0元素，且它們的維數(shù)都是P，所以任意兩個(gè)這樣的子空間的直和是。在參考文獻(xiàn)中給出了的一種劃分，從而得到了一種構(gòu)造這類函數(shù)的方法，并且給出了對(duì)應(yīng)Bent函數(shù)的代數(shù)范式。

定理3對(duì)于上的線性化多項(xiàng)式，如果它的系數(shù)矩陣A對(duì)應(yīng)的行列式的值不等于0，則可根據(jù)它構(gòu)造出一組PS類Bent函數(shù)。

雖然Bent函數(shù)具有一些優(yōu)良的密碼性質(zhì)，但它也有一些缺陷（如不具備平衡性和相關(guān)免疫性）。文獻(xiàn)引入了部分Bent函數(shù)的概念，它具備Bent函數(shù)的優(yōu)點(diǎn)（如非線性度高，擴(kuò)散性好等），同時(shí)還具備平衡性和相關(guān)免疫性。文獻(xiàn)引入了平衡函數(shù)的概念，這類函數(shù)保持了部分Bent函數(shù)的所有好的密碼特性且沒有非零線性結(jié)構(gòu)。

除了相關(guān)免疫函數(shù)和Bent函數(shù)之外，不重復(fù)齊次函數(shù)和完全非線性函數(shù)也是2類重要的布爾函數(shù)。

另外當(dāng)n為奇數(shù)時(shí)，一般布爾函數(shù)最大的Walsh譜值的下界還不知道。目前只有二次布爾函數(shù)和為3、5、7的情形是已知的。

參考文獻(xiàn)討論了差分攻擊和線性攻擊的聯(lián)系，并指出當(dāng)輸入變量的個(gè)數(shù)不小于輸出變量個(gè)數(shù)的兩倍時(shí)，多輸出Bent函數(shù)能抵抗線性攻擊，完全非線性函數(shù)能抵抗差分攻擊，并且它們是等價(jià)的。當(dāng)這兩個(gè)變量個(gè)數(shù)相同，而且是奇數(shù)時(shí)，幾乎完全非線性函數(shù)能抵抗差分攻擊，而幾乎Bent函數(shù)能抵抗線性攻擊，并且此時(shí)如果一個(gè)函數(shù)是幾乎Bent的，則它也是幾乎完全非線性的。反之不一定成立，參考文獻(xiàn)對(duì)此給出了其等價(jià)的充分必要條件。

目前，對(duì)偶的Bent函數(shù)的結(jié)構(gòu)還需要進(jìn)一步研究，構(gòu)造出更多的有限域上的Bent函數(shù)是一個(gè)有待解決的問題。另外，為奇數(shù)時(shí)，一般布爾函數(shù)最大的譜值的下界還不是完全已知的。因此，如何得到具有更多良好密碼性質(zhì)的布爾函數(shù)成為密碼學(xué)上的一個(gè)重要研究課題。

參考文獻(xiàn)：

[1] Rothaus O S. On Bent functions .Journal of Combinatoral Theory（Ser. A），1976，20；300-305.

[2] 常祖領(lǐng).布爾函數(shù)的研究.博士學(xué)位論文，南開大學(xué)，2003.

[3] Carlet C.Oartially-Bent functions.Advances in 92，1993，27（3）：280-291.

[4] Zheng Y L，Zhang X M，Plateaued functions.Information and Communication Security， 1999，13（9）：284-300.

[5] Patterson N J， Wiedemann D H. Correcting to the covering radius of the Reed—Muller code is at least 16272.IEEE Transactions on Information Theory，Vol 36，443.

[6] Chabaud F. Vaudenay S. Links between differential and linear cryptanalysis.

Europ—Crypto’94，1994：356-365.