布爾函式

在數學中，布爾函式（Boolean function）描述如何基於對布爾輸入的某種邏輯計算確定布爾值輸出，它們在複雜性理論的問題和數字計算機的晶片設計中扮演基礎角色。布爾函式的性質在密碼學中扮演關鍵角色，特別是在對稱密鑰算法的設計中（參見S-box）。

在數學中，布爾函式通常是如下形式的函式：

F(b1,b2,...,bn)

帶有 n 個來自兩元素布爾代數 {0,1} 的布爾變數 bi，F 的取值也在 {0,1} 中。

在一般的定義域上的，取值在 {0,1} 中的函式也叫做布爾值函式，所以布爾函式是它的特殊情況。

基本介紹

• 中文名：布爾函式
• 外文名：Boolean function

簡介

布爾函式是研究密碼算法和密碼技術的重要工具，無論在流密碼還是在分組密碼中，在對稱還是在非對稱密碼中都有重要的套用。

帶有定義域 {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) ，當時，對於給定的s 和q，證明了如果w充分大，則，即證明了 X(d,n)不是平衡的，並且利用泰勒展式估計了w的大小；對於給定的 wq 和 t，證明了如果s 充分大，則

即證明了 X(d,n)不是平衡的

參見

代數集

布爾代數（邏輯）

布爾代數主題

布爾域

布爾邏輯

布爾值函式

邏輯連詞

真值函式

真值表

對稱布爾函式

決策樹模型

迴避的布爾函式