一類代數(shù)免疫度最優(yōu)的奇數(shù)變元旋轉(zhuǎn)對稱布爾函數(shù)的構(gòu)造*

沈黎鵬,陳克非,2,3

1.杭州師范大學(xué) 理學(xué)院,杭州311121

2.杭州市密碼與網(wǎng)絡(luò)安全重點(diǎn)實(shí)驗(yàn)室,杭州311121

3.衛(wèi)士通摩石實(shí)驗(yàn)室,北京100070

1 引言

密碼系統(tǒng)中使用的布爾函數(shù)應(yīng)該滿足一些安全性指標(biāo):代數(shù)次數(shù),平衡性,相關(guān)免疫度,非線性度,差分均勻度等.隨著代數(shù)攻擊[1,2]的出現(xiàn),代數(shù)免疫度成為選擇布爾函數(shù)的一個(gè)重要的新指標(biāo)[3,4].從文獻(xiàn)[4]的研究成果我們可以知道n元布爾函數(shù)的代數(shù)免疫度上界是如果達(dá)到了這個(gè)上界,那么我們稱布爾函數(shù)是代數(shù)免疫度最優(yōu)的.近年來,許多最優(yōu)代數(shù)免疫度函數(shù)類被密碼學(xué)者提出[3,5–8].

如今,學(xué)者們還致力于研究性質(zhì)優(yōu)良的旋轉(zhuǎn)對稱布爾函數(shù)(RSBFs).這是一類具有在循環(huán)群作用下函數(shù)值保持不變的布爾函數(shù),其旋轉(zhuǎn)對稱性使得布爾函數(shù)具有結(jié)構(gòu)簡單、運(yùn)算速度快、實(shí)現(xiàn)代價(jià)小等優(yōu)點(diǎn).旋轉(zhuǎn)對稱布爾函數(shù)在一定條件下可以具備優(yōu)良的密碼學(xué)性質(zhì),比如文獻(xiàn)[9]構(gòu)造的布爾函數(shù)具有1 階彈性,文獻(xiàn)[10]構(gòu)造的布爾函數(shù)具有bent 性.因此,旋轉(zhuǎn)對稱布爾函數(shù)在密碼學(xué)領(lǐng)域發(fā)揮著極其重要的作用.

目前,關(guān)于奇變元的最優(yōu)代數(shù)免疫度RSBFs 已經(jīng)有了較多的研究成果.2007年,Sarkar和Maitra[11]修改擇多函數(shù),給出一類具有最優(yōu)代數(shù)免疫的RSBFs,但是其非線性度不高,為年,Su 等人[12]基于正數(shù)拆分理論分別構(gòu)造了奇數(shù)和偶數(shù)變元的代數(shù)免疫度最優(yōu)RSBFs 構(gòu)造,具有較高的非線性度,當(dāng)函數(shù)變量個(gè)數(shù)n為奇數(shù)時(shí)的非線性度為同年,文獻(xiàn)[13]構(gòu)造了一類最優(yōu)代數(shù)免疫的奇數(shù)元BFSRs,其非線性度為年,Fu 等人[14]中改進(jìn)了文獻(xiàn)[12]的方案,構(gòu)造的布爾函數(shù)非線性度為之后,Sun 等人[15]給出了兩類最優(yōu)代數(shù)免疫的奇數(shù)元RSBFs,也都是基于整數(shù)拆分理論構(gòu)造的,而且第一類函數(shù)的非線性度超過了以往的構(gòu)造.

對于代數(shù)免疫度最優(yōu)的奇數(shù)元RSBFs 本文給出了一種新的構(gòu)造,在構(gòu)造方法上受到了文獻(xiàn)[15]的啟發(fā).通過對集合元素的計(jì)數(shù)可以發(fā)現(xiàn),構(gòu)造出的函數(shù)在非線性度和代數(shù)次數(shù)上具有較大的優(yōu)勢.本文所得結(jié)果也為今后使用密碼函數(shù)提供了一種新的選擇.

2 準(zhǔn)備知識

2.1 布爾函數(shù)的基礎(chǔ)知識

一個(gè)n元布爾函數(shù)是到F2的一個(gè)映射.任一布爾函數(shù)f均可由它的真值表表示:f=[f(0,··· ,0),f(0,··· ,1),··· ,f(1,··· ,1)].f是平衡的,如果wt(f)=2n?1.

記Bn為所有n元布爾函數(shù)組成的集合.對任意f(x0,x1,··· ,xn?1)∈Bn,都可唯一表示成上次數(shù)不超過n的一個(gè)多項(xiàng)式:

這種表示方法被稱為布爾函數(shù)的代數(shù)標(biāo)準(zhǔn)型.式(1)中f的代數(shù)次數(shù)定義為:

代數(shù)次數(shù)小于或等于1 的函數(shù)被稱為仿射函數(shù).所有仿射函數(shù)的集合記為An,即An={f∈Bn|deg(f)≤1}.

定義1對于f∈Bn,如果存在g∈Bn,使得fg=0,則稱g為f的零化子.f的代數(shù)免疫度是定義為:

定義2對于函數(shù)f∈Bn,定義f的Walsh 變換:

對于f,g∈Bn,定義d(f,g)=wt(f+g)為f與g的Hamming 距離.布爾函數(shù)f的非線性度是f與所有仿射函數(shù)的最小Hamming 距離,記作nl(f),即:

等價(jià)于:

2.2 旋轉(zhuǎn)對稱布爾函數(shù)

定義3布爾函數(shù)f∈Bn稱為旋轉(zhuǎn)對稱布爾函數(shù),如果對任意的以及1≤l≤n?1 均成立.

定義4如果

則稱F(x)為擇多函數(shù)[16].

文獻(xiàn)[3]指出了擇多函數(shù)F(x)的代數(shù)免疫度達(dá)到最優(yōu),其代數(shù)次數(shù)為deg(F)=2?log2n?.

3 布爾函數(shù)的構(gòu)造

3.1 整數(shù)拆分

首先,我們引入整數(shù)拆分的相關(guān)知識,這是接下來函數(shù)構(gòu)造的基礎(chǔ).

一個(gè)正整數(shù)k的拆分可以表示成一個(gè)序列(k1,k2,··· ,km),且滿足k1+k2+···+km=k.同時(shí)也要注意到,僅是順序不同的序列表示整數(shù)k不同的拆分.我們把每一個(gè)ki稱為一個(gè)部分.易知,整數(shù)k拆分成m個(gè)部分的計(jì)數(shù)為

引理1給定正整數(shù)k,m1和m2,m=m1+m2,k的拆分滿足以下3 個(gè)條件:

(1)a1+a2+···+am=k;

(2)am≥2;

(3)(a1,a2,··· ,am)中m1個(gè)部分等于1,其余m2個(gè)部分大于等于2.

記k的拆分?jǐn)?shù)為pm1,m2(k),則

證明:等同于分球入盒問題,即有k個(gè)相同的球,m個(gè)不相同的盒子,其中m1個(gè)盒子只放一個(gè)球,另外m2個(gè)盒子至少放兩個(gè)球,已確定某一個(gè)盒子至少放兩個(gè)球,求分法數(shù).首先盒子的分法有種,盒子確定的情況下球的分法有種,因此共有種分法.

推論1在引理1相同條件下,如果am?1≥2,則拆分?jǐn)?shù)如果am?1=1,則拆分?jǐn)?shù)

引理2給定正整數(shù)k,m1和m2,m=m1+m2,k的拆分滿足以下兩個(gè)條件:

(1)a1+a2+···+am=k;

(2)已知(a1,a2,··· ,am)中ai1,ai2,···aim2≥2.

記k的拆分?jǐn)?shù)為qm1,m2(k),則

證明:同樣利用分球入盒模型易證.

引理1和引理2給出了整數(shù)k在兩種特定情況下的拆分?jǐn)?shù)計(jì)算公式,更多關(guān)于整數(shù)拆分的知識見文獻(xiàn)[17].

3.2 集合的構(gòu)造與計(jì)數(shù)

下面我們根據(jù)不同的m1和m2,對Sh,m1,m2進(jìn)行分類.

當(dāng)m1≥1,m2≥2,dm?1≥2時(shí),記由1和2

當(dāng)m1≥1,m2≥2,dm?1=1時(shí),記則

當(dāng)m1=0,m2≥2,記由引理1和2

當(dāng)m2=1時(shí),記由引理1和2

為便于計(jì)數(shù),令

其中k1≥2,dm≥2,對任意1≤i≤m?1,若di≥2,則ki+1≥2.

其中t∈Ik,h,集合

命題1是上述構(gòu)造的向量集合,以下結(jié)論成立.

(2)對任意的t1,t2∈Ik,h,如果則

證明:(1)對任意的設(shè)任意的可表示成n/t1或n/t2個(gè)分塊的級聯(lián),所以必可表示成[n/t1,n/t2]個(gè)相同分塊的級聯(lián),即n/(t1,t2)個(gè)相同分塊,由β1存在性知反之,若存在r|(t1,t2)且r∈Ik,h,設(shè)任意的β2可表示成n/r個(gè)相同分塊的級聯(lián),又有(n/t1)|(n/r),(n/t1)|(n/r),所以β2必可表示成n/t1或n/t2個(gè)相同分塊的級聯(lián),于是

(2)可由(1)的證明得到.

例1給定k=103,當(dāng)h=99時(shí),取t1=69,t2=23 ∈I103,99.對任意的向量必可表示為(a,a,a)的形式,其中a[x0,··· ,x68]是γ的一個(gè)分塊.根據(jù)集合的定義可知

再令

根據(jù)式(5)和式(6),我們可按以下算法計(jì)算|T2h|.

算法1 計(jì)算|T2h|Input:k,h,Ik,h={t1,t2,··· ,tm}Output:|T2 h|1 輸入k,h,Ik,h={t1,t2,··· ,tm},其中t1< t2< ··· < tm,令i=1.2 計(jì)算|T′′h,ti|=|T′h,ti|?∑tj|ti,j

例2給定k=16,當(dāng)h=15時(shí),我們有此時(shí)由于k+h+ 1=32 為偶數(shù),所以

3.2.3T和U的構(gòu)造與計(jì)數(shù)

將T和U排列如下:

簡記為

3.3 函數(shù)的構(gòu)造

其中F(x)是n元擇多函數(shù).于是f(x)是一個(gè)平衡的n元旋轉(zhuǎn)對稱布爾函數(shù).

例3給定k=5,我們有

則有

令T=T3∪T4∪T5,U=U3∪U4∪U5.對任意α∈T∪U,有記F(x)是11 元擇多函數(shù),則

是一個(gè)平衡的11 元旋轉(zhuǎn)對稱布爾函數(shù).

4 布爾函數(shù)的性質(zhì)分析

4.1 代數(shù)免疫度

引理3對任意的h∈H,αhs∈Th以及uhs,uht∈Uh,1≤s,t≤|Th|,1≤s,t≤|Th| 以下結(jié)論成立.

(4)對任意的0≤l≤n?1,h1,h2∈H且

(5)對任意的0≤l≤n?1,當(dāng)s>t時(shí),

證明:(1)由Uh的定義顯然成立.

滿足k1+···+km=h,d1+···+dm=h?1.

當(dāng)1≤l≤dm+1,有

當(dāng)dm+2≤l≤n??h,如果存在l,使得則有

即存在di≥2,ki+1=1(1≤i≤m?2),與Th和Uh的定義矛盾.

當(dāng)n??h+1≤l≤n?1,有

(4)設(shè)

滿足k1+···+km=h1,d1+···+dm=h1?1.

我們分①和②兩種情況討論:

①?h1≥2(k+1?h2)

當(dāng)0≤l≤?h1?2(k+1?h2)+1,有

當(dāng)?h1?2(k+1?h2)+2≤l≤n??h2,分以下兩種情況:

(i)n??h1≥?h2

當(dāng)?h1?2(k+1?h2)+2≤l≤?h1,假設(shè)存在l使得必有km=1,且有

當(dāng)?h1+1≤l≤n??h2,有

假設(shè)存在l使得如果則有

否則,存在di≥2,ki+1=1(1≤i≤m?2),與Th和Uh的定義矛盾.

(ii)n??h1

?h1?2(k+1?h2)+2≤l≤n??h2時(shí)的證明與1)中?h1?2(k+1?h2)+2≤l≤?h1的情況相同.

當(dāng)n??h2+1≤l≤n?1,有

②?h1<2(k+1?h2)

當(dāng)l=0,式(8)仍成立.當(dāng)1≤l≤n?1,證明與(i)中?h1?2(k+1?h2)+2≤l≤n?1 的情況相同.

(5)當(dāng)l=0,若則αhs=uht,s=t,矛盾.當(dāng)1≤l≤n?1,可通過結(jié)論(4)中①的證明方法得到,將α(h1)s替換成αhs,將替換成uht,?h1替換成?h,?h2替換成

引理4[18]設(shè)如果集合和中的向量滿足:

則布爾函數(shù)

代數(shù)免疫度最優(yōu),其中F(x)是擇多函數(shù).

記

定理1式(7)中的f(x)代數(shù)免疫度最優(yōu).

證明:根據(jù)引理4,考慮到中向量的順序,要證f(x)代數(shù)免疫度最優(yōu),即證中的向量滿足:

由引理3,上述條件均成立.于是f(x)代數(shù)免疫度最優(yōu).

4.2 非線性度

首先我們給出一些必要的引理和命題.

引理5[3]F(x)是n元擇多函數(shù),其中n=2k+1.對任意的以下結(jié)論成立.

(1)如果wt(α)=1,則

(2)如果wt(α)=n,則

(3)如果2≤wt(α)≤n?1,則

命題2設(shè)n=2k+1(k≥220),則以下不等式成立:

證明:對k進(jìn)行歸納易證.

命題3令則

證明:當(dāng)15≤k<220,直接計(jì)算可知不等式成立.

當(dāng)k≥220,令

易見|R|=g(k+1).再令由(k+1,2k+1)=1 知,

引理6設(shè)n=2k+1(k≥17),則有

證明:令計(jì)算可得F(17)>0.F(k)是一個(gè)增函數(shù)(k≥17),因?yàn)?/p>

其中最后一個(gè)不等號用到了命題3的結(jié)論.

所以k≥17時(shí),F(k)>0.于是

定理2設(shè)n=2k+1(k≥3),式(7)中f(x)的非線性度滿足:

證明:對任意的ω∈,由式(4),式(7)和式(9),我們有

我們分以下四種情況討論:

(1)wt(ω)=0,即ω=(0,0,··· ,0),由于f是平衡的,故Wf(w)=0.

(2)wt(ω)=1,我們有由引理5

此時(shí),記|Wf(w)1|=|Wf(w)|.

(3)wt(ω)=n,即ω=(1,1,··· ,1),我們有n(?1)k+1.由引理5

(4)2≤wt(ω)≤n?1,由引理5

當(dāng)3≤k≤12,直接計(jì)算可得當(dāng)13≤k≤16,|Wf(w)| <|Wf(w)1|.當(dāng)k≥17,由引理6

綜上,當(dāng)3≤k≤12,我們可以得到非線性度的一個(gè)下界,即當(dāng)k≥13,在wt(ω)=1時(shí),|Wf(w)| 最大,因此

表1比較了文獻(xiàn)[12–15]與式(7)的布爾函數(shù)在k≥12時(shí)的非線性度.從表中可以看出本文構(gòu)造的函數(shù)非線性度遠(yuǎn)大于其他構(gòu)造,尤其是當(dāng)k逐漸增大時(shí),其優(yōu)勢更為明顯.

表1 非線性度超過部分的比較Table 1 Comparison of enhanced values of nonlinearity upon

表1 非線性度超過部分的比較Table 1 Comparison of enhanced values of nonlinearity upon

n 文獻(xiàn)[12]文獻(xiàn)[13]文獻(xiàn)[14]文獻(xiàn)[15]本文f(7)25 4094 8034 5108 24 372 ≥87 520 27 8190 16 200 10 227 61 660 480 642 29 16 382 32 556 20 466 151 836 1564 614 31 32 766 65 294 40 945 376 958 5106 518 33 65 534 130 798 81 904 919 506 16 705 158 35 131 070 261 836 163 823 2249 930 54 760 830 37 262 142 523 944 327 662 5435 062 179 839 434

另一方面,從非線性度的表達(dá)式看,文獻(xiàn)[13,15]與本文構(gòu)造的布爾函數(shù)其非線性度的大小都與集合Th中的元素個(gè)數(shù)有關(guān),而本文在集合的構(gòu)造上保證了Th和Uh中有盡可能多的元素,從而使得布爾函數(shù)在非線性度上具有更大的優(yōu)勢.

4.3 代數(shù)次數(shù)

定理3式(7)中函數(shù)f(x)的代數(shù)次數(shù)滿足的:

其中m是正整數(shù),m≥3.

證明:函數(shù)f(x)等價(jià)于f(x)=F(x)+G(x),G(x)滿足

因?yàn)閣t(G)是偶數(shù),所以由式(2)和式(3)知deg(f)≤n?1.G(x)的代數(shù)標(biāo)準(zhǔn)型中n?1 次項(xiàng)x0x1···xn?1/xi(0≤i≤n?1)的系數(shù)是集合和中滿足第i個(gè)分量為0 的向量個(gè)數(shù)N(mod 2).由向量x={x0,x1,··· ,xn?1} 生成的軌道定義知,x的每一個(gè)分量都會出現(xiàn)在第i個(gè)位置.又知對任意的k≥3,有|T3|=1,|T4|=3.于是

由于deg(F)=2?log2n?,當(dāng)n=2m+1時(shí),deg(F)=n?1.由于F和G的代數(shù)標(biāo)準(zhǔn)型都包含所有的n?1 次項(xiàng)x0x1···xn?1/xi(0≤i≤n?1),因此deg(f)=deg(F+G)≤n?2.當(dāng)2m+2≤n≤2m+1時(shí),deg(F)≤n?2,因此deg(f)=deg(G)=n?1.

5 結(jié)語

本文構(gòu)造了奇數(shù)元代數(shù)免疫度最優(yōu)的旋轉(zhuǎn)對稱布爾函數(shù),這類布爾函數(shù)在構(gòu)造方法上通過修改擇多函數(shù)支撐集,以增加函數(shù)的復(fù)雜性和改變密碼學(xué)性質(zhì).從集合的構(gòu)造看,我們構(gòu)造的集合T和U比同類構(gòu)造相應(yīng)的集合擁有更多的元素,這就使得布爾函數(shù)具有比較高的非線性度.通過取特殊子集,我們保證了函數(shù)在n=2m+1時(shí)的最優(yōu)代數(shù)次數(shù).

但是,仍有一些問題值得我們深入研究,比如此類函數(shù)在7≤n≤23時(shí)是否仍有高非線性度,此類函數(shù)是否能有效抵抗快速代數(shù)攻擊,如何構(gòu)造相關(guān)免疫的旋轉(zhuǎn)對稱布爾函數(shù)等.這些都是我們今后的研究方向.