布爾函數檢視原始碼討論檢視歷史

布爾函數

原圖鏈接

中文名: 布爾函數 外文名: Boolean function

在數學中，布爾函數（Boolean function）描述如何基於對布爾輸入的某種邏輯計算確定布爾值輸出，它們在複雜性理論的問題和數字計算機的芯片設計中扮演基礎角色。布爾函數的性質在密碼學中扮演關鍵角色，特別是在對稱密鑰算法的設計中（參見S-box）。 在數學中，布爾函數通常是如下形式的函數： F(b1,b2,...,bn) 帶有 n 個來自兩元素布爾代數 {0,1} 的布爾變量 bi，F 的取值也在 {0,1} 中。 在一般的定義域上的，取值在 {0,1} 中的函數也叫做布爾值函數，所以布爾函數是它的特殊情況。

簡介

布爾函數是研究密碼算法和密碼技術的重要工具，無論在流密碼還是在分組密碼中，在對稱還是在非對稱密碼中都有重要的應用。   帶有定義域 {1,2,3,... } 的這種函數通常叫做二進制序列，就是說 0 和 1 的無限序列；通過限制到 { 1,2,3,...,n }，布爾函數是編碼長度為 n 的序列的自然的方法。 它有 2^{2^n} 個布爾函數；它們在複雜性理論的問題和數字計算機的芯片設計中扮演基礎角色。布爾函數的性質在密碼學中扮演關鍵角色，特別是在對稱密鑰算法的設計中(參見 S-box)。 在布爾值函數上的布爾運算逐點（point-wise）組合值（比如通過 XOR 或其他布爾運算符）。 布爾函數可以唯一的寫為積（AND）之和（XOR）。這叫做代數範式 (ANF），也叫做Zhegalkin多項式。 f(x1,x2,...,xn) =a0 +a1x1 + a2x2 + ... + anxn + a{1,2}x1x2 + a{n-1,n}x(n-1）xn + ... + a{1,2,...,n}x1x2...xn 序列 a0,a1,...,a{1,2,...,n} 的值因此還唯一的表示一個布爾函數。布爾函數的代數度被定義為出現在乘積項中的 xi 的最高數。所以 f(x1,x2,x3） = x1 + x3 有度數 1 （線性），而 f(x1,x2,x3） = x1 + x1x2x3 有度數 3 （立方）。  

特點

布爾函數必須滿足一定的密碼學性質，以保證密碼系統符合安全性的基本要求，並能抵抗現有的各種攻擊。下面介紹幾條衡量布爾函數密碼學性質的指標。 為了抵抗最佳仿射逼近攻擊，布爾函數必須與仿射函數保持儘可能大的漢明距離。為了衡量布爾函數抵抗「仿射攻擊」的能力，引入了非線性度的概念。  

代數範式

布爾函數可以唯一的寫為積（AND）之和（XOR）。這叫做代數範式（ANF），也叫做Zhegalkin多項式。 這裡的序列 的值因此還唯一的表示一個布爾函數。布爾函數的代數次數被定義為出現在乘積項中的 xi 的最高次數。所以 f(x1,x2,x3） = x1 + x3 有次數 1 （線性），而 f(x1,x2,x3） = x1 + x1x2x3 有次數 3 （立方）。 對於每個函數 f 都有一個唯一的 ANF。只有四個函數有一個參數: f(x) = 0,f(x) = 1,f(x) = x,f(x) = 1 + x （它們都可以在 ANF 中給出），要表示有多個參數的函數，可以使用如下等式： ，這裡的 並且。實際上，如果 x1 = 0 則 x1h = 0 並因此 ；如果 x1 = 1 則 x1h = h 並因此。因為 g 和 h 二者都有比 f 少的參數，可以得出遞歸的使用這個過程將完成於只有一個變量的函數。例如，讓我們構造一個 （邏輯或）的 ANF: f(x,y) = f(0,y) + x(f(0,y) + f（1,y））；因為 並且 ，可以得出 f(x,y) = y + x(y + 1）；通過打開括號我們得到最終的 ANF: f(x,y) = y + xy + x = x + y + xy。 一個布爾函數介紹了如何確定一個布爾值輸出基於某種邏輯輸入計算的布爾值。這些職能發揮作用的問題的基本理論，複雜性 ，以及作為設計的電路芯片和數字電腦。布爾函數的性質研究中發揮關鍵作用密碼學 ，特別是在設計的對稱密鑰算法 （見替代框）。 布爾函數通常代表中的句子命題邏輯 ，有時作為多元多項式超過綠 ⑵，但更有效的申述， 二元決策圖 （BDD）的， 正常的否定形式 ，與命題向無環圖 （PDAG）。 在合作博弈論，布爾函數被稱為遊戲） 簡單的遊戲 （表決；這個概念應用到解決問題的社會選擇理論。  

密碼學中

布爾函數是流密碼系統的核心部件，研究布爾函數是流密碼系統重點。代數攻擊是密碼學的研究熱點。布爾函數必須具有好的密碼性質:平衡，高的代數免疫，高的代數次數，高的非線性度，代數攻擊的能力。

對稱布爾函數

對於 n元d次初等對稱布爾函數 X(d,n) ，當，即證明了 X(d,n)不是平衡的，並且利用泰勒展式估計了w的大小；對於給定的 wq 和 t，證明了如果s 充分大，則 即證明了 X(d,n)不是平衡的

參見

代數集 布爾代數（邏輯） 布爾代數主題 布爾域 布爾邏輯 布爾值函數 邏輯連詞 真值函數 真值表 對稱布爾函數 決策樹模型 迴避的布爾函數