布爾函數(shù)相關(guān)免疫性與平衡性關(guān)系的研究

李衛(wèi)衛(wèi)

（上海政法學(xué)院 現(xiàn)代教育技術(shù)中心，上海 201701）

1 引言

布爾函數(shù)的相關(guān)免疫性是保證密碼系統(tǒng)具有良好安全性的重要性質(zhì)。布爾函數(shù)的導(dǎo)數(shù)（偏導(dǎo)數(shù)）的概念和性質(zhì)是人們早已熟知的，但導(dǎo)數(shù)（偏導(dǎo)數(shù)）只能反映布爾函數(shù)內(nèi)部一個(gè)方面值的結(jié)構(gòu)特點(diǎn)。因而在討論布爾函數(shù)的相關(guān)免疫性時(shí)，沒有什么用途。在文獻(xiàn)[1,2]中引入布爾函數(shù)的e導(dǎo)數(shù)能刻畫布爾函數(shù)內(nèi)部值的另一種特點(diǎn)的結(jié)構(gòu)，將其和導(dǎo)數(shù)一起深入到布爾函數(shù)的內(nèi)部結(jié)構(gòu)中，從布爾函數(shù)內(nèi)部不同特點(diǎn)的結(jié)構(gòu)對(duì)相關(guān)免疫性的影響來分析布爾函數(shù)的平衡性與相關(guān)免疫性的關(guān)系，可得出有關(guān)布爾函數(shù)相關(guān)免疫性有意義的新結(jié)果，同時(shí)，也為更好地研究布爾函數(shù)的密碼學(xué)性質(zhì)保證密碼系統(tǒng)的安全性指引了一個(gè)新的研究方向。

2 預(yù)備知識(shí)

首先，對(duì)e導(dǎo)數(shù)的概念和與本文有關(guān)的性質(zhì)做簡要敘述。

定義1[1]布爾函數(shù) f( x)的多元e導(dǎo)數(shù)為

若r=1，則布爾函數(shù)f( x)對(duì)單個(gè)變元xi的e導(dǎo)數(shù)記為ef( x)/exi，即

定義2[2]布爾函數(shù)f( x)對(duì)單個(gè)變元xi的導(dǎo)數(shù)記為df( x)/dxi，定義為

定義3[2]布爾函數(shù)f( x)對(duì)多個(gè)變元xi的導(dǎo)數(shù)記為df( x)/d(xi1,···xir),即

下面不加證明地給出2個(gè)有關(guān)導(dǎo)數(shù)和e導(dǎo)數(shù)的性質(zhì)引理。

引理1[3]布爾函數(shù)f( x)是平衡H布爾函數(shù)，當(dāng)且僅當(dāng)w(df( x)/dxi)=2n-1，且w(e f( x)/exi)=2n-2,i=1,2,···,n

引理2[3]對(duì)布爾函數(shù)f( x),

其取值范圍i=1,2,···,n。

3 平衡布爾函數(shù)的一階相關(guān)免疫性的判定

通過對(duì)平衡布爾函數(shù)一階相關(guān)免疫性的研究，可以簡化檢測平衡布爾函數(shù)是否一階相關(guān)免疫的計(jì)算，能很容易地構(gòu)造高維一階相關(guān)免疫的平衡布爾函數(shù)，從而得出許多重要的密碼學(xué)性質(zhì)定理。

定理1 n維平衡布爾函數(shù)f( x), x=(x1,x2,···,xn)由2個(gè)n-1維布爾函數(shù)fp(x)和fq(x)，其中x=(x1,x2,···,xn)級(jí)聯(lián)構(gòu)成：f( x)=(1+x1)fp(x)+x1fq(x)。

1) 平衡布爾函數(shù)f( x)若有

則f( x)是一階相關(guān)免疫函數(shù)。

2) 若平衡布爾函數(shù)f( x)是一階相關(guān)免疫函數(shù)，則w( fp( x))n-1=w( fq( x))n-1=2n-2,且w(e fp(x)exn)=w(e fq(x)exn)。

證明 ① 當(dāng)式（1）成立，且f( x)是平衡布爾函數(shù)，則由偏導(dǎo)數(shù)的定義便知，對(duì)an∈GF(2)[3]（GF(2)表示伽羅華域），有w( f( x)|xn=an)=2-1w( f( x))=2n-2。取a∈GF(2)n,且w( a)=n，則式（1）等價(jià)于w( f( x+a)+f( x ))=0,f( x+a)=f( x)。故對(duì)任意xi, i=1,2,···,n ，有

由于w( f( x))=w( xif( x))+w((1+xi) f( x))=2n-1，再由式（2）及f( x+a)的意義便知

故對(duì)任意xi, i=1,2,···,n ，有

故知f( x)是一階相關(guān)免疫函數(shù)。

② 若f( x)是一階相關(guān)免疫的平衡布爾函數(shù)，則必有式（4）成立，于是在式（4）中，取xi為x1，便知

而在式（4）中，取xi為xn-1和1+xn-1，便知：w(e fp(x)exn)=w(e fq(x)exn)。

4 平衡布爾函數(shù)二階相關(guān)免疫性的判定及其構(gòu)造

定理1說明一階相關(guān)免疫的平衡布爾函數(shù)（且非線性函數(shù)[4]）是易于構(gòu)造的，那么是否存在并同樣易于構(gòu)造出二階相關(guān)免疫的平衡布爾函數(shù)？下面來討論這一問題。給出一個(gè)平衡布爾函數(shù)一階相關(guān)免疫的充分性定理。

定理2 f( x)為平衡布爾函數(shù)，

且w( ef( x)exn)=0，則f( x)是一階相關(guān)免疫函數(shù)。

證明 若式（5）成立，則f( x)在xx···x00～xx···x11取值范圍內(nèi)對(duì)f( x)均有xn=0和xn=1處的值相等。又由于f( x)為平衡布爾函數(shù)，故對(duì)an∈GF(2)，有

由于w(e f( x)/exn)=0，故f( x)在上述各取值范圍內(nèi)的值均相等，均為

故知

由各取值范圍內(nèi)的值均相等及式（6）和式（7）可知，對(duì)xi( i≠n-1,n)也有

故由式（6）、式（8）和式（9）可知，對(duì)ai∈GF(2)n[5]，有w( f( x)|xi=ai)=2n-2，即f( x)是一階相關(guān)免疫的平衡布爾函數(shù)。

現(xiàn)在來討論平衡布爾函數(shù)二階相關(guān)免疫的判定問題。該問題也是在密碼學(xué)領(lǐng)域中一直沒有得到很好解決的難點(diǎn)問題之一，而下面的定理3、定理4給出了一個(gè)較之簡單的解決方法。同時(shí)，也給出了一個(gè)構(gòu)造三階相關(guān)免疫[6]的平衡布爾函數(shù)的方法。

定理3 設(shè)g( x), x=(x1, x2,···,xn-2)是n-2元的一階相關(guān)免疫的平衡布爾函數(shù)，則n元布爾函數(shù)f( x)=g( x)+xn-1+xn是三階相關(guān)免疫的平衡布爾函數(shù)。

證明 先證明對(duì)任意n-2元布爾函數(shù)g( x),n元布爾函數(shù)f( x)=g( x)+xn-1+xn都是一階相關(guān)免疫的平衡布爾函數(shù)。

故w( f( x))=2-1w(df( x)dxn)+w(e f( x)exn)=2n-1，可知f( x)是平衡布爾函數(shù)。

由于

由f( x)是平衡布爾函數(shù)，式（10）和式（11）及定理2可知，f( x)是一階相關(guān)免疫的平衡布爾函數(shù)。于是有

由開始處證明的結(jié)論便知，對(duì)i≠j(i, j=1,2,···,n -2)時(shí)，

由式（12）知，對(duì)i≠j,當(dāng)i=n-1,j≠n或i=n, j≠n -1時(shí)，由g( x)的任意性有

或

而當(dāng)i=n-1,j=n時(shí)，由于g( x)是任意n-2元平衡布爾函數(shù)，故

由式（13）～式（16）可知f( x)是二階相關(guān)免疫平衡布爾函數(shù)。

同樣，對(duì)i≠j≠k(i, j, k=1,2,···,n-2)，由開始的證明可知，g( x)+xi+xj+xk是與xn-1,xn無關(guān)的n-2元布爾函數(shù)。及

故

同樣由式（12）及式（12）中g(shù)( x)是任意n-2元布爾函數(shù)，故對(duì)i≠j≠k,i, j, k中有1個(gè)而且只有1個(gè)變元是xn-1或xn，而其余2個(gè)變元均不為xn-1或xn。不妨設(shè)xi=xn-1或xn，則有

或

當(dāng)i≠j≠k(i, j, k=1,2,···,n-2)，且i, j, k中有1個(gè)為xn-1，1個(gè)為xn時(shí)，不妨設(shè)xi=xn-1，xj=xn，由于g( x)是一階相關(guān)免疫函數(shù)，故有

由式(17)～式(20)可知，f( x)是三階相關(guān)免疫的平衡布爾函數(shù)。

從定理3的證明，顯然可得到如下推論。

推論1 設(shè)g( x), x=(x1, x2,···,xn-2)是n-2元的平衡布爾函數(shù)，則n元布爾函數(shù)f( x)=g( x)+xn-1+xn是二階相關(guān)免疫的平衡布爾函數(shù)。

推論2 設(shè)g( x), x=(x1, x2,···,xn-2)是n-2元布爾函數(shù)，則n元布爾函數(shù)f( x)=g( x)+xn-1+xn是相關(guān)免疫的平衡布爾函數(shù)。

定理3實(shí)際上給出了一個(gè)構(gòu)造三階相關(guān)免疫的平衡布爾函數(shù)的方法[7]。判斷一個(gè)平衡布爾函數(shù)是二階相關(guān)免疫函數(shù)，判斷工作量是很大的，但定義了e導(dǎo)數(shù)以后，可以得到一個(gè)判斷平衡布爾函數(shù)二階相關(guān)免疫的較簡單方便的方法。因此有下面的定理。

定理4 設(shè)f( x)為非線性布爾函數(shù)，若

則f( x)是二階相關(guān)免疫的平衡布爾函數(shù)。

證明 由式（21）便知，f( x)是平衡布爾函數(shù)。

故f( x)+xi+xn一定與xn無關(guān)，所以f( x)一定為如下函數(shù)f( x)=g( x)+xn（其中g(shù)( x)與xn無關(guān)）。

同樣由于w(df( x)dxn-1)=2n，故對(duì)i=1,2,···,n-1,n，有

因此，f( x)+xi+xn-1一定與xn-1無關(guān)，故f( x)一定是如下函數(shù)。

其中，g1( x)+xn-1=g( x)，且g1( x)是與xn-1及xn無關(guān)的非線性函數(shù)。

由式（23）及推論2，便知f( x)是一階相關(guān)免疫的平衡布爾函數(shù)。當(dāng)i, j=1,2,···,n-2，且i≠j（其中r=n-1或r=n）。有

故知

取xj=xn-1,i=1,2,···n-1,n，有

故

同理，取xj=xn,i=1,2,···,n -1，也有

于是由式（27）、式（29）、式（30），便知對(duì)一切i=1,2,···,n-1,n,且i≠j，均有式（22），即w( f( x)+xi+xj)=2n-1，故知f( x)是二階相關(guān)免疫的平衡布爾函數(shù)。證畢。

由定理4的證明，還可得到如下推論。

推論3 設(shè)f( x)為非線性平衡布爾函數(shù)，若式（21）成立，則：

1) f( x)是一階相關(guān)免疫的平衡布爾函數(shù)；

2) f( x)一定為式（23），即f( x)=g1( x)+xn-1+xn（其中g(shù)1( x)是與xn-1、xn無關(guān)的n-2元布爾函數(shù)）；

3) 式若（27）成立，則g1( x)是n-2元平衡布爾函數(shù)。

推論3的第1個(gè)和第2個(gè)結(jié)論在定理4中已給出了詳細(xì)的證明，而第3個(gè)結(jié)論只需要由w( f( x)+xn-1+xn)=w( g1( x))n=2n-1，即知w( g1( x))n-2=2(n-2)-1，故結(jié)論成立。

由定理3和定理4顯然還可得到如下推論4。

推論4 若f( x)是三階相關(guān)免疫的平衡布爾函數(shù)，且滿足定理4的式（21）和式（22），則：f( x)=g1( x)+xn-1+xn，其中g(shù)1( x)是與xn-1、xn無關(guān)的n-2元一階相關(guān)免疫的平衡布爾函數(shù)。

從定理3和定理4的證明中可看出，在定理的這種構(gòu)造相關(guān)免疫函數(shù)的方法中，擴(kuò)散性[8]對(duì)免疫性沒有影響。

5 結(jié)束語

從文中的討論及結(jié)論可知，用e導(dǎo)數(shù)（e偏導(dǎo)數(shù)）和導(dǎo)數(shù)（偏導(dǎo)數(shù)）深入到布爾函數(shù)的內(nèi)部結(jié)構(gòu)中，可以較容易地得到相關(guān)免疫性的有意義的結(jié)論，得出一些有用的且能揭示滿足相關(guān)免疫性的平衡布爾函數(shù)結(jié)構(gòu)特點(diǎn)的性質(zhì)，如判斷相關(guān)免疫性、構(gòu)造相關(guān)免疫函數(shù)等密碼系統(tǒng)所需的內(nèi)容[9～11]。進(jìn)一步揭示了布爾函數(shù)優(yōu)良的密碼學(xué)性質(zhì)，為更好地研究布爾函數(shù)的密碼學(xué)性質(zhì)保證密碼系統(tǒng)的安全性和抗攻擊性打下了基礎(chǔ)。

[1] LI W W, WANG Z. The E-derivative of Boolean functions and its application in the fault detection and cryptographic system[A]. The 5th IIGSS Workshop, Kybetrnetes[C]. 2007.245-249.

[2] 溫巧燕, 鈕心忻, 楊義先. 現(xiàn)代密碼學(xué)中的布爾函數(shù)[M]. 北京: 科學(xué)出版社, 2000. 31-33.WEN Q Y, NIU X X, YANG Y X. Boolean Function in Modern Cryptoloy[M]. Beijing: Science Publishing House, 2000. 31-33.

[3] 李衛(wèi)衛(wèi), 王卓. E-導(dǎo)數(shù)和導(dǎo)數(shù)在布爾函數(shù)中的應(yīng)用[A]. 中國通信學(xué)會(huì)第五屆學(xué)術(shù)年會(huì)論文集[C]. 2008.267-270.LI W W, WANG Z. The application of derivative and E-derivative on H-Boolean functions[A]. The 5th China Institute of Communications Collected Papers[C]. 2008. 267-270.

[4] GUO Y F, LAN L Y. Balanced correlation-immune functions[J]. China Science and Technology Information, 2006, 20(8): 22-25.

[5] XIAO G Z, MASSEY J L. A spectral characterization of correlation-immune combining functions[J]. IEEE Trans on Inform Theory,1988, 34(3): 725-728.

[6] MO J. The construction and enumeration of symmetric balanced Boolean functions[J]. Journal of Beijing University of Posts and Telecommunications, 2006, 29(5): 5-8.

[7] 張串絨, 肖國鎮(zhèn). 一類布爾函數(shù)的性質(zhì)和應(yīng)用[J]. 通信技術(shù),2001,16(2):11-14.ZHANG C R, XIAO G Z. Properties and applications of a class of Boolean functions[J]. Communications Technology, 2001, 16 (2):11-14.

[8] HE L S. On Boolean functions with highest algebraic immune degree[J]. Chinese Journal of Computers, 2006, 29(9): 1579-1583.

[9] ZHANG W G, XIAO G Z. A characterization of algebraic immune Boolean functions[J]. Journal of Beijing University of Posts and Telecommunications, 2007, 30(5): 56-57.

[10] LUO W H, LI C. Algebraic immunity study of Boolean functions[J].Computer Engineering and Applications, 2007, 43(8): 59-60.

[11] SIEGENTHALER T. Correlation-immunity of nonlinear combining functions for cryptographic applications[J]. IEEE Trans, 1984, 30(5):776-778.