偶變元嚴格幾乎最優彈性布爾函數的High-Meets-Low 構造*

王飛鴻, 孫玉娟, 董雪雯, 張衛國

1.西安電子科技大學 空天地一體化綜合業務網全國重點實驗室, 西安710071

2.武漢船舶通信研究所, 武漢430200

1 引言

布爾函數在對稱密碼學中具有極為重要的作用, 如流密碼中的偽隨機數生成器、分組密碼中的S 盒、Hash 函數等都可以通過適當的非線性布爾函數的組合來設計.布爾函數的安全性指標是衡量其密碼學性質好壞的依據.在流密碼設計中被廣泛接受的布爾函數安全性指標主要有: 平衡性、適當階數的相關免疫性、高非線性度、高代數次數、高代數免疫階、高快速代數免疫階等, 這些指標反映了密碼抵抗各種類型攻擊的能力.例如, 在流密碼系統設計中, 為了抵抗最佳仿射逼近攻擊[1], 布爾函數應具有高非線性度; 為了抵抗相關攻擊[2], 布爾函數應具有適當階數的相關免疫性[3].平衡性是設計用于密碼場景的布爾函數時需滿足的基本性質.同時具有平衡性和相關免疫性的布爾函數, 稱之為彈性函數.平衡的t階相關免疫函數, 稱為t階彈性函數.非線性度為Nf的n元t階彈性布爾函數f, 在本文中簡稱為(n,t,Nf) 函數.

布爾函數的彈性階和非線性度之間存在較強的制約關系, 較早指出存在這種制約關系的學者是Meier等人[4]與Ding[1].上世紀80 年代中期以來, 如何構造高非線性度的彈性布爾函數是一個重要的研究課題[5–21], 彈性布爾函數的非線性度的緊上界是尚未解決的公開難題.

本文給出了在偶數個變元情形下嚴格幾乎最優彈性布爾函數的HML 構造方案, 并描述了兩例參數分別為(22,4,221?210?29) 和(30,4,229?214?212) 的彈性函數的構造細節, 說明了由本文方法所得函數的參數可以優于文獻[10] 中由GMM 構造法所得函數的參數.

本文其余部分安排如下: 第2 節介紹了布爾函數及HML 構造的相關知識; 第3 節給出偶變元嚴格幾乎最優的彈性布爾函數的HML 構造方案;第4 節給出了(22,4,221?210?29)函數和(30,4,229?214?212)函數的構造細節, 并與文獻[10] 中的結果進行比較; 第5 節總結全文.

2 預備知識

2.1 布爾函數

n元布爾函數定義為從Fn2到F2的一個映射.令Bn表示所有n元布爾函數構成的集合.用F2上的一個長為2n的向量

且形如式(1)的表示形式存在且唯一, 稱該表示形式為f的代數正規型, 其中λI ∈F2,X=(x1,x2,···,xn)∈Fn2.f(X) 的代數次數是使得λI= 1 的最大|I| 值, 記為deg(f), 其中|I| 表示集合I的基數.若deg(f)≤1, 則稱f是仿射函數.設ω= (ω1,ω2,···,ωn).將向量ω和X的內積記為:ω·X=ω1x1+ω2x2+···+ωnxn.顯然,ω·X是常數項為0 的仿射函數.布爾函數f ∈Bn在ω點的Walsh 譜值定義為

則稱f為嚴格幾乎最優函數.

設n元布爾函數f(X) 中x1,x2,···,xn是 F2上均勻分布的獨立隨機變量, 若f(X) 與x1,x2,···,xn中任意t個變元統計獨立, 則稱f(X) 是t階相關免疫函數.平衡的相關免疫函數稱為彈性函數, 平衡布爾函數的相關免疫階稱為布爾函數的彈性階.文獻[22] 給出彈性函數的頻譜特征, 這一結論被稱為Xiao-Massey 定理.

引理1[22](Xiao-Massey 定理) 布爾函數f ∈Bn是t階彈性函數當且僅當對任意ω ∈Fn2, 0≤wt(ω)≤t, 都有Wf(ω)=0.

下面介紹一種在HML 等構造法中需要使用到的重要工具: 殘缺Walsh 變換.

定義2[15]設S是Fn2上的非空真子集,X ∈S.稱函數fS:S →F2是S上的n元殘缺布爾函數.fS在ω ∈Fn2點的殘缺Walsh 變換定義為

若有序多重集WfS={FWfS(ω)|ω ∈Fn2}中元素是按ω的字典序排序的, 則稱WfS為fS的殘缺Walsh 譜.

殘缺Walsh 譜有兩條重要性質, 見引理2 和3.

則有

引理 3[15]設f和fSi是引理2 中定義的函數, 若對任意的ω ∈Fn2, 0≤wt(ω)≤t, 總有FWfSi(ω)=0,i=1,2,···,d成立, 則f是t階彈性函數.

直和構造是一種基本的布爾函數構造方法, 由直和構造所得函數的彈性階滿足如下關系:

是s+m元t1+t2階彈性函數.

證明: 設α ∈Fs2,β ∈Fm2.由公式(2)可知Wh(α,β)=Wc·X(α)·Wg(β).由wt(c)=t2,易知c·X是t2?1 階彈性函數, 又g是t1階彈性函數.注意到wt(α,β)=wt(α)+wt(β), 故當0≤wt(α,β)≤t1+t2時, 必有0≤wt(α)≤t2?1 或0≤wt(β)≤t1.由引理1, 有Wc·X(α) = 0 或Wg(β) = 0.從而Wh(α,β)=0, 即h(X,Y) 是一個s+m元t1+t2階彈性函數.

2.2 HML 構造法描述

文獻[15]中基于PW 函數(或KY 函數)給出奇數個變元的非線性度嚴格幾乎最優彈性函數的HML構造方案.由于構造方案中需要在向量空間的不同劃分上構造殘缺布爾函數, 我們給出例1 便于讀者理解這種“劃分”.下面描述基于PW 函數的HML 構造法.

其中{U1,U2,U3,U4}是F152的一個劃分.并統計Fu2×Uj中漢明重量不小于t+1 的向量個數, 其中j=1,2,3,u ≥0, 即

3 偶變元嚴格幾乎最優彈性函數HML 構造的一般性結論

文獻[11] 中給出的一種偶變元高非線性度1 階彈性函數的構造方法, 這些函數的非線性度非常接近bent 函數的非線性度,這是1 階彈性函數目前所能達到的最高非線性度.因此我們選取它作為偶數個變元的HML 構造中的初始函數, 并根據引理4 修改集合T1的取值范圍為T1={η|wt(η)≥t ?1,η ∈Fk2},實現了偶變元的嚴格幾乎最優彈性函數的HML 構造, 下面給出該構造的一般性結論.

設g ∈Bm是由文獻[11] 構造的m元1 階彈性函數(m ≥8 且為偶數), 其Walsh 譜取值有

同時成立.從而可以分別建立從Ei到Ti的單射Φi, 其中i= 1,2,3,4.設X= (x1,x2,···,x2k)∈F2k2及Y ∈Fm2, 分別在Si上構造四個n元殘缺布爾函數:

由引理3,f是t階彈性函數.由式(5)得

成立, 則存在(n,t,2n?1?2n/2?1?2n/2?2) 嚴格幾乎最優彈性函數.

定理2 對g ∈Bm, 在m ≥10 且m ≡2 mod 4 時, 有

證明: 與定理1 的證明相似.

4 兩例高非線性度彈性布爾函數的具體構造

為了便于讀者理解, 下面給出(22,4,221?210?29) 函數和(30,4,229?214?212) 函數的構造細節,并與文獻[10] 中的結果進行比較.

4.1 (22,4,221 ?210 ?29) 函數的構造

首先選取一個文獻[11] 中構造的1 階彈性函數g1∈B8, 其真值表的16 進制表示為

注意到集合U4中向量對應的Walsh 譜振幅值與其它三個集合U1,U2,U3中向量對應的Walsh 譜振幅值間差值的二進制展開分別是: 24?0=24+23, 24?8=24, 24?16=23.這些差值中有兩種2 的冪決定了F222被劃分為三個集合S1,S2和S3.

第一步: 在S1上構造22 元殘缺布爾函數fS1.

根據引理4, 由于所構造函數的彈性階是4, 把F72中重量不小于3 的向量作成集合T1, 即

由引理4 及T1的定義有

第二步: 在S2上構造22 元殘缺布爾函數fS2.

首先統計F82中使函數g1的Walsh 譜振幅值分別為0, 8 和16 時重量為τ的向量個數, 其中0≤τ ≤8, 即

表1 中列出了函數g1對應的Nj(τ) 值,j=1,2,3.

表1 函數g1 的Nj(τ) 值, j = 1,2,3Table 1 Nj(τ) for g1 function, j = 1,2,3

從而對任意u ≥0, 式(6)中Γj(u,t) 的數量為

由式(6),T2中的向量都不小于5.由式(15)得

第三步: 在S3上構造22 元殘缺布爾函數fS3.

令

相應地, 由式(15)得

fS3的殘缺Walsh 譜為

由定義1, 函數f為嚴格幾乎最優函數.

與由文獻[10] 中GMM 構造法得到的函數比較見表2.在非線性度相同的前提下, 本文中構造的22元嚴格幾乎最優布爾函數的彈性階更優.

表2 嚴格幾乎最優布爾函數的彈性階和非線性度比較Table 2 Resiliency and nonlinearity comparison of strictly almost optimal functions

通過該構造可以得到一個(22,4,221?210?29) 彈性函數, 其真值表見文獻[23], 讀者可自行驗證其4 階彈性和Walsh 譜分布的正確性.

4.2 (30,4,229 ?214 ?212) 函數的構造

通過文獻[11] 構造的一個1 階彈性函數g2∈B12, 其真值表見附錄, 其Walsh 譜振幅值分布如下

其中U1∪U2∪U3∪U4∪U5=F122且Ui ∩Uj=?對任意的1≤i ＜j ≤5 成立.由引理1 知, 其Walsh譜還滿足

注意到集合U5中向量對應的Walsh 譜振幅值與其它四個集合U1,U2,U3,U4中向量對應的Walsh 譜振幅值間差值的二進制展開分別是: 80?0 = 26+24, 80?16 = 26, 80?48 = 25, 80?64 = 24.這些差值中有三種2 的冪決定了F302被劃分為四個集合S1,S2,S3和S4.

相應地, 統計了F122中使函數g2的Walsh 譜振幅值分別為0, 16, 48 和64 時重量為τ的向量個數,其中0≤τ ≤12, 即

表3 中列出了函數g2對應的Nj(τ) 值,j=1,2,3,4.

表3 函數g2 的Nj(τ) 值, j = 1,2,3,4Table 3 Nj(τ) for g2 function, j = 1,2,3,4

從而對任意u ≥0, 式(6)中Γj(u,t) 的數量為

其中v=min{t,12},λ=min{u,t ?τ}.分別令

與由文獻[10] 中GMM 構造法得到的函數比較見表4.

表4 嚴格幾乎最優布爾函數的彈性階和非線性度比較Table 4 Resiliency and nonlinearity comparison of strictly almost optimal functions

在彈性階相同的前提下, 本文中構造的30 元嚴格幾乎最優布爾函數的非線性度更優.

5 結論

自上世紀80 年代中期, 如何構造高非線性度的彈性布爾函數一直是一個重要的研究課題, 文獻[15]引入了“殘缺布爾函數” 和“殘缺Walsh 變換” 的概念, 提出HML 密碼函數構造法, 首次使奇數個變元的彈性布爾函數的非線性度大幅提高到2n?1?2(n ?1)/2+5·2(n?11)/2.本文推廣該構造技術至偶數個變元的情形, 實現了偶變元嚴格幾乎最優的彈性布爾函數的HML 構造方案, 構造出了非線性度為2n?1?2n/2?1?2n/2?m/4和2n?1?2n/2?1?2n/2?(m/2?1)/2(m ≥8 且為偶數) 的嚴格幾乎最優彈性函數, 并給出兩個具有目前已知最高非線性度的彈性函數的例子, 其參數分別為(22,4,221?210?29) 和(30,4,229?214?212).