一類代數免疫度最優的奇數變元旋轉對稱布爾函數的構造*

沈黎鵬,陳克非,2,3

1.杭州師范大學 理學院,杭州311121

2.杭州市密碼與網絡安全重點實驗室,杭州311121

3.衛士通摩石實驗室,北京100070

1 引言

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

如今,學者們還致力于研究性質優良的旋轉對稱布爾函數(RSBFs).這是一類具有在循環群作用下函數值保持不變的布爾函數,其旋轉對稱性使得布爾函數具有結構簡單、運算速度快、實現代價小等優點.旋轉對稱布爾函數在一定條件下可以具備優良的密碼學性質,比如文獻[9]構造的布爾函數具有1 階彈性,文獻[10]構造的布爾函數具有bent 性.因此,旋轉對稱布爾函數在密碼學領域發揮著極其重要的作用.

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

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

2 準備知識

2.1 布爾函數的基礎知識

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

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

這種表示方法被稱為布爾函數的代數標準型.式(1)中f的代數次數定義為:

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

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

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

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

等價于:

2.2 旋轉對稱布爾函數

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

定義4如果

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

文獻[3]指出了擇多函數F(x)的代數免疫度達到最優,其代數次數為deg(F)=2?log2n?.

3 布爾函數的構造

3.1 整數拆分

首先,我們引入整數拆分的相關知識,這是接下來函數構造的基礎.

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

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

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

(2)am≥2;

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

記k的拆分數為pm1,m2(k),則

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

推論1在引理1相同條件下,如果am?1≥2,則拆分數如果am?1=1,則拆分數

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

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

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

記k的拆分數為qm1,m2(k),則

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

引理1和引理2給出了整數k在兩種特定情況下的拆分數計算公式,更多關于整數拆分的知識見文獻[17].

3.2 集合的構造與計數

下面我們根據不同的m1和m2,對Sh,m1,m2進行分類.

當m1≥1,m2≥2,dm?1≥2時,記由1和2

當m1≥1,m2≥2,dm?1=1時,記則

當m1=0,m2≥2,記由引理1和2

當m2=1時,記由引理1和2

為便于計數,令

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

其中t∈Ik,h,集合

命題1是上述構造的向量集合,以下結論成立.

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

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

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

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

再令

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

算法1 計算|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 計算|T′′h,ti|=|T′h,ti|?∑tj|ti,j

例2給定k=16,當h=15時,我們有此時由于k+h+ 1=32 為偶數,所以

3.2.3T和U的構造與計數

將T和U排列如下:

簡記為

3.3 函數的構造

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

例3給定k=5,我們有

則有

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

是一個平衡的11 元旋轉對稱布爾函數.

4 布爾函數的性質分析

4.1 代數免疫度

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

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

(5)對任意的0≤l≤n?1,當s>t時,

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

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

當1≤l≤dm+1,有

當dm+2≤l≤n??h,如果存在l,使得則有

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

當n??h+1≤l≤n?1,有

(4)設

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

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

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

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

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

(i)n??h1≥?h2

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

當?h1+1≤l≤n??h2,有

假設存在l使得如果則有

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

(ii)n??h1

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

當n??h2+1≤l≤n?1,有

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

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

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

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

則布爾函數

代數免疫度最優,其中F(x)是擇多函數.

記

定理1式(7)中的f(x)代數免疫度最優.

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

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

4.2 非線性度

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

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

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

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

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

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

證明:對k進行歸納易證.

命題3令則

證明:當15≤k<220,直接計算可知不等式成立.

當k≥220,令

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

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

證明:令計算可得F(17)>0.F(k)是一個增函數(k≥17),因為

其中最后一個不等號用到了命題3的結論.

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

定理2設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

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

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

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

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

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

表1比較了文獻[12–15]與式(7)的布爾函數在k≥12時的非線性度.從表中可以看出本文構造的函數非線性度遠大于其他構造,尤其是當k逐漸增大時,其優勢更為明顯.

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

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

n 文獻[12]文獻[13]文獻[14]文獻[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

另一方面,從非線性度的表達式看,文獻[13,15]與本文構造的布爾函數其非線性度的大小都與集合Th中的元素個數有關,而本文在集合的構造上保證了Th和Uh中有盡可能多的元素,從而使得布爾函數在非線性度上具有更大的優勢.

4.3 代數次數

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

其中m是正整數,m≥3.

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

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

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

5 結語

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

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