-
布爾函數
鎖定
在數學中,布爾函數(Boolean function)描述如何基於對布爾輸入的某種邏輯計算確定布爾值輸出,它們在複雜性理論的問題和數字計算機的芯片設計中扮演基礎角色。布爾函數的性質在密碼學中扮演關鍵角色,特別是在對稱密鑰算法的設計中(參見S-box)。
在數學中,布爾函數通常是如下形式的函數:
F(b1,b2,...,bn)
- 中文名
- 布爾函數
- 外文名
- Boolean function
- 類 型
- 數學函數
布爾函數定義
布爾函數簡介
布爾函數可以唯一的寫為積(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 (立方)。
[2]
布爾函數特點
布爾函數必須滿足一定的密碼學性質,以保證密碼系統符合安全性的基本要求,並能抵抗現有的各種攻擊。下面介紹幾條衡量布爾函數密碼學性質的指標。
布爾函數代數範式
布爾函數可以唯一的寫為積(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(
布爾函數應用
布爾函數應用程序中
一個布爾函數介紹瞭如何確定一個布爾值輸出基於某種邏輯輸入計算的布爾值。這些職能發揮作用的問題的基本理論,複雜性 ,以及作為設計的電路芯片和數字電腦。布爾函數的性質研究中發揮關鍵作用密碼學 ,特別是在設計的對稱密鑰算法 (見替代框)。
布爾函數密碼學中
布爾函數是流密碼系統的核心部件,研究布爾函數是流密碼系統重點。代數攻擊是密碼學的研究熱點。布爾函數必須具有好的密碼性質:平衡,高的代數免疫,高的代數次數,高的非線性度,代數攻擊的能力。
布爾函數對稱布爾函數
對於 n元d次初等對稱布爾函數 X(d,n) ,當時,對於給定的s 和q,證明了如果w充分大,則,即證明了 X(d,n)不是平衡的,並且利用泰勒展式估計了w的大小;對於給定的 wq 和 t,證明了如果s 充分大,則
即證明了 X(d,n)不是平衡的
布爾函數參見
代數集
布爾代數(邏輯)
布爾代數主題
布爾域
布爾值函數
邏輯連詞
對稱布爾函數
決策樹模型
- 參考資料
-
- 1. 幾類熱點布爾函數的性質分析 .中國知網[引用日期2017-03-14]
- 2. 馬諾。米莫里斯.數字化設計:塞爾維亞雜誌,2010-04-06
- 3. 秦豔琳主編;吳曉平,羅芳副主編. 信息安全數學基礎[M]. 武漢:武漢大學出版社, 2014.06.151