滿足特定平方和指標平衡布爾函數的性質分析

周 宇

(保密通信重點實驗室,四川成都610041)

0 引言

密碼函數主要用在通信和密碼等領域,布爾函數是密碼函數中使用最廣泛的一類密碼函數。布爾函數的全局雪崩準則是基于擴散準則。為了克服擴散準則在某些點(局部性)上的自相關值,使布爾函數在整體上達到最優,1995年,Zhang Xianmo和Zheng Yuliang發現擴散性只能用來刻畫布爾函數在部分點的自相關值,而對其他點沒有要求,所以提出密碼函數的全局雪崩準則(GAC)[1]:絕對值指標和平方和指標。GAC的提出,使人們對SAC和PC有了更為理性的思考。SAC和PC對某些點上的自相關值要求苛刻,而對其它點卻不加限制,這導致密碼函數的局部安全性。而GAC從全局著眼,對所有點的自相關值都提出了要求。2010年周宇等[2]提出了互相關函數的全局雪崩準則,將GAC指標推廣到兩個不同的布爾函數之間,得到這個準則的上下界,同時也得到該指標與高階非線性度的關系。這兩個概念為進一步研究提出了新的研究方向,在設計和分析中如何去找到這類指標較小的平衡布爾函數是值得研究的課題之一。

文中從兩類達到較小的平方和指標的平衡布爾函數入手,研究對應的絕對值指標的下界,并對小變元函數給出其下界值。

1 基本概念

n元布爾函數f(x)是指從 Fn2到F2的一個映射,Bn表示所有n元布爾函數的全體。1995年Zhang和Zheng提出全局雪崩準則(GAC)。

定義1 設 f(x)∈Bn,則f(x)的平方和指標定義為[1]:

f(x)的絕對值指標定義為:

其中 f(x)的自相關函數定義為

2010年周宇等[2]將此推廣到兩個不同的布爾函數之間,引入互相關所對應的全局雪崩準則。

定義2 設 f(x),g(x)∈Bn,則 f(x)和g(x)的互相關平方和指標定義為:

2 主要結果

Zhang Xianmo和Zheng Yuliang在研究GAC指標時,對一個布爾函數f(x)∈Bn的擴散補集A(所有非擴散點形成的集合,稱為擴散補集)進行分析時,得到:

第一類函數:當 #A=2,變元 n為奇數時σf=22n+1。

第二類函數:當 #A=4,變元 n為偶數時σf=22n+2。

對每一類函數,都得到對應的函數表達式,但是這兩類函數有其局限性,這是由于研究的都是幾乎擴散函數(即在幾乎所有的點(排除非零點)上都滿足擴散性),一方面我們知道bent函數在所有點(排除非零點)上都滿足擴散性,但bent函數是非平衡的,算法設計中為了滿足Golomb偽隨機性,一般要求密碼部件是平衡的。另一方面,擴散點也不能太多,這種幾乎擴散函數在密碼算法中是不適用的,因為擴散性越好其對應的代數免疫性越低,這樣就不能抵抗代數攻擊。所以這里考慮一般的函數。

JSeberry和Zhang Xianmo等[3]在研究平衡布爾函數的非線性度和擴散時對變元為奇數的情況,給出#A=5的平方和指標,進一步印證上述結果。同時周宇等[4]在2012年提出一種基于修改bent函數和不相交譜的方法的平衡布爾函數構造方法,得到了變元在偶數情況下其平方和指標可達到σf=22n+2。同時Stanica和Sung等[5]得到在偶數變元情況下平方和指標達到σf=22n+2的平衡布爾函數,但是這些構造方法都沒有給出在一般情況下相反的問題:即平方和指標達到σf=22n+2時對應的平衡布爾函數的絕對值指標。

文中就這兩類函數進行分析。

引理1 設 f(x)∈Bn(n≥3),wt(f)≡0 mod 2。則對任意的 α∈ Fn2有 Δf(α)≡0 mod 8。

引理2[2]設f(x)∈Bn(n≥3),則

首先分析第一類滿足 σf=22n+1的平衡布爾函數的絕對值指標的下界。

定理1 設 f(x)∈ Bn(n ≥3)且 wt(f)=2n-1,t=#{α∈ Fn2:Δf(α)≠0}。若 σf=22n+1,則

(i)t≥1;

證明 由于 f(x)是平衡函數,在引理1的基礎上,為了方便分析設 Δf(αi)=8·li(li∈Z,0≤i≤2n-1),這里 αi∈ Fn2。則根據引理2可知

進一步在不引起混淆的情況下設 l0=α0=(0,0,…,0)為 Fn2中0向量,此時對應的 Δf(α0)=2n,對其它的做如下假設(這個假設不影響對問題的分析):li≠0(1≤i≤t),li=0(t+1≤i≤2n-1)。則式(1)簡化為:

當 σf=22n+1時 ,有

可知

分兩方面討論:

注解1:定理1表明

(i)f(x)至少有1個擴散點;

表1 定理1中平衡布爾函數的 Δf下界

表1表明:當7≤n≤30時,Δf下界至少大于2n/2。

推論1 設 f(x)∈Bn(n≥3)且 wt(f)=2n-1,σf=22n+1。若滿足 m階擴散準則,則

特別地,在分組密碼的S盒中用得最多的是8入8出,這里就對 n=8元平衡布爾函數進行分析,得到對應的下界,見表2。

表2 8元平衡布爾函數的 Δf下界

注意:m=8對應的是bent函數,是非平衡的,這里不考慮。

在設計一個布爾函數時希望絕對值指標 Δf越小越好,根據表2可知擴散階越高越好,但同時也考慮其它密碼學指標,例如代數免疫、相關免疫、代數厚度等,而不能僅僅認為擴散階越高越好。

其次分析第二類滿足 σf=22n+2的平衡布爾函數的絕對值指標的下界。

定理2 設 f(x)∈ Bn(n ≥3)且 wt(f)=2n-1,t=#{α∈ Fn2:Δf(α)≠0}。若 σf=22n+2,則

(i)t≥1;

證明 在定理1的基礎上,當 σf=22n+2時,有

可知

分兩方面討論:

注解2:定理2表明

(i)f(x)至少有1個擴散點;

推論2 設 f(x)∈Bn(n≥3)且 wt(f)=2n-1,σf=22n+1。若滿足 m階擴散準則,則

注解3:定理1和定理2的結果改進了Sung等[6]對滿足一定擴散階的平衡布爾函數的平方和指標下界,文中給出絕對值指標的下界。同時周宇等在文獻[7]中給出這類函數的自相關分布特征。結合Zhang Xianmo和Zheng Yuliang在文獻[8]中的結果,可知定理1和定理2中t=3,6時是不存在這樣的函數;t=4時變元n為偶數;t=5時變元 n為奇數。

最后考慮t取特殊值的情況:

推論3 設 f(x)∈ Bn(n≥3)且 wt(f)=2n-1,t=#{α∈ Fn2:Δf(α)≠0},t=4。

(i)若 σf=22n+1,則對任意的 α∈Fn2有|Δf(α)|∈{2n-1,0}。此時有 Δf=2n-1。

(ii)若σf=22n+2,則不存在這樣的平衡布爾函數。

3 結束語

達到一定的平方和指標的布爾函數是序列密碼中的一個研究方向,文中給出2類達到較小平方和指標的布爾函數的絕對值指標的下界,對密碼函數部件的設計和分析有一定理論指導,這些結果改進了已有的一些結果,所以在后續研究中重點是如何去構造這類達到最小平方和指標的布爾函數。同時還應當考慮具有相同平方和指標(或者相同自相關分布[9])的布爾函數密碼學性質,這些對設計實用的布爾函數具有重要的意義。

[1] X M Zhang,Y L Zheng.GAC—the criterion for global avalanche characteristics of cryptographic functions[J].Journal for Universal Computer Science,1995,(5):316-333.

[2] Yu Zhou,Min Xie,Guozhen Xiao.On the global avalanche characteristics of two Boolean functions and the higher order nonlinearity[J].Information Sciences,2010,180:256-265.

[3] J Seberry,X M Zhang,Y Zheng.Nonlinearity balanced Boolean functions and their propagation characteristics[C].In Advancesin Cryplogy-CRYPTO'93,LNCS.773:49-60,Springer-Verlag,Berlin,Heidelberg,New York,1994.

[4] Yu Zhou,Xinfeng Dong,Wenzheng Zhang,et al.New bounds on the sum-of-squares indicator,Communications and Networking in China[R].ChinaCom 2012.Fourth International Conference,8-10,Aug,2013:173-178.

[5] P Stanica S H Sung.Improving the nonlinearity of certain balanced Boolean functions with good local and global avalanche characteristics[J].Information Processing Letters,2001,79:167-172.

[6] S H Sung,S Chee,C Park.Global avalanche characteristics and propagation criterion of balanced Boolean functions[J].Information Processing Letters,1999,69:21-24.

[7] Yu Zhou,Weiguo Zhang,Juan Li,et al.The auto-correlation distribution of balanced Boolean functions[J].Frontier of Computer Sciences,2013,7(3):272-278.

[8] X M Zhang,Y L Zheng.Characterizing the structures of cryptographic functions satisfying the propagation criterion for almost all vectors[J].Designs,Codes and Cryptography.1996,7:111-134.

[9] Yu Zhou.On the distribution of auto-correlation value of balanced Boolean functions[J].Advances in Mathematics of Communications,2013,7(2):335-347.