H布爾函數的相關免疫性與重量的關系

黃景廉，王卓

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

1 引言

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

2 預備性概念

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

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

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

由定義1和布爾函數的導數的定義，可直接得到下面的引理1和引理2。

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

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

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]關于擴散性的定義顯然可由導數來描述，于是可得出關于f (x)的擴散性的等價定義引理3。

引理3 布爾函數f (x)滿足k (1≤k≤n)次擴散準則，當且僅當對一切 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)滿足一次擴散準則，當且僅當對一切 xi，(i=1, 2,…, n)，有

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

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

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

下面的引理5是一些文獻中已有的結果，這里引入是因為本文的討論要用。本文也將給出用導數性質進行的證明。

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

證明 若f (x)是H布爾函數，則由引理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用反證法證明。

假設 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。但由導數的性質知，有 w(df(x)/dxn)=w(d (1+f(x))/dxn)＜2n-1，故由引理3知，這與f(x)是H布爾函數矛盾，故必有w(f(x))≤2n-1+2n-2。

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

3 對 H布爾函數的重量與相關免疫性及其階數關系的討論

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

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

則f(x)必為一階相關免疫函數。

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

故知f(x)為一階相關免疫函數。

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

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

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

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

則f1(x)和f2(x)的級聯函數

是n+1元一階相關免疫函數。

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

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

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

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

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

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

有了上面的準備，下面來討論各種重量H布爾函數的相關免疫性。

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

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

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

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

由于f(x)是H布爾函數，且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布爾函數，必有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)兩式組成的聯立方程組，則對一切 i,k=1,2,…,n，k≠i，有解

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

由于式(15)必成立及式(16)是方程組唯一解，可知，式(16)中有一式成立，則另一式也必成立。于是取 fe(x)=ef(x)/exn，即 f1(x)是由 f(x)中 ef(x)/exn=1 且df(x)/dxn=0的那些值的函數，即有 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)的第一式。故知相應的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元布爾函數按保證f (x)是H布爾函數，及滿足?fe(x)/?(xn-2xn-1xn)=0的某種次序逐步級聯構成。故知由式(16)第一式，易于構造出一階相關免疫函數，即一階相關免疫的w(f(x))= 2n-1+2n-2的H布爾函數是存在的。

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

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

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

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

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

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

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

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

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

于是由一階相關免疫時得到的 f1(x)、f2(x)、f3(x)、f4(x)，根據式(21)第一式的要求，按 f1(x)、f2(x)、f3(x)、f4(x)、f4(x)、f3(x)、f2(x)、f1(x)的次序構造得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)的次序構造得 fr(x)=1+x2+x1x2+x1x3+x1x4+x2x3+x2x4+x2x5+x3x5+x4x5，其中，ft(x)和 fr(x)均為 n=5元二階相關免疫 H布爾函數。于是，將 ft(x)和 fr(x)按次序 ft(x)、fr(x)、fr(x)、ft(x)、fr(x)、ft(x)、ft(x)、fr(x)、…兩兩逐步級聯，便可得到任意 n元二階相關免疫的w(f(x))=2n-1+2n-2的H布爾函數。

故定理3成立。證畢。

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

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

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

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

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

仍至少是m階相關免疫的n+1元H布爾函數。

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

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

成立。

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

由于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)兩式聯立成方程組并解之，得唯一解式(24)，故f (x)為m (m≥1)階相關免疫函數的充分必要條件是式(24)的兩式均成立。由于式(24)是方程組式(26)、式(27)的唯一解，故推論2成立。

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

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

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

max mi= m=n-2

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

顯然，即相應有

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

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

和

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

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

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

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

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

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

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

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

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

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

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

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

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

證明 設 f(x)是 w(f(x))=2n-1+2n-2的 H 布爾函數，則顯然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個二元布爾函數逐步級聯構成。這在定理3中已經看到過。由引理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)級聯構造的。故由定理4知，可以構造fe(x)是任意m (1≤m≤n-2) 階相關免疫函數。即有

其中，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)知，必有

繼續這一推導，且由于又有

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

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

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

故顯然有

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

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

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

證明 設g(x)為w(g(x))=2n-1+2n-2的m (1≤m≤n-2)階相關免疫的H布爾函數。則由相關免疫的定義知，對ω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) 階相關免疫的H布爾函數。證畢。

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

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

證明 由于定理條件有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中的級聯方式逐步級聯構成。由定理1、定理2及其推理可知，若f10(xn-1xn) 與 f20(xn-1xn) 成對出現，f30(xn-1xn)和f40(xn-1xn) 成對出現，其余均取0級聯時，f(x)必為一階相關免疫函數。由于w(f(x))=w(ef(x)/exn)＜2n-1，因而級聯時要有較多的 0值二元函數參與級聯。于是 f(x)必為如下形式：

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

現在來討論f(x)是否二階相關免疫。由式(51)，并經簡單的重量公式推導，有

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

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

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

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

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

證明 同式(10)、式(11)、式(12)的推導相同，也有結果：f(x)一階相關免疫，當且僅當

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

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

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

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

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

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

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

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

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

同定理3的推導相同，也有：f (x) 二階相關免疫，當且僅當

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

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

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

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

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

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

4 結束語

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

參考文獻：

[1] 李世取,曾本勝, 廉玉忠等. 密碼學中的邏輯函數[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布爾函數[J]. 北京郵電大學學報,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布爾函數(Ⅱ)[J].電子科學學刊,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] 溫巧燕,鈕心忻,楊義先. 現代密碼學中的布爾函數[M].北京:科學出版社,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] 何亮, 王卓, 李衛衛. 減小平衡H布爾函數相關度的算法和相關問題研究[J]. 通信學報, 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] 溫巧燕, 張劼, 鈕心忻等. 現代密碼學中的布爾函數研究綜述[J].電信科學, 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.