劉華寧,陳曉林

(西北大學數學學院,陜西西安 710127)

1 引言

Boolean函數在流密碼,分組密碼以及散列函數的研究中起著重要作用.為了研究Boolean函數,人們提出了許多有關Boolean函數的密碼學指標.

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

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

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

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

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

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

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

Lange與Winterhof[2]將上述命題進行了推廣.

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

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

隨后文獻[3]進一步研究了命題1.2中Boolean函數的性質,得到了以下結果.

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

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

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

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

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

則有

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

因此本文是對文獻[2]與[3]的推廣.

2 最大Fourier系數與非線性

首先介紹下面的引理.

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

其中t1,···,tn是非負整數且t1＜p,···,tn＜p.則有

證 參閱文獻[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,且

根據文獻[3]中的方法,設x是一個整數且1＜x＜s,則有

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

定義

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

再由引理2.1可得

設實數x0滿足

并取x=bx0c+1,有

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

注意到

因此

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

從而可得(1.5)式.

3 稀疏性

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

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

定義

容易證明

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

定義

以及L=|N|.則有

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

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

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

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

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

為某個多項式的d＞1次冪.由引理2.1可得

因此

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

4 平均靈敏度

令

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

且

定義

根據文獻[3]中的方法,以及引理2.1可得

這就證明了(1.7)式.

5 進一步的討論

利用相同的方法,還可構造范圍更大的Boolean函數族,并證明下面的結論.

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

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

則有

注 滿足定理5.1中的條件的子集有很多個.例如,設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]蘇忠,林闖,任豐原.無線傳感器網絡中基于散列鏈的隨機密鑰預分發(fā)方案[J].計算機學報,2009,32(1):30–41.

[7]夏永波.Bent序列的構造及其相關值分布[J].數學雜志,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.