基于偽隨機(jī)子集生成的Boolean函數(shù)

劉華寧,陳曉林

(西北大學(xué)數(shù)學(xué)學(xué)院,陜西西安 710127)

1 引言

Boolean函數(shù)在流密碼,分組密碼以及散列函數(shù)的研究中起著重要作用.為了研究Boolean函數(shù),人們提出了許多有關(guān)Boolean函數(shù)的密碼學(xué)指標(biāo).

設(shè) F2是一個二元域,Fn2是 F2上的一個n維線性空間,所謂n元Boolean函數(shù)B(x1,···,xn)是指從 Fn2到 F2的一個映射. 設(shè) x=(x1,···,xn),a=(a1,···,an)∈Fn2,則〈a,x〉=a1x1+···+anxn表示通常的內(nèi)積.Boolean 函數(shù)B(x1,···,xn)的最大 Fourier系數(shù) ^B(a)定義為

Boolean函數(shù)B(x1,···,xn)的非線性定義如下

每一個Boolean函數(shù)都可以唯一地表示成多項(xiàng)式的形式,稱為Boolean函數(shù)的代數(shù)正規(guī)型

Boolean函數(shù)的稀疏性spr(B)是代數(shù)正規(guī)型中非零系數(shù)單項(xiàng)式的個數(shù).此外Boolean函數(shù)的平均靈敏度σav(B)定義如下其中a(i)是a改變第i個坐標(biāo)后所得的向量.

近幾年來,一些密碼學(xué)研究者從數(shù)論的角度出發(fā)構(gòu)造了許多具有“好”的密碼學(xué)性質(zhì)的Boolean函數(shù).例如,Coppersmith與Shparlinski[1]利用模p的二次剩余構(gòu)造了如下的Boolean函數(shù).

命題1.1 設(shè)p為奇素數(shù),s=blog2pc,其中bxc表示不超過x的最大整數(shù).定義Boolean函數(shù)為

其中uj∈{0,1}且1≤j≤s.則有

Lange與Winterhof[2]將上述命題進(jìn)行了推廣.

命題1.2 設(shè)p為奇素數(shù),Fq是階為q=pr(r≥1)的有限域,β0,···,βr?1是Fq在Fp上的一組基,s=blog2pc.定義Boolean函數(shù)如下

其中ki?1=ui1+ui2·2+···+uis·2s?1,uij∈{0,1}且 1≤j≤s,1≤i≤r.則有

隨后文獻(xiàn)[3]進(jìn)一步研究了命題1.2中Boolean函數(shù)的性質(zhì),得到了以下結(jié)果.

命題1.3 設(shè)p,r,s,B如以上命題所定義.則有

最近幾十年來,隨著數(shù)論、組合以及相關(guān)學(xué)科的發(fā)展,偽隨機(jī)子集得到了深入的研究和廣泛的應(yīng)用.許多論文都是關(guān)于這一領(lǐng)域的,這些論文中提出了大量的思想、方法和工具.1992年,Chung與Graham[4]發(fā)現(xiàn)整數(shù)環(huán)的子集具有一類令人驚奇的互相等價的性質(zhì),并且如果一個子集滿足這類性質(zhì)中的任何一條,則滿足其余性質(zhì).Gowers[5]對整數(shù)環(huán)的偽隨機(jī)子集進(jìn)行了具體的數(shù)量分析,利用所定義的Gowers范數(shù),在整數(shù)環(huán)的子集引入了新的偽隨機(jī)測度,進(jìn)而給出了Szemer′edi定理的新證明.

偽隨機(jī)子集不僅有著深刻的理論意義,還在網(wǎng)絡(luò)安全、密碼學(xué)等領(lǐng)域中具有廣泛的應(yīng)用.研究者發(fā)現(xiàn)偽隨機(jī)子集可以提高密鑰預(yù)分配過程的效率和安全性,進(jìn)而改善密鑰管理、廣播認(rèn)證協(xié)議、無線傳感網(wǎng)絡(luò)的過程(參閱文獻(xiàn)[6]),另外還可用于構(gòu)造匿名路徑以避免路徑信息被竊聽(參閱文獻(xiàn)[7]與[8]).

本文將利用偽隨機(jī)子集構(gòu)造大族的Boolean函數(shù),并在第2節(jié)到第4節(jié)中證明下面的結(jié)論.

定理1.1 設(shè)p為奇素數(shù),q=pr,Fq為有限域,A?Fq是Fq的子集,滿足

則有

注 設(shè)p為奇素數(shù),q=pr,Fq為有限域.定義不難證明

因此本文是對文獻(xiàn)[2]與[3]的推廣.

2 最大Fourier系數(shù)與非線性

首先介紹下面的引理.

引理2.1設(shè)p為奇素數(shù),q=pn,χ為有限域 Fq上的d(d＞1)階乘法特征,v1,···,vn是Fq在Fp上的一組基.設(shè)f(x)∈Fq[x]不能表為Fq上任何多項(xiàng)式的d次冪的常數(shù)倍,且在它的分裂域中有m個不同的根.定義

其中t1,···,tn是非負(fù)整數(shù)且t1＜p,···,tn＜p.則有

證 參閱文獻(xiàn)[9]中的定理2.

記ki?1=ui1+ui2·2+···+uis·2s?1,其中uij∈{0,1},1≤j≤s,1≤i≤r.定義

其中z=k0β0+···+kr?1βr?1,ki?1=ui1+ui2·2+···+uis·2s?1,1≤i≤r,且

根據(jù)文獻(xiàn)[3]中的方法,設(shè)x是一個整數(shù)且1＜x＜s,則有

顯然任意z∈H2s都能唯一地表為z=y+w,其中y∈H2x,且

定義

易知〈z,a〉=〈y,b〉+〈w,c〉.由 Cauchy-Schwarz 不等式有

再由引理2.1可得

設(shè)實(shí)數(shù)x0滿足

并取x=bx0c+1,有

結(jié)合(2.1)與(2.2)式可得

注意到

因此

這就證明了(1.4)式.又由于s=blog2pc＞log2p?1,則有

從而可得(1.5)式.

3 稀疏性

設(shè)整數(shù)a滿足2a＞(spr(B)+1)r1≥2a?1. 令M={0,···,2a?1}r{(0,···,0)},對每一個定義函數(shù)

其中mi=mi1+···+mia2a?1,mij∈{0,1},1≤j≤a,1≤i≤r. 對于定義在u11,···,u1(s?a),···,ur1,···,ur(s?a)的所有中,不同單項(xiàng)式的個數(shù)不超過spr(B).注意到|M|=2ar?1＞spr(B),則可以找到非平凡的線性組合,使得

定義

容易證明

其中y∈H2s?a,w∈2s?aH2a{0},且與w∈2s?aH2a{0}是一一對應(yīng)的.

定義

以及L=|N|.則有

為方便起見,記N={w1,w2,···,wL}. 可得

設(shè)χ′是 Fq的乘法特征群的生成元,其階為q?1,則可把χ1,···,χL分別寫成

其中 1≤a1,···,aL≤q?2.定義

則χ?的階為q?1 的大于 1 的因數(shù),1≤δ1,···,δL≤q?2,且 (δ1,···,δL)=1,從而

注意到w1,···,wL互不相同,且 (δ1,···,δL)=1. 則 (y+w1)δ1···(y+wL)δL不可能表

為某個多項(xiàng)式的d＞1次冪.由引理2.1可得

因此

注意到s=blog2pc＞log2p?1,有從而 spr(B)≥(2a?1)r?1＞這就證明了(1.6)式.

4 平均靈敏度

令

并記B′(k)=B(u11,···,u1s,···,ur1,···,urs),其中

且

定義

根據(jù)文獻(xiàn)[3]中的方法,以及引理2.1可得

這就證明了(1.7)式.

5 進(jìn)一步的討論

利用相同的方法,還可構(gòu)造范圍更大的Boolean函數(shù)族,并證明下面的結(jié)論.

定理5.1 設(shè)p為奇素數(shù),q=pr,Fq為有限域,A?Fq是Fq的子集,滿足

設(shè)β0,···,βr?1是 Fq在 Fp上的一組基.定義s=blog2pc,并設(shè)uij∈{0,1},1≤j≤s,1≤i≤r.記ki?1=ui1+ui2·2+···+uis·2s?1,1≤i≤r.定義

則有

注 滿足定理5.1中的條件的子集有很多個.例如,設(shè)g是F?q的生成元,則下列子集

都滿足定理5.1的要求.

[1]Coppersmith D,Shparlinski I E.On polynominal approximation of the discrete logarithm and the Diきe-Hellman mapping[J].J.Cryp.,2000,13(3):339–360.

[2]Lange T,Winterhof A.Incomplete character sums over finite fields and their application to the interpolation of the discrete logarithm by Boolean functions[J].Acta Arith.,2002,101(3):223–229.

[3]Lange T,Winterhof A.Interpolation of the discrete logarithm in Fqby Boolean functions and by polynomials in several variables modulo a divisor ofq?1[J].Disc.Appl.Math.,2003,128(1):193–206.

[4]Chung F R K,Graham R L.Quasi-random subsets of Zn[J].J.Combin.The.Ser.A,1992,61(1):64–86.

[5]Gowers W T.A new proof of Szemer′edi’s theorem[J].Geom.Funct.Anal.,2001,11(3):465–588.

[6]蘇忠,林闖,任豐原.無線傳感器網(wǎng)絡(luò)中基于散列鏈的隨機(jī)密鑰預(yù)分發(fā)方案[J].計算機(jī)學(xué)報,2009,32(1):30–41.

[7]夏永波.Bent序列的構(gòu)造及其相關(guān)值分布[J].數(shù)學(xué)雜志,2010,30(4):663–670.

[8]Xu L,Chen S,Huang X,Mu Y.Pseudonym and bloom filter based secure and anonymouse DSR protocol in wireless ad hoc network[J].Int.J.Comput.Netw.Commun.Secur.,2010,5(1):35–44.

[9]Winterhof A.Some estimates for character sums and applications[J].Des.Codes Cryptogr.,2001,22(2):123–131.