周 宇

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

0 引言

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

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

1 基本概念

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

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

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

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

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

定義2 設(shè) f(x),g(x)∈Bn,則 f(x)和g(x)的互相關(guān)平方和指標(biāo)定義為:

2 主要結(jié)果

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

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

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

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

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

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

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

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

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

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

(i)t≥1;

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

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

當(dāng) σf=22n+1時 ,有

可知

分兩方面討論:

注解1:定理1表明

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

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

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

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

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

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

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

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

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

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

(i)t≥1;

證明 在定理1的基礎(chǔ)上,當(dāng) σf=22n+2時,有

可知

分兩方面討論:

注解2:定理2表明

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

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

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

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

推論3 設(shè) 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 結(jié)束語

達(dá)到一定的平方和指標(biāo)的布爾函數(shù)是序列密碼中的一個研究方向,文中給出2類達(dá)到較小平方和指標(biāo)的布爾函數(shù)的絕對值指標(biāo)的下界,對密碼函數(shù)部件的設(shè)計和分析有一定理論指導(dǎo),這些結(jié)果改進了已有的一些結(jié)果,所以在后續(xù)研究中重點是如何去構(gòu)造這類達(dá)到最小平方和指標(biāo)的布爾函數(shù)。同時還應(yīng)當(dāng)考慮具有相同平方和指標(biāo)(或者相同自相關(guān)分布[9])的布爾函數(shù)密碼學(xué)性質(zhì),這些對設(shè)計實用的布爾函數(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.