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

周 宇

(保密通信重點(diǎn)實(shí)驗(yàn)室,四川成都610041)

0 引言

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

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

1 基本概念

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

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

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

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

2010年周宇等[2]將此推廣到兩個(gè)不同的布爾函數(shù)之間,引入互相關(guān)所對(duì)應(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í),對(duì)一個(gè)布爾函數(shù)f(x)∈Bn的擴(kuò)散補(bǔ)集A(所有非擴(kuò)散點(diǎn)形成的集合,稱(chēng)為擴(kuò)散補(bǔ)集)進(jìn)行分析時(shí),得到:

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

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

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

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

文中就這兩類(lèi)函數(shù)進(jìn)行分析。

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

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

首先分析第一類(lèi)滿(mǎn)足 σf=22n+1的平衡布爾函數(shù)的絕對(duì)值指標(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可知

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

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

可知

分兩方面討論:

注解1:定理1表明

(i)f(x)至少有1個(gè)擴(kuò)散點(diǎn);

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

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

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

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

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

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

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

其次分析第二類(lèi)滿(mǎn)足 σf=22n+2的平衡布爾函數(shù)的絕對(duì)值指標(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時(shí),有

可知

分兩方面討論:

注解2:定理2表明

(i)f(x)至少有1個(gè)擴(kuò)散點(diǎn);

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

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

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

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

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

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

3 結(jié)束語(yǔ)

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