H布爾函數(shù)的相關(guān)免疫性與重量的關(guān)系

黃景廉，王卓

（西北民族大學(xué) 計算機科學(xué)與信息工程學(xué)院，甘肅 蘭州 730030）

1 引言

在現(xiàn)代密碼學(xué)中，楊義先教授提出的H布爾函數(shù)及對 H布爾函數(shù)的研究[1～4]，為布爾函數(shù)密碼學(xué)性質(zhì)的研究開辟了一個重要的、新的研究方向和研究領(lǐng)域。由于密碼系統(tǒng)抵抗各種攻擊的綜合能力的要求，要求設(shè)計的布爾函數(shù)要兼具擴散性、相關(guān)免疫性、代數(shù)免疫性等密碼學(xué)性質(zhì)?？芍?，直接討論H布爾函數(shù)的相關(guān)免疫性要比單純地、孤立地討論布爾函數(shù)的相關(guān)免疫性更有意義，能更直接地對擴散性、相關(guān)免疫性等直接進行綜合性研究。H布爾函數(shù)為各種密碼學(xué)性質(zhì)的綜合研究提供了一個方向性工具，有重要的密碼學(xué)價值。本文正是在這一方向上來討論擴散性、重量和相關(guān)免疫性的關(guān)系問題。在H布爾函數(shù)存在的重量范圍內(nèi)，H布爾函數(shù)的相關(guān)免疫性及其階數(shù)與它的重量有何直接關(guān)系的問題，是一個可以直接從H布爾函數(shù)的重量即可便捷地、明確判定H布爾函數(shù)的相關(guān)免疫性及其階數(shù)的重要問題，也是人們尚未顧及研究的問題。由于布爾函數(shù) f(x)的導(dǎo)數(shù)只能反映 f(x)在 df(x)/dxi=1（這時相應(yīng)有 ef(x)/exi=0）的取值情況，只有定義布爾函數(shù) f(x)的 e-導(dǎo)數(shù)[5～7]，才能反映 f(x)在 ef(x)/exi=1（而這時相應(yīng)有df(x)/dxi=0）時的另一種取值情況。本文將導(dǎo)數(shù)和與導(dǎo)數(shù)一起才能完整刻畫布爾函數(shù)的重量而定義的e-導(dǎo)數(shù)相結(jié)合作為研究工具，討論了在 2n-2≤w(f(x))≤2n-1+2n-2這一大的重量范圍內(nèi)，各種重量H布爾函數(shù)的相關(guān)免疫性及其階數(shù)的存在性問題，以及m (m≥2) 階相關(guān)免疫函數(shù)的階數(shù)m與函數(shù)的維數(shù)n有何關(guān)系的問題，得到一系列有用的明確結(jié)果。

2 預(yù)備性概念

布爾函數(shù)的導(dǎo)數(shù)是布爾代數(shù)、邏輯設(shè)計和密碼學(xué)中早已有定義的概念[8,9]，但e-導(dǎo)數(shù)是為刻畫布爾函數(shù)的重量才定義的新概念。為后面討論各種不同重量 H布爾函數(shù)的相關(guān)免疫性及其階數(shù)的需要和閱讀方便，下面給出導(dǎo)數(shù)和e-導(dǎo)數(shù)的定義以及它們與布爾函數(shù)、重量、擴散性、相關(guān)免疫性的一些最基本的簡單關(guān)系。

定義1 n元布爾函數(shù)f (x)對變元xi1,…, xir的e-導(dǎo)數(shù)，記為ef (x)/e(xi1,…, xir)，并定義為

其中，f(x)對單個變元xi(i=1, 2,…, n)的e-導(dǎo)數(shù)，記為ef(x)/exi, (i=1, 2,…, n)。經(jīng)簡單推導(dǎo)，有如下便于使用的形式：

由定義1和布爾函數(shù)的導(dǎo)數(shù)的定義，可直接得到下面的引理1和引理2。

引理1 有乘積關(guān)系df (x)/dxie f (x)/exi=0，(i=1,2,…, n)。

引理2 對任意n元布爾函數(shù)f(x)，有如下關(guān)系。

1) f (x)=f(x)?f(x)/?(xi1,…, xir)+ef(x)/ e(xi1,…, xir)，(1≤r≤n, 1≤ i1＜i2＜…＜ir≤n)。

2) f (x)= f(x)d f(x)/dxi+e f(x)/exi，(i=1, 2,…, n)。

3) w(f(x))=w(f(x)? f(x)/ ?(xi1,…, xir))+w(ef(x)/e(xi1,… , xir))=2-1w(?f (x)/ ? (xi1,… , xir))+w(e f(x)/e(xi1,…, xir))，(1≤r≤n, 1≤ i1＜i2＜…＜ir≤n)。

4) w(f (x))=w(f (x)df(x)/dxi)+w(ef (x)/ exi)=2-1w(df (x)/dxi)+w(ef (x)/exi)，(i=1, 2,…, n)。

[4]關(guān)于擴散性的定義顯然可由導(dǎo)數(shù)來描述，于是可得出關(guān)于f (x)的擴散性的等價定義引理3。

引理3 布爾函數(shù)f (x)滿足k (1≤k≤n)次擴散準(zhǔn)則，當(dāng)且僅當(dāng)對一切 xi1,…, xik，(1≤k≤n, 1≤i1＜i2…＜ik≤n)，有

w(?f(x)/?(xi1,…,xik)=2n-1，(1≤k≤n, 1≤ i1＜i2＜…＜ik≤n)

特別地，f (x)滿足一次擴散準(zhǔn)則，當(dāng)且僅當(dāng)對一切 xi，(i=1, 2,…, n)，有

由引理2的4)和引理3，可以用導(dǎo)數(shù)和e-導(dǎo)數(shù)來導(dǎo)出和參考文獻[4]p19、p133、p22關(guān)于平衡 H布爾函數(shù)的定義等價的定義，即引理4。

引理4 f(x)是平衡H布爾函數(shù)，當(dāng)且僅當(dāng)對一切 xi(i=1, 2,…, n)，有

w(df(x)/dxi)=2n-1，且 w(ef(x)/exi)=2n-2，(i=1, 2,…, n)

下面的引理5是一些文獻中已有的結(jié)果，這里引入是因為本文的討論要用。本文也將給出用導(dǎo)數(shù)性質(zhì)進行的證明。

引理5 布爾函數(shù)f(x)是H布爾函數(shù)的必要條件是 2n-2≤w(f (x))≤2n-1+2n-2。

證明 若f (x)是H布爾函數(shù)，則由引理3知，必有w(df (x)/dxn)=2n-1，又由引理2的4)知，必有w(f(x))≥2-1w(df (x)/dxn)=2n-2。

對w(f(x))≤2n-1+2n-2用反證法證明。

假設(shè) w(f(x))＞2n-1+2n-2，則有 w(1+f(x)) =2n-w(f(x))＜2n-2，故由引理 2，必有 w(d (1+f (x))/dxn) ＜2n-1。但由導(dǎo)數(shù)的性質(zhì)知，有 w(df(x)/dxn)=w(d (1+f(x))/dxn)＜2n-1，故由引理3知，這與f(x)是H布爾函數(shù)矛盾，故必有w(f(x))≤2n-1+2n-2。

故若 f(x)是 H 布爾函數(shù)，必有 2n-2≤w(f(x))≤2n-1+2n-2。

3 對 H布爾函數(shù)的重量與相關(guān)免疫性及其階數(shù)關(guān)系的討論

下面對2n-2≤w(f (x))≤2n-1+2n-2中所有H布爾函數(shù)的相關(guān)免疫性及其階數(shù)進行討論，同時給出一些有關(guān)的輔助性定理。

定理 1 對布爾函數(shù) f (x)（x∈GF(2)n，f (x)≠c，c∈GF(2)），若

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

證明 若 f(x)滿足式(3)，則對一切 i=1, 2,…, n，顯然必有

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

定理1及式(4)是參考文獻[4]p47中相關(guān)免疫的一個充要條件。式(3)是式(4)的一個充分條件，故式(3)只是f(x)一階相關(guān)免疫的充分條件，而不是必要條件。

例如：f(x)=x4+x1x4+x2x4+x2x5+x3x4+x4x5+x1x2x4+x1x2x5+x1x3x4+x1x3x5+x1x4x5+x2x3x4+x2x3x5+x3x4x5

f(x)是一階相關(guān)免疫函數(shù)，但不滿足式(3)。

定理2 若n元布爾函數(shù)f1(x)和f2(x)有w(f1(x))=w(f2(x))，且

則f1(x)和f2(x)的級聯(lián)函數(shù)

是n+1元一階相關(guān)免疫函數(shù)。

這里要注意的是，式(6)與一些參考文獻[4]P163、參考文獻[1]P16、P48中定義的級聯(lián)函數(shù)

不僅形式不同，而且有本質(zhì)的差異，這一點是顯然的。

證明 由于w(f1(x))=w(f2(x))，則由式(6)知有

由于式(5)，則由定理1知f1(x)和f2(x)均為n元一階相關(guān)免疫函數(shù)。故對i=1, 2,…, n，ai∈GF(2)，必有

結(jié)合式(8)、式(9)，便知f(x)是n+1元一階相關(guān)免疫函數(shù)。證畢。

定理1和定理2說明了一階相關(guān)免疫函數(shù)f(x)取值的某種對稱性。而由一階相關(guān)免疫定義的充要條件式(4)來看，這種對稱性是充分必要的性質(zhì)。顯然，定理2還可作進一步的多次級聯(lián)的推理。限于篇幅，這里省略。

有了上面的準(zhǔn)備，下面來討論各種重量H布爾函數(shù)的相關(guān)免疫性。

下面對w(f(x)) =2n-1+2n-2的m 階(m≥1)相關(guān)免疫性分成幾個定理來證明。

定理3 在w(f(x))=2n-1+2n-2的H布爾函數(shù)中，存在二階相關(guān)免疫的H布爾函數(shù)。

證明 為推導(dǎo)公式明晰的需要，這里要從一階相關(guān)免疫推起（因為由定理1和定理2知，一階肯定存在）。設(shè)f(x)是w(f(x))=2n-1+2n-2的H布爾函數(shù)，經(jīng)簡單推導(dǎo)，有

于是由式(10)、式(11)、引理4和相關(guān)免疫的條件（w(f (x) +xi)=2n-1）要求知，f(x)一階相關(guān)免疫，當(dāng)且僅當(dāng)

由于f(x)是H布爾函數(shù)，且w(f(x))= 2n-1+2n-2，則由引理2、引理3知，必有

w(df(x)/dxk)=2n-1，w(ef(x)/exk)=2n-1，(k=1, 2,…,n)，故由引理1知，必有

反之，顯然滿足式(13)的 H布爾函數(shù)，必有w(f(x))=2n-1+2n-2，w(ef(x)/exk)=2n-1。

又由于 w(xi) =2n-1, (i,=1,2,…,n)，故由式(13)知，必有

將式(14)展開，并由引理1知有

解式(12)、式(15)兩式組成的聯(lián)立方程組，則對一切 i,k=1,2,…,n，k≠i，有解

于是可知，當(dāng)f(x)一階相關(guān)免疫時，必有式(12)成立，而式(15)是必成立的。故必有式(16)兩式均成立。反之，若式(16)成立時，顯然將式(16)代入式(12)，式(12)必成立。故f(x)一階相關(guān)免疫，當(dāng)且僅當(dāng)式(16)成立。

由于式(15)必成立及式(16)是方程組唯一解，可知，式(16)中有一式成立，則另一式也必成立。于是取 fe(x)=ef(x)/exn，即 f1(x)是由 f(x)中 ef(x)/exn=1 且df(x)/dxn=0的那些值的函數(shù)，即有 w(fe(x))=w(ef(x)/exn)=2n-1。而滿足式(16)第一式的 fe(x)顯然是存在的。比如滿足定理 1的條件?fe(x)/? (x1,…,xn)=0，或滿足定理 2 的條件?fe(x)/? (x1,…, xn)=0，或滿足對定理 2進行推廣的條件?fe(x)/?(xn-2xn-1xn)=0 的 fe(x)（由于 w(fe(x)) = 2n-1，fe(x)) = ef(x)/exn）是存在的。這時，fe(x)顯然都滿足式(16)的第一式。故知相應(yīng)的f(x)也滿足式(16)的第一式，故f(x)也滿足式(16)的第二式。事實上，取?fe(x)/? (xn-2xn-1xn)=0的條件，便知f(x)可由f1(x)=xn-1+xn+xn-1xn；f2(x)=1 +xn-1+xn-1xn；f3(x) =1+xn-1xn；f4(x)=1+xn+xn-1xn這4個2元布爾函數(shù)按保證f (x)是H布爾函數(shù)，及滿足?fe(x)/?(xn-2xn-1xn)=0的某種次序逐步級聯(lián)構(gòu)成。故知由式(16)第一式，易于構(gòu)造出一階相關(guān)免疫函數(shù)，即一階相關(guān)免疫的w(f(x))= 2n-1+2n-2的H布爾函數(shù)是存在的。

于是取f(x)是w(f(x))=2n-1+2n-2的一階相關(guān)免疫的 H布爾函數(shù)，并對它的二階相關(guān)免疫性進行討論。經(jīng)簡單推導(dǎo)，有

由引理 4和式(12)、式(13)、式(17)、式(18)及二階相關(guān)免疫條件知，f(x)二階相關(guān)免疫，當(dāng)且僅當(dāng)

由于式(13)必成立，又由于 w(xixj)=2n-2, (i,j=1,2,…,n; i≠j)，故必有

求解式(19)、式(20)兩式組成的聯(lián)立方程組，則對一切 i,j,k=1,2,…,n，k≠i≠j，有解

顯然，通過和前面一階相關(guān)免疫相同的討論，可得結(jié)論：f(x) 二階相關(guān)免疫，當(dāng)且僅當(dāng)式(21)成立。

利用前面一階相關(guān)免疫時得出的 f1(x)、f2(x)、f3(x)、f4(x)，便能輕易構(gòu)造w(f(x))=2n-1+ 2n-2的二階相關(guān)免疫函數(shù)。為對任意n元能更清楚地證明存在性，先構(gòu)造2個低元的二階相關(guān)免疫函數(shù)，然后再逐步級聯(lián)成任意n元的方法來構(gòu)造。為此，先證明如下關(guān)系。

若fi1(x)和fi2(x)均為m(m≥1)階相關(guān)免疫n元H布爾函數(shù)，且w(fi1(x)+ fi2(x))= 2n-1，則 fi1(x) 和fi2(x)的級聯(lián)函數(shù)：

仍至少是m階相關(guān)免疫的n+1元H布爾函數(shù)，這是由于，對ωx (1≤w (ω)≤m)，經(jīng)推導(dǎo)，有 w(f(x)+ ωx)=w((1+x0) fi1(x)+ωx)+w(x0fi2(x)+ωx)- w(ωx)，故知 f(x)仍為m(m≥1)階n+1元布爾函數(shù)。又

即f (x)為n+1元H布爾函數(shù)。

于是由一階相關(guān)免疫時得到的 f1(x)、f2(x)、f3(x)、f4(x)，根據(jù)式(21)第一式的要求，按 f1(x)、f2(x)、f3(x)、f4(x)、f4(x)、f3(x)、f2(x)、f1(x)的次序構(gòu)造得ft(x)=1+ x1+ x2+ x3+ x4+ x5+ x1x2+ x1x3+ x1x4+ x2x3+x2x4+ x2x5+ x3x5+ x4x5

又按 f3(x)、f4(x)、f1(x)、f2(x)、f2(x)、f1(x)、f4(x)、f3(x)的次序構(gòu)造得 fr(x)=1+x2+x1x2+x1x3+x1x4+x2x3+x2x4+x2x5+x3x5+x4x5，其中，ft(x)和 fr(x)均為 n=5元二階相關(guān)免疫 H布爾函數(shù)。于是，將 ft(x)和 fr(x)按次序 ft(x)、fr(x)、fr(x)、ft(x)、fr(x)、ft(x)、ft(x)、fr(x)、…兩兩逐步級聯(lián)，便可得到任意 n元二階相關(guān)免疫的w(f(x))=2n-1+2n-2的H布爾函數(shù)。

故定理3成立。證畢。

從定理3證明中的式(16)、式(21)的推導(dǎo)，可以看出，w(f(x))= 2n-1+2n-2的H布爾函數(shù)的三階相關(guān)免疫的充要條件，也有

如果用歸納法來證明，顯然可以得到任意m (m≥1)階相關(guān)免疫的充要條件。限于篇幅，不作詳細(xì)推導(dǎo)，直接給出如下定理4。

定理4 w(f(x))=2n-1+2n-2的H布爾函數(shù)f (x)任意 m (m≥1)階相關(guān)免疫的充要條件是，對一切S1≠S2≠…≠Sm≠k，m≥1，有

現(xiàn)在需要用 w(f(x))=2n-1且 ef (x)/exn=2n-1，df(x)/dxn=0的布爾函數(shù)中，存在任意m (m≥1)階相關(guān)免疫布爾函數(shù)及定理 4，來證明存在w(f(x))=2n-1+2n-2的任意m (m≥1)階相關(guān)免疫H布爾函數(shù)。下面先給出定理3、定理4的推論，然后再給出解決上述問題的定理5。

推論1 若ft(x)和fr(x)均為m (m≥1)階相關(guān)免疫n元H布爾函數(shù)，且w(ft(x) +fr(x))=2n-1，則ft(x)和fr(x)的級聯(lián)函數(shù)：

仍至少是m階相關(guān)免疫的n+1元H布爾函數(shù)。

推論1在定理3中式(22)已證明，這里不再重復(fù)證明。

推論2 若f (x)為w(f(x))=2n-1+2n-2的H布爾函數(shù)，則f (x)為m (m≥1)階相關(guān)免疫函數(shù)的充分必要條件是式(24)的第二式（或第一式）

成立。

證明 從定理3的推導(dǎo)便可知，f (x)為m (m≥1)階相關(guān)免疫函數(shù)的充分必要條件是

由于w(f(x))=2n-1+2n-2，w(df(x)/dxk)=2n-1，w(ef(x)/exk)=2n-1，(k =1,2,…, n )，則定理 3 有式(13)必成立，于是和定理3由式(13)推出式(14)、式(15)相仿。由于w(xS1xS2…xSm)=2n-m，(1≤Si≤n，i=1,2,…, m)，必有

將式(26)、式(27)兩式聯(lián)立成方程組并解之，得唯一解式(24)，故f (x)為m (m≥1)階相關(guān)免疫函數(shù)的充分必要條件是式(24)的兩式均成立。由于式(24)是方程組式(26)、式(27)的唯一解，故推論2成立。

顯然，特別提出推論 2，是為以后判斷w(f(x))=2n-1+2n-2的H布爾函數(shù)f(x)是否m (m≥1)階相關(guān)免疫時，只需對ef (x)/exn=fS(x) 進行判斷，這比同時判斷式(24)的2個式子要省一半工作量。

定理 4和推論 2只是給出了判斷 w(f(x))=2n-1+2n-2的H布爾函數(shù)是不是m (m≥1)階相關(guān)免疫函數(shù)的充分必要條件，并沒有給出它存在的結(jié)論。但推論2給出了判斷它的存在性的簡便方法。為此，下面給出定理5。

定理5 在w(f(x))=2n-1，且w(ef(x)/exn) =2n-1，df(x)/dxn= 0的 n (n ≥3)元布爾函數(shù) f (x)中（即f(x)=ef(x)/exn），存在任意 m (m≥1) 階相關(guān)免疫函數(shù)，且相關(guān)免疫階數(shù)最高為m=n-2階，即

max mi= m=n-2

證明 由定理條件w(f(x))= w(ef(x)/exn) =2n-1，f(x)= ef(x)/exn，則當(dāng)n ≥3時，取f (x)滿足

顯然，即相應(yīng)有

則由定理1、定理2及推論1知，f(x)必為一階相關(guān)免疫函數(shù)。而且還可知，f(x)這時必定是由f21(x)=xn-1和 f22(x)=1+xn-1按式(25)讓 x0依次取為xn-2,xn-3,…, x2,x1逐步級聯(lián)得到的函數(shù)。而且由式(28)、式(29)知，f(x)必須在n≥3時，才至少是一階相關(guān)免疫的。有以上結(jié)果后，下面便可用歸納法來推導(dǎo)f(x)的表示式及相應(yīng)的相關(guān)免疫性質(zhì)。

當(dāng) n=3，即 x=xn-2xn-1xn時，利用式(25)，取x0=xn-2，對 f21(xn-1xn)= xn-1和 f22(xn-1xn)=1+xn-1作級聯(lián)，得

和

式(30)、式(31)中，f21(x)和 f22(x)是二元函數(shù)。顯然，f31(x)和f32(x) 仍然是仿射函數(shù)[3,6]（線性函數(shù)）。

根據(jù)相關(guān)免疫的定義[3]：f(x)為m階相關(guān)免疫，當(dāng)且僅當(dāng)對任意的1≤ i1≤i2≤…≤ir≤ n和滿足1≤w(ω)≤ m 的ω=(ω1,…, ωn)∈GF(2)n，

顯然可知，三元函數(shù)（即n=3）f31(x)和f32(x) 均為一階相關(guān)免疫線性函數(shù)，但一定不是二階相關(guān)免疫函數(shù)。

同樣，取n=4，即x=xn-3xn-2xn-1xn時，有

其中，f31(x)和 f32(x)是三元布爾函數(shù)。于是，顯然由相關(guān)免疫的定義式(32)可知，f41(x)和f42(x) 均為二階相關(guān)免疫線性函數(shù)，但一定不是三階相關(guān)免疫函數(shù)。

現(xiàn)在用歸納法，假設(shè)n=k時，依x0=xn-4, xn-5,…,xk的順序，按式(25)的級聯(lián)方式逐步級聯(lián)，得到的n=k元布爾函數(shù)為

且顯然fk1(x)和fk2(x)均為n-2=k-2階相關(guān)免疫函數(shù)。

則當(dāng)n=k+1時，按式(25)的級聯(lián)方式，對fk1(x)和fk2(x) 進行級聯(lián)，得

得到的仍是 k+1元線性函數(shù)（仿射函數(shù)），且顯然f(k+1),1(x)和f(k+1),2(x)是n-2=(k+1)-2= k-1階相關(guān)免疫函數(shù)。

故對于n元的，w(f(x))=w(ef(x)/exn)=2n-1的布爾函數(shù)f(x)中，存在m=n-2階相關(guān)免疫函數(shù)。

除由上面 f21(x)和 f22(x)逐步級聯(lián)構(gòu)成的w(f(x))=w(ef(x)/exn)=2n-1的函數(shù) f(x)外，尚可由(x)=0和(x)=1構(gòu)成的級聯(lián)函數(shù) f '(x)，由級聯(lián)式(25)可知， f '(x)一定少含變量xn-2，xn-1，xn3個，由于上面的函數(shù)是按二階相關(guān)免疫來構(gòu)造的，還必須滿足 w(f(x))=w(ef (x)/exn)=2n-1，所以顯然再不可能構(gòu)造出其他結(jié)構(gòu)的二階相關(guān)免疫函數(shù)了。故相關(guān)免疫階數(shù)一定小于m=n-2。限于篇幅，不詳證。故知，相關(guān)免疫階數(shù)最高為m=n-2。

由推論2和定理4，顯然可得到下面的定理6 。

定理6 在w(f(x))=2n-1+2n-2的H布爾函數(shù)中，存在任意m (1≤m≤n-2) 階相關(guān)免疫H布爾函數(shù)。

證明 設(shè) f(x)是 w(f(x))=2n-1+2n-2的 H 布爾函數(shù)，則顯然f (x)可由f1(x)=xn-1+ xn+xn-1xn；f2(x)=1+xn-1+xn-1xn；f3(x)=1+xn-1xn；f4(x)=1 +xn+xn-1xn這4個二元布爾函數(shù)逐步級聯(lián)構(gòu)成。這在定理3中已經(jīng)看到過。由引理2的2)，有

其中，fd(x)= f(x) df(x)/dxn；fe(x)=ef(x)/exn，且w(fd(x))=2n-2，w(fe(x))=w(ef(x)/exn)=2n-1。顯然，使 fe(x)=ef(x)/exn（w(fe(x))=w(ef(x)/exn)=2n-1）滿足定理5的式(28)、式(29)的f(x)是存在的，并且是易于由定理 3 中的 f1(x)、f2(x)、f3(x)、f4(x)按式(25)級聯(lián)構(gòu)造的。故由定理4知，可以構(gòu)造fe(x)是任意m (1≤m≤n-2) 階相關(guān)免疫函數(shù)。即有

其中，1≤w(ω)≤n-2=m，ω∈GF(2)n。故知有

于是，必有

又有 w((xSi+xSj)ef(x)/exn)=w(xSief(x)/exn)+w(xSjef(x)/exn)-2w(xSixSjef(x)/exn)=2-1w(ef(x)/exn)，故由式(41)知，必有

繼續(xù)這一推導(dǎo)，且由于又有

故由式(43)知，當(dāng)fe(x) = ef(x)/exn為m (1≤m≤n-2) 階相關(guān)免疫函數(shù)時，必有

其中，1≤S1＜S2＜…＜ Sm≤n。

由于fe(x)=ef(x)/exn是滿足定理5的式(28)、式(29)的要求，按定理5的方式構(gòu)造的，故fe(x)必如定理5中式(37)、式(38)的形式的如下函數(shù)：

故顯然有

故由式(44)、式(46)，知，必有

于是由式(47)，f (x)的構(gòu)成及推論2知，f (x)是w(f(x))=2n-1+2n-2的H布爾函數(shù)中的任意m (1≤m≤n-2)階相關(guān)免疫函數(shù)，證畢。

定理7 在w(f(x))=2n-2的H布爾函數(shù)中，存在任意m (1≤m≤n-2) 階相關(guān)免疫H布爾函數(shù)。

證明 設(shè)g(x)為w(g(x))=2n-1+2n-2的m (1≤m≤n-2)階相關(guān)免疫的H布爾函數(shù)。則由相關(guān)免疫的定義知，對ωx(1≤w(ω)≤m, 1≤m≤n-2)，有w(g(x)+ωx)=2n-1。取 f(x)=1+g(x)，有

故由式(48)、式(49)、式(50)知，f(x)是 w(f(x))=2n-2的任意m (1≤m≤n-2) 階相關(guān)免疫的H布爾函數(shù)。證畢。

現(xiàn)在來討論 2n-2＜w(f(x))＜2n-1+2n-2中 H 布爾函數(shù)的相關(guān)免疫性。

定理 8 在 w(f(x))=w(ef(x)/exn)＜2n-1（即 f(x) =ef(x)/exn, df(x)/dxn=0）的布爾函數(shù)中，不存在二階相關(guān)免疫函數(shù)。

證明 由于定理條件有f(x)=ef(x)/exn，可知f (x)必由f10(xn-1xn) =xn-1, f20(xn-1xn)=1+xn-1,f30(xn-1xn)=0,f40(xn-1xn)=1按式(6)、式(25)，即定理5中的級聯(lián)方式逐步級聯(lián)構(gòu)成。由定理1、定理2及其推理可知，若f10(xn-1xn) 與 f20(xn-1xn) 成對出現(xiàn)，f30(xn-1xn)和f40(xn-1xn) 成對出現(xiàn)，其余均取0級聯(lián)時，f(x)必為一階相關(guān)免疫函數(shù)。由于w(f(x))=w(ef(x)/exn)＜2n-1，因而級聯(lián)時要有較多的 0值二元函數(shù)參與級聯(lián)。于是 f(x)必為如下形式：

其中，xn-r是xi( i =1,2,…,n-1 ) 中的某一個， f '(x)中既含有xi( i =1,2,…,n-1 ) 中除xn-r外的其余某些一次函數(shù)項，也含有不包括xn的一些二次及二次以上的函數(shù)項（其實，一定含有xn-1這一項，只是為了一般性的考慮，以xn-r來進行標(biāo)記）。以上所述的結(jié)果，只需做一些維數(shù)n較小的級聯(lián)即可明顯得出，然后通過歸納法即可輕易證明。由于結(jié)果很明顯，限于篇幅，不再詳證。由于 f(x)一階相關(guān)免疫，故由相關(guān)免疫的定義及式(51)知，必有

現(xiàn)在來討論f(x)是否二階相關(guān)免疫。由式(51)，并經(jīng)簡單的重量公式推導(dǎo)，有

由式(53)知，w( '()fx) =2n-1，故w(xixn-r'()fx)≤2n-2，又顯然 0＜2w(xn-rf (x))＜2n-1，故代入式(54)知，式(54)必不等于 2n-1，故由二階相關(guān)免疫的定義知，f(x)一定不是二階相關(guān)免疫函數(shù)。

推論 3 若 f(x)=ef(x)/exn（即 df(x)/dxn=0）且w(f (x))= w(ef(x)/exn)＜2n-2，則 f(x)中存在一階相關(guān)免疫函數(shù)，但f(x)一定不是二階相關(guān)免疫函數(shù)。

由式(2)，對 f(x)，若記 f10(x) = f (x)df(x)/dxn，f20(x)= ef(x)/exn，則

由式(55)對 f (x)分解后，下面來證明重要的定理9。

定理9 將H布爾函數(shù)f(x)分解成式(55)的f10(x)= f(x)df(x)/dxn和 f20(x) = ef(x)/exn，則 f(x)一階相關(guān)免疫，則f10(x)和f20(x) 均必為一階相關(guān)免疫函數(shù)；f(x)二階相關(guān)免疫，則f10(x)和f20(x)均必為二階相關(guān)免疫函數(shù)。

證明 同式(10)、式(11)、式(12)的推導(dǎo)相同，也有結(jié)果：f(x)一階相關(guān)免疫，當(dāng)且僅當(dāng)

顯然，若H布爾函數(shù)f (x)滿足

時，f(x)必滿足式(56)，則f(x)必為一階相關(guān)免疫函數(shù)。

反之，當(dāng)f(x)為一階相關(guān)免疫的H布爾函數(shù)，且w(ef(x)/exk)＜2n-1時，用反證法，假設(shè)式(57)不成立，不妨設(shè)w(xidf(x)/dxk)=2-1w(df(x)/dxk)+2n-r, 則由于f(x)為H布爾函數(shù)，有w(df(x)/dxk)=2n-1，故必有w(xief(x)/exk)=2-1w(ef(x)/exk) -2×2n-r（這一結(jié)果對n=4時是顯然的。對任意的n時，用歸納法是易于證明的。限于篇幅，不再詳證）。將這一結(jié)果代入式(56)左端，有

即式(56)不成立，f (x)不是一階相關(guān)免疫H布爾函數(shù)，與f(x)是一階相關(guān)免疫H布爾函數(shù)矛盾，故必有式(57)成立。

由于 f(x)一階相關(guān)免疫，必有 w(xnf(x)) =2-1w(f(x))，又由式(2)，必有

同式(57)必成立的證明相同，也必有

對式(57)，顯然也有：f (x)一階相關(guān)免疫，則必有

故由式(60)、式(61)知，f (x)一階相關(guān)免疫，必有f10(x)和f20(x)均為一階相關(guān)免疫函數(shù)。

在 2n-2＜w(f(x))＜2n-1+2n-2范圍中，也普遍存在一階相關(guān)免疫的H布爾函數(shù)，而且由定理1、定理2及其級聯(lián)構(gòu)造方法(6)知，一階相關(guān)免疫的H布爾函數(shù)不僅存在，而且是易于構(gòu)造的。于是，現(xiàn)在來討論一階相關(guān)免疫的 H布爾函數(shù)的二階相關(guān)免疫性。有了前面對一階相關(guān)免疫性的必要條件的討論，對二階相關(guān)免疫性的討論，由于與一階相關(guān)免疫相仿，和定理3已有的對w(f(x))=2n-1+2n-2的H布爾函數(shù)的討論相同，已很顯然。限于篇幅，這里只做簡略的討論。和定理 3中式(19)的討論相同，對任意的一階相關(guān)免疫H布爾函數(shù)f (x)，根據(jù)參考文獻[4]的 p19、p133和參考文獻[1]的 p39、p40、p50的定義：

同定理3的推導(dǎo)相同，也有：f (x) 二階相關(guān)免疫，當(dāng)且僅當(dāng)

和式(57)的討論相同，f (x) 二階相關(guān)免疫，當(dāng)且僅當(dāng)

和式(60)、式(61)的討論相同，f (x) 二階相關(guān)免疫，也必有

即f(x) 二階相關(guān)免疫，則f10(x)和f20(x)也必為二階相關(guān)免疫函數(shù)。證畢。

由定理8及推論3和定理9，顯然可直接得到定理10。

定理 10 在 2n-2＜w(f(x))＜2n-1+2n-2中的 H 布爾函數(shù)中，不存在二階相關(guān)免疫的H布爾函數(shù)。

顯然，這時有 w(f20(x))=w(ef(x)/exn)＜2n-1，f20(x)不是二階相關(guān)免疫的，則再由定理9即得出結(jié)論。但由于結(jié)論很重要，故作為定理給出。

4 結(jié)束語

H布爾函數(shù)存在于一個很大的重量范圍內(nèi)，數(shù)量龐大[10]。H布爾函數(shù)的相關(guān)免疫性及其階數(shù)與重量有無聯(lián)系？有何聯(lián)系？m階相關(guān)免疫的H布爾函數(shù)的相關(guān)免疫階數(shù)m與它的維數(shù)n有無關(guān)系？有何關(guān)系？本文對這些問題進行解決，給出了具體的結(jié)果，即只有在 w(f(x))=2n-1+2n-2和 w(f(x))=2n-2的 H布爾函數(shù)中，存在任意 m(m≥1) 階相關(guān)免疫的 H布爾函數(shù)，m和維數(shù)n的關(guān)系為max mi=n-2。而在2n-2＜w(f(x))＜2n-1+2n-2這樣一個大范圍內(nèi)的各種重量的H布爾函數(shù)中，只存在一階相關(guān)免疫的H布爾函數(shù)，但不存在二階相關(guān)免疫的H布爾函數(shù)。這些結(jié)果使 H布爾函數(shù)的相關(guān)免疫性和重量明確聯(lián)系起來，能夠按重量進行分類，這對構(gòu)造具有良好密碼學(xué)性質(zhì)的布爾函數(shù)有實際意義，由此也可知，H布爾函數(shù)在密碼學(xué)研究中有重要作用。

參考文獻：

[1] 李世取,曾本勝, 廉玉忠等. 密碼學(xué)中的邏輯函數(shù)[M].北京: 北京中軟電子出版社,2003.LI S Q, ZENG B S, LIAN Y Z, et al. Logic Function in Cryptography[M]. Beijing: Beijing Soft Electronic Publishing House, 2003.

[2] 楊義先. N元H布爾函數(shù)[J]. 北京郵電大學(xué)學(xué)報,1988,11(3):1-9.YANG Y X. On the H-Boolean functions[J]. Journal of Beijing University of Posts and Telecommunications, 1988,11(3):1-9.

[3] 楊義先,邢育森. N元H布爾函數(shù)(Ⅱ)[J].電子科學(xué)學(xué)刊,1997, 19(2):214-216.YANG Y X,XING Y S. On the H Boolean function(Ⅱ)[J]. Journal of Electronics,1997,19(2): 214-216.

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

[5] 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, Kybernetes[C]. 2007. 245-249.

[6] 何亮, 王卓, 李衛(wèi)衛(wèi). 減小平衡H布爾函數(shù)相關(guān)度的算法和相關(guān)問題研究[J]. 通信學(xué)報, 2010,31(2):93-99.HE L, WANG Z, LI W W. Algorithm of reducing the balanced H-Boolean function correlation_measure and research on correlation issue[J]. Journal on Communications, 2010, 31(2): 93-99.

[7] DING Y J, WANG Z, YE J H. Initial-value problem of the Boolean function's primary function and its application in cryptographic system[J]. Kybernetes, 2010, 39(6): 900-906.

[8] XIAO G Z, MASSEY J L. A spectral characterization of correlation-immune combining functions[A]. IEEE Trans on Inform[C]. 1988.

[9] 溫巧燕, 張劼, 鈕心忻等. 現(xiàn)代密碼學(xué)中的布爾函數(shù)研究綜述[J].電信科學(xué), 2004,20(12):43-46.WEN Q Y, ZHANG J, NIU X X, et al. Review of Boolean functions of modern cryptography[J]. Telecommunication Science, 2004, 20(12): 43-46.

[10] DELFS H, KNEBL H. Introduction to Cryptography[M]. Springer-Verlag, 2002.