滿足特定平方和指標平衡布爾函數(shù)的性質(zhì)分析

周 宇

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

0 引言

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

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

1 基本概念

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

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

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

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

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

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

2 主要結果

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

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

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

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

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

文中就這兩類函數(shù)進行分析。

引理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的平衡布爾函數(shù)的絕對值指標的下界。

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

(i)t≥1;

證明 由于 f(x)是平衡函數(shù),在引理1的基礎上,為了方便分析設 Δf(αi)=8·li(li∈Z,0≤i≤2n-1),這里 αi∈ Fn2。則根據(jù)引理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中平衡布爾函數(shù)的 Δ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元平衡布爾函數(shù)進行分析,得到對應的下界,見表2。

表2 8元平衡布爾函數(shù)的 Δf下界

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

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

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

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

最后考慮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,則不存在這樣的平衡布爾函數(shù)。

3 結束語

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

[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.