一類平衡的最優(yōu)代數(shù)免疫度布爾函數(shù)的構(gòu)造

王筱琛 陳克非 沈忠華 程慧潔

(杭州師范大學(xué)理學(xué)院數(shù)學(xué)系 浙江 杭州 310012)

0 引 言

近年來(lái),代數(shù)攻擊[1]方法被提出后,受到了密碼學(xué)界廣泛的關(guān)注,在密碼設(shè)計(jì)領(lǐng)域就出現(xiàn)了如何設(shè)計(jì)好的布爾函數(shù)來(lái)抵抗代數(shù)攻擊,如何在保證代數(shù)免疫度高的前提下保證函數(shù)其他密碼學(xué)性質(zhì)也不會(huì)很差等問(wèn)題。密碼學(xué)研究人員致力于研究設(shè)計(jì)性質(zhì)優(yōu)秀的布爾函數(shù)來(lái)抵抗包括代數(shù)攻擊在內(nèi)的攻擊手段。近年來(lái),許多最優(yōu)代數(shù)免疫度函數(shù)類被密碼學(xué)者提出[2-8]，但是這些函數(shù)在達(dá)到代數(shù)免疫度達(dá)到最優(yōu)的情況下并沒(méi)有保證其他密碼學(xué)性質(zhì)的下界達(dá)到一定的高度,比如函數(shù)的非線性度、代數(shù)次數(shù)、平衡性等都沒(méi)有達(dá)到理想的情況。在文獻(xiàn)[9]中,作者構(gòu)造了一類平衡的最優(yōu)代數(shù)免疫度函數(shù),并且擁有最佳代數(shù)次數(shù)和較高的非線性度,然而它在抵抗快速相關(guān)免疫攻擊時(shí)并沒(méi)有表現(xiàn)出很好的抵抗能力。文獻(xiàn)[10]中作者構(gòu)造了一類偶數(shù)元的非線性度非常高的平衡代數(shù)免疫度最優(yōu)布爾函數(shù),并且通過(guò)枚舉說(shuō)明了n≤18時(shí)函數(shù)的非線性度超過(guò)了Carlet-Feng函數(shù)[11],而且通過(guò)實(shí)驗(yàn)驗(yàn)證其非線性度與理論上界非常近。我們知道Carlet-Feng函數(shù)時(shí)一類非常具有代表性的最優(yōu)代數(shù)免疫度布爾函數(shù),并且在抗擊快速代數(shù)攻擊時(shí)也有非常好的表現(xiàn),只是在函數(shù)的顯示表示上存在一定得缺陷。

不僅如此,如今許多布爾函數(shù)學(xué)者致力于研究代數(shù)免疫度最優(yōu)的旋轉(zhuǎn)對(duì)稱布爾函數(shù)。這是一類具有在循環(huán)群作用下保持不變性質(zhì)的布爾函數(shù),這類布爾函數(shù)在一定條件下可以具備良好的密碼學(xué)性質(zhì)。文獻(xiàn)[12]中構(gòu)造了兩類偶數(shù)階的旋轉(zhuǎn)對(duì)稱布爾函數(shù),在最優(yōu)代數(shù)免疫度的前提下作者還證明了這兩類函數(shù)具有足夠抵抗線性攻擊的代數(shù)次數(shù)以及非常高的非線性度。還有一些學(xué)者利用文獻(xiàn)[13]中Ding提出的多數(shù)函數(shù),構(gòu)造最優(yōu)代數(shù)免疫度布爾函數(shù)。在文獻(xiàn)[5]中證明了多數(shù)函數(shù)被證明具有最優(yōu)代數(shù)免疫度,并且得到了n元多數(shù)函數(shù)代數(shù)次數(shù)為2|log2n|,但是根據(jù)Lobanov界[14],多數(shù)函數(shù)的非線性度是最壞的。因此有許多在多數(shù)函數(shù)基礎(chǔ)上構(gòu)造的旋轉(zhuǎn)對(duì)稱布爾函數(shù)被提出[15-16],但是在非線性度上面并沒(méi)有巨大的突破。

本文利用文獻(xiàn)[10]中的方法構(gòu)造了一類偶數(shù)元的代數(shù)免疫度最優(yōu)布爾函數(shù),這類布爾函數(shù)是由一列多數(shù)函數(shù)和一個(gè)平衡的旋轉(zhuǎn)對(duì)稱的代數(shù)免疫度最優(yōu)布爾函數(shù)串聯(lián)而成,并且從理論上證明了這類函數(shù)的非線性度下界，以及代數(shù)次數(shù)下界。最后我們還簡(jiǎn)單分析了函數(shù)的相關(guān)免疫階數(shù), 函數(shù)是否具有更高的階數(shù)還需進(jìn)一步研究。

1 準(zhǔn)備知識(shí)

1.1 布爾函數(shù)的基本知識(shí)

f=[f(0,…,0),f(0,…,1),…,f(1,…,1)]

我們將所有n元布爾函數(shù)組成的集合記作Bn,那么對(duì)任意f∈Bn,我們可以將其唯一地寫F[x1,x2,…,xn]上的多項(xiàng)式：

對(duì)于f,g∈Bn,定義d(f,g)=wt(f-g)為f與g的距離,f與所有仿射函數(shù)的最小距離稱為f的非線性度,記作nl(f), 也即：

布爾函數(shù)的非線性度可以由其Walsh變換來(lái)刻畫。對(duì)于函數(shù)f∈Bn,定義f的Walsh變換為：

Pr?f=a|xi1=a1,xi2=a2,…,xim=am」=Pr[f=a]

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

1.2 旋轉(zhuǎn)對(duì)稱布爾函數(shù)

我們稱一個(gè)布爾函數(shù)f∈Bn是對(duì)稱的,如果對(duì)其自變量進(jìn)行任意的置換,它的值都不變,即：

f(x0,x1,…,xn-1)=f(xτ(0),xτ(1),…,xτ(n-1))

式中：τ是集合{0,1,…,n-1}上的置換。

布爾函數(shù)f是對(duì)稱的當(dāng)且僅當(dāng)其代數(shù)正規(guī)型可以寫成如下形式：

f=?f(Λ1),f(Λ2),…,f(Λkn)」

文獻(xiàn)[17]中構(gòu)造了一類偶數(shù)階的具有最優(yōu)代數(shù)免疫度的旋轉(zhuǎn)對(duì)稱布爾函數(shù)：

式中：c∈{0,1}。并且證明了這類函數(shù)具有較高的非線性度和代數(shù)次數(shù)。

1.3 布爾函數(shù)的串聯(lián)表示

2 函數(shù)的構(gòu)造與性質(zhì)分析

2.1 函數(shù)W(x,y)的構(gòu)造

t(x,y)=g(xy2k-2)

為bent函數(shù),且這個(gè)函數(shù)屬于Dillon在文獻(xiàn)[18]中提出的PSap類函數(shù)。并且在文獻(xiàn)[19]中證明了如果下面的假設(shè)成立,t(x,y)也是代數(shù)免疫度最優(yōu)布爾函數(shù)。

假設(shè)1對(duì)于x∈Z2k-1,x可被表示成長(zhǎng)度為k的二元串,若wt(x)表示x的二元串表示中1的個(gè)數(shù), 令：

Sr={(a,b)|a,b∈Z2k-1,a+b≡r(mod2k-1),wt(a)+wt(b)≤k-1}

這里1≤r≤2k-2,k≥2,那么|Sr|≤2k-1。

假設(shè)的正確性現(xiàn)在還是公開問(wèn)題, 文獻(xiàn)[19]中通過(guò)利用一種矩陣變換的算法已經(jīng)證明了這個(gè)假設(shè)在k≤29時(shí)均成立。

下面將上面函數(shù)改寫,令：

2.2 函數(shù)W(x,y)的代數(shù)免疫度

引理1[10]設(shè)函數(shù)f=f0‖f1‖…‖f2k-1,其中f0為平衡函數(shù),fi(1≤i≤2k-1)為代數(shù)免疫度最優(yōu)布爾函數(shù),那么f為代數(shù)免疫度最優(yōu)布爾函數(shù)。

定理1若假設(shè)1成立,則函數(shù)W(x,y)具有最優(yōu)代數(shù)免疫度。

證明由于多數(shù)函數(shù)是平衡的代數(shù)免疫度最優(yōu)函數(shù),因此tF(x,y)是bent函數(shù),并且具有最優(yōu)代數(shù)免疫度。因此對(duì)于任意的l∈An,我們可以將l寫成：

l=l0‖l1‖…‖l2k-1

因?yàn)閠F(x,y)是bent函數(shù),所以：

d(tF,l)=d(0,l0)+d(F1,l1)+…+

d(F2k-1,l2k-1)=2n-1-2n/2-1

2.3 函數(shù)W(x,y)的非線性度

定理2若假設(shè)1成立,2k元布爾函數(shù)W(x,y)滿足不等式：

證明任取l∈B2k,我們有：

因?yàn)閐(0,l)≤2k-1,所以：

d(W,l)≥d(T,l0)+22k-1-2k≥22k-1-

2.4 函數(shù)W(x,y)的代數(shù)次數(shù)

引理2[17]n元旋轉(zhuǎn)對(duì)稱布爾函數(shù)T(x)的代數(shù)次數(shù)滿足：

式中：m為某個(gè)正整數(shù)。

引理3[5]n元多數(shù)函數(shù)F(x)的代數(shù)次數(shù)滿足deg(F)=2?log2n」。

定理3當(dāng)k取非2冪次的偶數(shù)時(shí),函數(shù)W(x,y)的代數(shù)次數(shù)deg(W)≥n-1。

證明因?yàn)?/p>

若k為非2冪次整數(shù)時(shí),存在m∈N,使得2m+2≤k≤2m+1-1,2?log2k」=2m

于是由引理3

所以deg(W)≥n-1。

2.5 函數(shù)W(x,y)的相關(guān)免疫性

定理4函數(shù)W(x,y)的相關(guān)免疫階tW≥1。

且

于是

又

因此

3 結(jié) 語(yǔ)

本文構(gòu)造了一類偶數(shù)元的布爾函數(shù),這類函數(shù)在構(gòu)造方法上運(yùn)用了函數(shù)串聯(lián)的方法,其中串聯(lián)因子大部分采用多數(shù)函數(shù),在第一個(gè)位置的全零函數(shù)用一個(gè)旋轉(zhuǎn)對(duì)稱布爾函數(shù)來(lái)代替,以增加函數(shù)的復(fù)雜性和改變密碼學(xué)性質(zhì)。本文證明了此函數(shù)在保證最優(yōu)代數(shù)免疫度的情況下還具有非常高的非線性度和代數(shù)次數(shù)。并且由于多數(shù)函數(shù)結(jié)構(gòu)簡(jiǎn)單,因此在函數(shù)生成效率方面也比較有優(yōu)勢(shì)。最后我們還對(duì)函數(shù)的相關(guān)免疫階數(shù)進(jìn)行計(jì)算,其是否還具有更高階的相關(guān)免疫階尚需進(jìn)一步探索。

[1] Courtois N T,Meier W.Algebraic Attacks on Stream Ciphers with Linear Feedback[M]//Advances in Cryptology-EUROCRYPT 2003.Springer Berlin Heidelberg,2003:345-359.

[2] Braeken A,Preneel B.On the Algebraic Immunity of Symmetric Boolean Functions[C]//Progress in Cryptology-Indocrypt 2005,International Conference on Cryptology in India,Bangalore,India,December 10-12,2005,Proceedings.2005:35-48.

[3] Carlet C,Dalai D K,Gupta K C,et al.Algebraic immunity for cryptographically significant Boolean functions:analysis and construction[J].IEEE Transactions on Information Theory,2006,52(7):3105-3121.

[4] Dalai D K,Gupta K C,Maitra S.Cryptographically Significant Boolean Functions:Construction and Analysis in Terms of Algebraic Immunity[M]//Fast Software Encryption.Springer Berlin Heidelberg,2005:98-111.

[5] Dalai D K.Basic theory in construction of boolean functions with maximum possible annihilator immunity[J].Designs,Codes and Cryptography,2006,40(1):41-58.

[6] Li N,Qi W F.Construction and Analysis of Boolean Functions of 2t+1 Variables with Maximum Algebraic Immunity[C]//Advances in Cryptology-ASIACRYPT 2006,International Conference on the Theory and Application of Cryptology and Information Security,Shanghai,China,December 3-7,2006,Proceedings.2006:84-98.

[7] Li N,Qu L J,Qi W F,et al.On the Construction of Boolean Functions With Optimal Algebraic Immunity[J].IEEE Transactions on Information Theory,2008,54(3):1330-1334.

[8] Qu L J,Feng K,Liu F,et al.Constructing Symmetric Boolean Functions With Maximum Algebraic Immunity[J].IEEE Transactions on Information Theory,2009,55(5):2406-2412.

[9] Feng K,Liao Q,Yang J.Maximal values of generalized algebraic immunity[J].Designs,Codes and Cryptography,2009,50(2):243-252.

[10] Wang Q,Tan C H.Balanced Boolean functions with optimum algebraic degree,optimum algebraic immunity and very high nonlinearity[J].Discrete Applied Mathematics,2014,167(4):25-32.

[11] Carlet C,Feng K.An Infinite Class of Balanced Functions with Optimal Algebraic Immunity,Good Immunity to Fast Algebraic Attacks and Good Nonlinearity[M]//Advances in Cryptology-ASIACRYPT 2008.Springer Berlin Heidelberg,2008:425-440.

[12] Sun L,Fu F W.Constructions of even-variable RSBFs with optimal algebraic immunity and high nonlinearity[J].Journal of Applied Mathematics & Computing,2017:1-18.

[13] Ding C,Xiao G,Shan W.The Stability Theory of Stream Ciphers[M].Springer Berlin Heidelberg,1991.

[14] Lobanov M.Tight bound between nonlinearity and algebraic immunity[OL].2005.http://eprint.iacr.org/2005/441.pdf.

[15] Fu S,Qu L,Li C,et al.Balanced rotation symmetric boolean functions with maximum algebraic immunity[J].Iet Information Security,2011,5(2):93-99.

[16] Fu S,Li C,Matsuura K,et al.Construction of Rotation Symmetric Boolean Functions with Maximum Algebraic Immunity[M]//Cryptology and Network Security.Springer Berlin Heidelberg,2009:402-412.

[17] Su S,Tang X.Construction of rotation symmetric Boolean functions with optimal algebraic immunity and high nonlinearity[J].Designs,Codes and Cryptography,2014,71(2):183-199.

[18] Dillon J F.Elementary hadamard difference sets[C]//Proceedings of the Sixth Southeastern Conference on Combinatorics,Graph Theory,and Computing.1975:237-249.

[19] Tu Z,Deng Y.A conjecture about binary strings and its applications on constructing Boolean functions with optimal algebraic immunity[J].Designs Codes & Cryptography,2011,60(1):1-14.

[20] Massey J L.A spectral characterization of correlation-immune combining functions[J].IEEE Transactions on Information Theory,1988,34(3):569-571.