一次擴(kuò)散布爾函數(shù)的一些密碼學(xué)性質(zhì)

黃景廉， 張椿玲

（西北民族大學(xué) 電氣工程學(xué)院，甘肅 蘭州 730030）

0 引言

在現(xiàn)代密碼體制的安全性中，布爾函數(shù)的密碼學(xué)性質(zhì)是起關(guān)鍵作用的因素之一[1-3]。將導(dǎo)數(shù)和自定義的 e-導(dǎo)數(shù)結(jié)合在一起引入到布爾函數(shù)密碼學(xué)性質(zhì)研究中[4]，有將布爾函數(shù)取值的不同特點區(qū)分開，以區(qū)別分析的優(yōu)點，能導(dǎo)出一些用傳統(tǒng)研究工具，如頻譜方法等[5-6]不易導(dǎo)出的新的密碼學(xué)性質(zhì)，這里以導(dǎo)數(shù)和自定義的 e-導(dǎo)數(shù)結(jié)合作為新的研究工具，來研究H布爾函數(shù)[7-8]的一些密碼學(xué)性質(zhì)。

1 一些預(yù)備性概念

e-導(dǎo)數(shù)是為研究布爾函數(shù)的密碼學(xué)性質(zhì)自定義的，導(dǎo)數(shù)在密碼學(xué)研究中因單獨使用起不了什么作用而幾乎不用[1-2,5]。本文以e-導(dǎo)數(shù)和導(dǎo)數(shù)作研究工具，因此，需要對e-導(dǎo)數(shù)的概念，及e-導(dǎo)數(shù)和導(dǎo)數(shù)與布爾函數(shù)的擴(kuò)散性的基本關(guān)系作一簡略介紹。

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

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

由e-導(dǎo)數(shù)和導(dǎo)數(shù)的定義，可直接得到引理1和引理2。

引理1 n元布爾函數(shù)f(x)對相同變元的e-導(dǎo)數(shù)和導(dǎo)數(shù)的積為零。

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

很輕易就能用導(dǎo)數(shù)來描述布爾函數(shù) f(x)的擴(kuò)散性。

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

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

由引理2的關(guān)系4和引理3，可以得出引理4和引理5。

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

2 布爾函數(shù)、H布爾函數(shù)的密碼學(xué)性質(zhì)

下面對 0＜w(f (x))＜2n中的布爾函數(shù)討論其密碼學(xué)性質(zhì)。

性質(zhì) 1 對布爾函數(shù) f(x)（x∈GF(2)n，f(x)≠c，c∈GF(2)），若：

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

式(3)只是 f(x)一階相關(guān)免疫的充分條件，而不是必要條件。

性質(zhì) 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ù)[9]。

由性質(zhì)2可得如下推論。

推論1 把n元布爾函數(shù)f(x)看成由2n-3個3元布爾函數(shù) fi(x) (x = xn-2xn-1xn，i=1,2,…,2n-3)級聯(lián)構(gòu)成，且有：

?fi(x)/?(xn-2xn-1xn)=0, i=1,2,…, 2n-3, 即：

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

性質(zhì) 3 在 w(f(x))=2n-1+2n-2的布爾函數(shù)中，當(dāng)n≥3時，存在一階相關(guān)免疫的H布爾函數(shù)；當(dāng)n≥5時，存在二階相關(guān)免疫的H布爾函數(shù)[9]。

下面給出對任意n的一般性討論結(jié)果。

1）對f(x)為w(f(x))=2n-1+2n-2的H布爾函數(shù)，n≥3時，存在而且可構(gòu)造出一階相關(guān)免疫的f(x)。

2）對 f(x)是 w(f(x))=2n-1+2n-2的一階相關(guān)免疫的H布爾函數(shù)，將2個n=4的函數(shù)級聯(lián)得到的n=5的f(x)為二階相關(guān)免疫的H布爾函數(shù)。

由 f1(x)、 f2(x)、 f3(x)、f4(x)任意次序的級聯(lián)，只要保證在第i次級聯(lián)時，df(x)/dxi都保證不會使其中某一個函數(shù)和自身相加，則級聯(lián)構(gòu)成的f(x)就一定是H布爾函數(shù)（由引理3即可證明）。

例1 將f1(x), f2(x), f3(x), f4(x), f4(x), f3(x), f2(x), f1(x)依次逐步級聯(lián)，所得函數(shù)：

是二階相關(guān)免疫的H布爾函數(shù)。

例2 以3元函數(shù)f3(x), f4(x), f1(x), f2(x), f2(x), f1(x),f4(x), f3(x)依次序兩兩逐步級聯(lián)得：

則fr(x)是二階相關(guān)免疫H布爾函數(shù)。

3）存在任意 n維的二階相關(guān)免疫的w(f(x))=2n-1+2n-2的H布爾函數(shù)。

4）當(dāng) n≥6時，存在三階相關(guān)免疫w(f(x))=2n-1+2n-2的H布爾函數(shù)。

給出一個三階免疫的例子例3。

例3 將例1中的二階相關(guān)免疫H布爾函數(shù)f(x)改記為ft(x)，對ft(x)和例2中的fr(x)，有：

但對其余xi+xj+xk，均有：

將ft(x)和fr(x)的變元角標(biāo)均增大1，即將x5記為x6，表示為 x5→x6，其余 x4→x5，x3→x4，x2→x3，x1→x2，然后將改變角標(biāo)后的ft(x)和fr(x)用變元x1作級聯(lián)，所得級聯(lián)函數(shù) f(x)=(1+x1) ft(x)+x1fr(x)是 n=6的w(f(x))=2n-1+2n-2的三階相關(guān)免疫H布爾函數(shù)。

性質(zhì)4 平衡H布爾函數(shù)如果是相關(guān)免疫的，則它只能最高為一階相關(guān)免疫函數(shù)。

證明 根據(jù)引理4，性質(zhì)1和性質(zhì)2的推論1可知，當(dāng)n≥4時，一階相關(guān)免疫的H布爾函數(shù)是存在的且易于構(gòu)造的。如，可由二元 H布爾函數(shù)f44(x)=1+xn-1+xn+xn-1xn逐步級聯(lián)構(gòu)成且總保持性質(zhì)2推論1的要求，即一階相關(guān)免疫的平衡H布爾函數(shù)是存在的，取f(x)為一階相關(guān)免疫的平衡H布爾函數(shù)，故有：

由引理 4及式(8)、式(9)知，f(x)是一階相關(guān)免疫,當(dāng)且僅當(dāng):

由于 f(x)一階相關(guān)免疫,必有 w(xif(x))=2n-2,又w(xi)=2n-1,故必有:

故必有:

由于式(11)、式(12)，若假設(shè) w(xief(x)/exk) ≠2n-3而 是 w(xief(x)/exk)=2n-3+2n-r(r≥3)， 則 必 有w(xidf(x)/dxk)=2n-3-2n-r，于是式(10)要成立，必有：

由式(13)及式(10)，必有：

反之，若式(13)、式(14)成立，則式(10)成立，f(x)是一階相關(guān)免疫。故 f(x)一階相關(guān)免疫當(dāng)且僅當(dāng)式(13)、式(14)成立。

在f(x)已一階相關(guān)免疫的條件下，現(xiàn)在來討論f(x)是否為二階免疫。和性質(zhì)3的討論相似，可得到：f(x)是二階相關(guān)免疫，當(dāng)且僅當(dāng)：

和式(13)、式(14)的討論相似，也有 f(x)二階相關(guān)免疫，當(dāng)且僅當(dāng)：

取 k=n，則 w(ef(x)/exn)=2n-2。分析 xn-1，1+xn-1，xn-2xn-1，xn-2(1+xn-1)，(1+xn-2)xn-1，xn-3xn-1這幾個函數(shù)的特點，以及如下關(guān)系：

則若f(x)二階免疫，由式(16)，必有：

若式(19)不成立，f(x)不是二階免疫已得證，若成立，又必有：

則由于式(17)的關(guān)系，可能((1+xn-2)xn-1ef(x)/exn)=0，這時f(x)不是二階免疫已得證，或者可能仍有：

但若式(21)成立，則由于式(18)的關(guān)系，必有：

故知，f(x)一定不是二階相關(guān)免疫函數(shù)，性質(zhì)得證。

從性質(zhì)4的式(13)，式(16)的證明中，以及性質(zhì)1的結(jié)果，可得出如下推論。

推論1 如果布爾函數(shù)f(x)有w(f(x))=2n-2，且df(x)/dxn=0，w(ef(x)/exn)=2n-2，則 f(x)相關(guān)免疫的階數(shù)最高為一階，f(x)一定不是二階相關(guān)免疫函數(shù)。

從性質(zhì) 3、性質(zhì) 4的式(13)、式(14)、式(16)的證明及結(jié)論，可以得出如下推論。

推論2 對布爾函數(shù) f(x)，若 df(x)/dxi≠0，ef(x)/exi=0,i=1,2,…,n，則 f(x)二階相關(guān)免疫當(dāng)且僅當(dāng) g(x)=df(x)/dxi,i=1,2,…,n二階相關(guān)免疫。

推論3 對布爾函數(shù)f(x)，記g(x)= f(x)df(x)/dxn，h(x)=ef(x)/exn，則f(x)二階相關(guān)免疫當(dāng)且僅當(dāng)g(x)與h(x)均二階相關(guān)免疫，即當(dāng) g(x)與 h(x) 均不二階相關(guān)免疫，也必有f(x)不是二階相關(guān)免疫函數(shù)。

推論3說明，g(x)與h(x)只要其中有一個不二階相關(guān)免疫，則必有f(x)不二階相關(guān)免疫。

性質(zhì) 5 布爾函數(shù) f(x)有 0＜w(f(x))= w(ef(x)/ exn)＜2n-1，即df(x)/dxn=0，則f(x)一定不是二階相關(guān)免疫函數(shù)[9]。

由性質(zhì)4的推論3和性質(zhì)5，可得到如下一系列推論：

推論 1 若 f(x)為 w(f(x))＜2n-2，ef(x)/exn=0，則f(x)一定不是二階相關(guān)免疫函數(shù)。

證明 由性質(zhì)1知，存在一階相關(guān)免疫的f(x)，而由性質(zhì)5知f(x)二階相關(guān)免疫當(dāng)且僅當(dāng)g(x)= df(x)/dxn二階相關(guān)免疫，但g(x)由性質(zhì)5知不是二階相關(guān)免疫函數(shù)，故f(x)不是二階相關(guān)免疫函數(shù)。

推論2 對w(f(x))＞2n-1+2n-2的f(x)，必不是二階相關(guān)免疫函數(shù)。

推論 3 對 2n-2＜w(f(x))＜2n-1+2n-2中的 H 布爾函數(shù)，一定不是二階相關(guān)免疫函數(shù)。

由于 w(df(x)/dxn)=2n-1，0＜w(ef(x)/exn)＜2n-1，則由性質(zhì)4的推論3及性質(zhì)5即得證。

3 結(jié)語

本文對一次擴(kuò)散布爾函數(shù)的一些密碼學(xué)性質(zhì)進(jìn)行了討論，為提高密碼系統(tǒng)抵抗相關(guān)攻擊的能力提供了理論依據(jù)，這一結(jié)果對指導(dǎo)設(shè)計具有較高安全性的密碼系統(tǒng)有實際意義。

[1]李世取,曾本勝, 廉玉忠,等.密碼學(xué)中的邏輯函數(shù)[M].北京: 北京中軟電子出版社,2003.

[2]溫巧燕,鈕心忻,楊義先.現(xiàn)代密碼學(xué)中的布爾函數(shù)[M].北京:科學(xué)出版社,2000.

[3]陳民,鄒傳云.基于非線性譯碼問題的RFID安全協(xié)議[J].通信技術(shù),2010,43(11):118-122.

[4]LI Weiwei, WANG Zhuo, HUANG Jinglian.The E-derivative of Boolean Functions and Its Application in the Fault Detection and Cryptographic System[J].Kybernetes(SCI), 2011,40(5-6): 905-911.

[5]溫巧燕,張劼,鈕心忻,等.現(xiàn)代密碼學(xué)中的布爾函數(shù)研究綜述[J].電信科學(xué),2004,20(12):43-46.

[6]齊云,劉玉孝.相關(guān)免疫函數(shù)和Hamming重量之間的關(guān)系[J].通信技術(shù),2008,41(12):363-365.

[7]楊義先.N元H-布爾函數(shù)[J].北京郵電學(xué)院學(xué)報,1988,11(03):1-9.

[8]楊義先,邢育森.N元H布爾函數(shù)(Ⅱ)[J].電子科學(xué)學(xué)刊,1997,19(02):214-216.

[9]HUANG Jinglian, WANG Zhou.The Categories of the Correlation-measure of the Linear Proliferation Boolean Functions[C].[s.l.]:WNIS, 2010:93-96.