第第第第三三三三章章章章 布爾函數(shù)布爾函數(shù)布爾函數(shù)布爾函數(shù)1第六節(jié)第六節(jié)嚴(yán)格雪崩準(zhǔn)則和擴散準(zhǔn)則嚴(yán)格雪崩準(zhǔn)則和擴散準(zhǔn)則第第第第三三三三章章章章 布爾函數(shù)布爾函數(shù)布爾函數(shù)布爾函數(shù)2設(shè)設(shè)ei= = (0, …,0, 1, 0, …,0) ∈ ∈ Fn2, 其中第1其余均為其余均為0。其中第i 個分量為個分量為定義定義 3。10 設(shè)≤ ≤ n) , f (x+ +ei) + + f (x) 都是平衡函數(shù)雪崩準(zhǔn)則雪崩準(zhǔn)則。 設(shè)f (x)是是n元布爾函數(shù)元布爾函數(shù), 若對任意都是平衡函數(shù), 則稱若對任意ei(1≤ ≤ i 則稱f(x)滿足嚴(yán)格滿足嚴(yán)格第第第第三三三三章章章章 布爾函數(shù)布爾函數(shù)布爾函數(shù)布爾函數(shù)3從定義可以看出從定義可以看出, f (x)滿足嚴(yán)格雪崩準(zhǔn)則意味著改滿足嚴(yán)格雪崩準(zhǔn)則意味著改變f (x)的自變量的某一個分量的自變量的某一個分量, 則一半被改變一半被改變。變則f (x) 的取值將會有的取值將會有第第第第三三三三章章章章 布爾函數(shù)布爾函數(shù)布爾函數(shù)布爾函數(shù)4例例 3。5 函數(shù)崩準(zhǔn)則崩準(zhǔn)則, 因為x2+ +1, x3) + + f (x1, x2, x3) = = x1是平衡的+ + f (x1, x2, x3) = = 1不是平衡的不是平衡的。
函數(shù)f (x1, x2,x3) = = x1x2+ + x3不滿足嚴(yán)格需因為f (x1+ +1現(xiàn)代密碼學(xué)基本原則, x2, x3) + + f (x1, x2, x3) = = x2和是平衡的, 但不滿足嚴(yán)格需和 f(x1,但f (x1, x2, x3+ +1) 第第第第三三三三章章章章 布爾函數(shù)布爾函數(shù)布爾函數(shù)布爾函數(shù)5例例 3。6 函數(shù)格需崩準(zhǔn)則格需崩準(zhǔn)則, 因為函數(shù)f (x1, x2, x3) = = x1x2+ + x2x3+ + x1x3滿足嚴(yán)因為滿足嚴(yán)f (x1+ +1, x2, x3) + + f (x1, x2, x3) = = x2+ + x3f (x1, x2+ +1, x3) + + f (x1, x2, x3) = = x1+ + x3f (x1, x2, x3+ +1) + + f (x1, x2, x3) = = x1+ + x2都是平衡函數(shù)都是平衡函數(shù)第第第第三三三三章章章章 布爾函數(shù)布爾函數(shù)布爾函數(shù)布爾函數(shù)6定義定義 3。11 設(shè)設(shè)f (x)是是n元布爾函數(shù)元布爾函數(shù), f (x)的自相關(guān)函數(shù)定義為數(shù)定義為的自相關(guān)函Cf(α α) = =(? ?1)f (x+α α )+f (x), α α ∈ ∈ F2nn所以所以 f(x) 滿足嚴(yán)格雪崩準(zhǔn)則當(dāng)且僅當(dāng)滿足嚴(yán)格雪崩準(zhǔn)則當(dāng)且僅當(dāng)Cf(ei) = = 0, i = = 1, 2, …, n。
2x F∈∑第第第第三三三三章章章章 布爾函數(shù)布爾函數(shù)布爾函數(shù)布爾函數(shù)7定義定義 3。12 設(shè)f 關(guān)于關(guān)于α α 滿足擴散準(zhǔn)則滿足擴散準(zhǔn)則, 若對任意滿足f都滿足擴散準(zhǔn)則都滿足擴散準(zhǔn)則, 則稱則稱f 滿足設(shè)α ∈α ∈ F2n, 若若f(x+α若對任意滿足1≤ ≤ W (α α ) ≤ ≤ k的滿足k次擴散準(zhǔn)則次擴散準(zhǔn)則。+α)+ +f(x)是平衡的是平衡的,則稱則稱的α α , 一次擴散準(zhǔn)則就是嚴(yán)格雪崩準(zhǔn)則一次擴散準(zhǔn)則就是嚴(yán)格雪崩準(zhǔn)則。 第第第第三三三三章章章章 布爾函數(shù)布爾函數(shù)布爾函數(shù)布爾函數(shù)8定理定理 3。18設(shè)設(shè)f (x)是是n元布爾函數(shù)元布爾函數(shù), 則則f滿足滿足k次擴散準(zhǔn)則當(dāng)且僅當(dāng)對任意準(zhǔn)則當(dāng)且僅當(dāng)對任意α α , 1 ≤ ≤ W(α α) ≤ ≤ k,有∑次擴散有22( )( )( 1) F∈Sα?=第第第第三三三三章章章章 布爾函數(shù)布爾函數(shù)布爾函數(shù)布爾函數(shù)9證明證明由定義由定義3。11知知現(xiàn)代密碼學(xué)基本原則, f 滿足滿足k次擴散準(zhǔn)則當(dāng)且僅次擴散準(zhǔn)則當(dāng)且僅當(dāng)對任意當(dāng)對任意α α , 1 ≤ ≤ W(α α) ≤ ≤ k, 有即即 Cf(α α) = = 0。 由定理由定理3。
1:有f(x+ +α α) + +f(x)是平衡的是平衡的, 第第第第三三三三章章章章 布爾函數(shù)布爾函數(shù)布爾函數(shù)布爾函數(shù)()( )f x()( )f( )f()( )f( )f2( )f( )α( 1)?( )( 1)w( )( 1)λ( )w S( )( 1)λ( 1)?( )( 1) xfx F∈∑ ∑∑ ∑∑w x? +xx F∈w F∈Fwx w?w F∈Fx F∈ww F∈CSSSSα+αλλα?λλα?+?∈+∈==???=??=?∑∑∑