密碼學中的布爾函數——Bent函數

摘 要：本文介紹布爾函數中的Bent函數及其的密碼性質。

關鍵詞：布爾函數；Bent函數；線性；密碼；相關度

中圖分類號：G712 文獻標識碼：A 文章編號：1002-7661（2012）22-368-01

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

本文介紹布爾函數中的Bent函數。

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

給出了Bent函數的定義如下：

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

另外，Bent函數還有一些等價定義：

定理1 設是元布爾函數，那么下面說法是等價的。為Bent函數。對每一個都有，其中：是的第行。。

。。。。其中：為矩陣；為的序列：為的序列，；；為集合中元素的個數；；

為的非線性度。

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

下面再介紹兩個定理：

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

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

定理3對于上的線性化多項式，如果它的系數矩陣A對應的行列式的值不等于0，則可根據它構造出一組PS類Bent函數。

雖然Bent函數具有一些優良的密碼性質，但它也有一些缺陷（如不具備平衡性和相關免疫性）。文獻引入了部分Bent函數的概念，它具備Bent函數的優點（如非線性度高，擴散性好等），同時還具備平衡性和相關免疫性。文獻引入了平衡函數的概念，這類函數保持了部分Bent函數的所有好的密碼特性且沒有非零線性結構。

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

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

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

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

參考文獻：

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

[2] 常祖領.布爾函數的研究.博士學位論文，南開大學，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.