一類布爾函數(shù)的代數(shù)免疫度的下界

田葉，張玉清,2，胡予濮，伍高飛

(1. 西安電子科技大學(xué)綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710071；2. 中國(guó)科學(xué)院大學(xué)國(guó)家計(jì)算機(jī)網(wǎng)絡(luò)入侵防范中心，北京 101408)

一類布爾函數(shù)的代數(shù)免疫度的下界

田葉1，張玉清1,2，胡予濮1，伍高飛1

(1. 西安電子科技大學(xué)綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710071；2. 中國(guó)科學(xué)院大學(xué)國(guó)家計(jì)算機(jī)網(wǎng)絡(luò)入侵防范中心，北京 101408)

代數(shù)免疫度是衡量布爾函數(shù)抵抗代數(shù)攻擊的重要指標(biāo)。最近，Mesnager等研究了布爾函數(shù)的零化子與函數(shù)所對(duì)應(yīng)循環(huán)碼最小距離之間的聯(lián)系，代數(shù)免疫度的下界可以由對(duì)應(yīng)的循環(huán)碼的最小距離得到。解決了Mesnager提出的一個(gè)公開問題，給出了一類特定函數(shù)的零化子次數(shù)的下界，并得到一類布爾函數(shù)的代數(shù)免疫度的下界。

密碼學(xué)；布爾函數(shù)；零化子；代數(shù)免疫度；循環(huán)碼；最小距離

1 引言

2003年，Courtois和Meier[1]在歐洲密碼學(xué)年會(huì)上提出了一種針對(duì)布爾函數(shù)的代數(shù)攻擊方法，對(duì)基于線性反饋移位寄存器的流密碼構(gòu)成了極大的威脅，這種方法的主要原理是建立初始密鑰和輸出密鑰流比特之間的代數(shù)方程，通過線性化方法求解該超定的多變?cè)蔷€性方程組以得到初始密鑰。為了衡量布爾函數(shù)抵抗代數(shù)攻擊的能力，代數(shù)免疫的概念也隨即被引出[1]。為了抵抗代數(shù)攻擊[1～3]，流密碼系統(tǒng)中使用的布爾函數(shù)需要盡可能具有高的代數(shù)免疫度。

國(guó)內(nèi)外學(xué)者對(duì)具有最高代數(shù)免疫階的布爾函數(shù)進(jìn)行了深入的研究[1～13]。Courtois和 Meier[1]證明了n元布爾函數(shù)的最大代數(shù)免疫度是，達(dá)到此上界的布爾函數(shù)稱為具有最優(yōu)代數(shù)免疫度的函數(shù)。Dalai[4]首次構(gòu)造了偶數(shù)元的具有最優(yōu)代數(shù)免疫的布爾函數(shù)。Carlet和Feng[6]構(gòu)造了一類平衡的具有最優(yōu)代數(shù)免疫度的布爾函數(shù)。2010年，Rizomiliotis[7]給出了一個(gè)關(guān)于布爾函數(shù)具有最優(yōu)代數(shù)免疫度的充要條件。最近，Mesnager[13]研究了布爾函數(shù)的零化子與循環(huán)碼之間的關(guān)系，將對(duì)布爾函數(shù)零化子的研究轉(zhuǎn)化為對(duì)所對(duì)應(yīng)循環(huán)碼的最小距離的研究，為研究布爾函數(shù)的代數(shù)免疫提供了一種新方法。

本文解決了 Mesnager提出的一個(gè)公開問題，給出了一類特定函數(shù)的零化子的次數(shù)下界，并得到一類布爾函數(shù)的代數(shù)免疫度的下界。

2 預(yù)備知識(shí)

本節(jié)介紹將要用到的循環(huán)碼和布爾函數(shù)相關(guān)的一些基礎(chǔ)知識(shí)。

2.1 循環(huán)碼

循環(huán)碼是一類重要的線性碼，在通信系統(tǒng)、存儲(chǔ)設(shè)備中有著廣泛的應(yīng)用[14～19]。

設(shè)n為正整數(shù)，記F2為含有2個(gè)元素的二元域，F(xiàn)2n為F2上的n維向量空間，F(xiàn)2n為含有2n個(gè)元素的有限域。

設(shè)n、k、d分別為正整數(shù)。記C是參數(shù)為[n, k, d]的線性碼，其中，碼C的長(zhǎng)度為n，碼C最小距離為d，維數(shù)為k。若對(duì)C中的任意碼字進(jìn)行循環(huán)移位后仍然是C的碼字，則C稱為循環(huán)碼。

定理1[14](BCH界)α為域上的本原元。設(shè)

C是循環(huán)碼，其生成多項(xiàng)式為g( x)，對(duì)于一些整數(shù)d≥0,δ≥ 1，滿足

也就是說碼C有（δ?1）個(gè)α的相鄰冪作為零點(diǎn)，則碼C的最小距離d≥δ。

2.2 布爾函數(shù)

在密碼學(xué)中，最常用的表達(dá)布爾函數(shù)的形式是代數(shù)正規(guī)型(ANF)，表達(dá)式如式(2)所示。

其中，“⊕”表示 F2上的加，αu∈F2，u=(u1,u2,…,un)，函數(shù)f( x)的代數(shù)次數(shù)定義為代數(shù)正規(guī)型中系數(shù)不為零的次數(shù)最高的乘積項(xiàng)中變?cè)膫€(gè)數(shù)，即，記為deg f。代數(shù)次數(shù)小于等于1的布爾函數(shù)稱為仿射函數(shù)。

布爾函數(shù)f( x)也可以看成是從F2n到F2的一個(gè)映射，它可以唯一地表示為

定義1[1]令f( x)∈F2n，如果存在一個(gè)非零的函數(shù)g( x)∈F2n，使f( x) g( x)=0，那么稱g( x)是f( x)的零化子。函數(shù) f( x)的代數(shù)免疫度AI( f)定義為f( x)與f( x)+1的零化子的最小次數(shù)。

本文標(biāo)記MDA( f)為函數(shù)f的零化子的最小次數(shù)，MDA(f+1)為函數(shù)f+1的零化子的最小次數(shù)。因此f(x)的代數(shù)免疫度可以記為

3 主要結(jié)果

布爾函數(shù)在編碼理論中具有重要的作用[13,20～22]。例如一類著名的二元碼Reed-Muller碼就可以通過布爾函數(shù)獲得。最近，Mesnager等[13]把對(duì)布爾函數(shù)零化子的研究轉(zhuǎn)化為對(duì)循環(huán)碼的研究，為研究代數(shù)免疫提供了一種新方法。本節(jié)詳細(xì)介紹了Mesnager提出的公開問題的具體方法。首先介紹一些關(guān)于循環(huán)碼和代數(shù)免疫關(guān)系的已有的結(jié)論，更多的細(xì)節(jié)見文獻(xiàn)[13]。

定義 2[13]記S為F2n的一個(gè)子集，任意x∈S

推論1[13]記S?F2n，則C( S)為長(zhǎng)度為2n的線性碼，為長(zhǎng)度2n?1的循環(huán)碼。

記g∶ F2n→F2為F2n上布爾函數(shù)f的零化子，g( x)可以表示為，其中，對(duì)于根據(jù)零化子的定義，當(dāng)任意x∈supp(f )，g( x)=。當(dāng) f(0)=1時(shí)，g(0)=0，μ0=0，g( x)=。因此，為的一個(gè)碼字。記。但并不是中的每一個(gè)碼字都能對(duì)應(yīng)函數(shù) f的一個(gè)零化子。本文記B為的集合，其中，，且滿足時(shí)，

推論2[13]布爾函數(shù)f∶F2n→F2且滿足f(0)=1，那么集合與函數(shù) f的零化子一一對(duì)應(yīng)。

定理2[13]設(shè)函數(shù)f∶F→F滿足 f(0)=1，記2n2δ為的最小距離。設(shè)d為滿足不等式的最小正整數(shù)，則MDA( f)≥d。

定理 3[13]設(shè)函數(shù)f∶F→F滿足f(0)=0，2n2記δ為的最小距離。設(shè)d為滿足不等式的最小正整數(shù)，則MDA( f)≥d?1。

定理 4[13]設(shè)函數(shù)f∶F→F，記δ為2n2的最小距離，記δ′為的最小距離。p為滿足不等式的最小正整數(shù)，p′為滿足不等式的最小正整數(shù)。因此，集合Sf對(duì)應(yīng)的布爾函數(shù)的代數(shù)免疫度AI( f)具有如下的下界。

1) 如果f(0)=1，則AI( f)≥min(p,p′?1)。

2) 如果f(0)=0，則AI( f)≥min(p?1,p′)。

設(shè)b和δ為 2個(gè)非負(fù)整數(shù)。記V(α,b,δ?1)={αb,αb+1,…,αb+δ?2}，其中，α為F中的一個(gè)本原2n元，記N=2n?1。

文獻(xiàn)[13]提出的公開問題具體描述如下，給定布爾函數(shù)f∶F2n→F2，t、b、k、δ均為正整數(shù)，m為與N互素的正整數(shù)，設(shè)集合Sf為

那么就存在函數(shù)1+f的零化子的最小次數(shù)的下界如何表示的問題。

注：當(dāng)m≤δ?2時(shí)，V (α,b,δ?1)∪V(α,b+m,δ?1)∪…∪V(α,b+km,δ?1)=V(α,b, km +δ?1)。下文，只考慮m＞δ?2的情形。

為了解決這個(gè)問題，首先對(duì)文獻(xiàn)[13]中的定理進(jìn)行完善得到定理5。

定理5布爾函數(shù)f∶F2n→F2，假設(shè)

于是有：

1) 當(dāng) f(0)=1時(shí)，MDA( f)≥p；

2) 當(dāng) f(0)=0時(shí)，MDA( f)≥p?1。

證明根據(jù)定義有

定理6對(duì)文獻(xiàn)[13]中的定理進(jìn)行了完善。

定理6布爾函數(shù)f∶F2n→F2，t、b、k、δ均為正整數(shù)，m為與N互素的正整數(shù)，假設(shè)

于是有：

1) 當(dāng) f(0)=1時(shí)，MDA( f)≥p；

2) 當(dāng) f(0)=0時(shí)，MDA( f)≥p?1。

證明根據(jù)Sf的定義，可得

設(shè)集合U為Sf中α的所有指數(shù)的集合，即式(5)中α的所有指數(shù)的集合。

設(shè)整數(shù)d0=k+δ，假設(shè)中含有重量ω小于d0的碼字，即ω＜k +δ。由于為循環(huán)碼，某一重量為ω的碼字可以表示為下面的碼多項(xiàng)式，其中，γ∈F ，0＜s＜N。i2ni

當(dāng) j∈U ，Pj=?1 ，前面假設(shè)ω＜k+δ，所以ω?k?1＜δ? 1，因此式(8)可以轉(zhuǎn)化為

結(jié)合式(9)和式(10)，可以得出φ(1)=0，然而與φ(1)≠0是矛盾的。因此，假設(shè)ω＜k+δ是錯(cuò)誤的，從而ω≥k+δ，也就是說中不存在任何重量ω小于k+δ的碼字，即的最小距離至少為k+δ。

再根據(jù)定理2和定理3，得到定理6，即完成了證明。

定理7給出公開問題的答案，并利用證明定理6的方法對(duì)其進(jìn)行證明。

定理7布爾函數(shù)f∶F2n→F2，t, b, k,δ均為正整數(shù)，m為與N互素的正整數(shù)，假設(shè)

于是有如下情況。

1) 當(dāng)m(1+k)＜2n?1時(shí)

① 如果 f(0)=1，則MDA(1+f)≥p ；

② 如果 f(0)=0，則MDA(1+f)≥p ?1。

2) 當(dāng)m(1+k)≥2n時(shí)

① 如果 f(0)=1，則MDA(1+f)≥p ；

② 如果 f(0)=0，則MDA(1+f)≥p ?1。

證明由Sf的定義可得

其中，

設(shè)集合U為S1+f中α的所有指數(shù)的集合，即式(12)～式(16)中α的所有指數(shù)的集合。

如果2n?km?δ=m?δ+1，則2n?1=m(1+k)，這與(m,2n?1)=1矛盾，所以2n?1≠m(1+k)。

下面分2種情況考慮。

1) 當(dāng)m(1+k)＜2n?1時(shí)，設(shè)整數(shù)d=k+m?0δ+2，假設(shè)中含有重量ω小于d0的碼字，即為某一重量為ω的碼字的碼多項(xiàng)式，其中，γi∈F2n，0＜si＜N。

令整數(shù)l=b+δ? 1，構(gòu)造等式Ζ為

前面假設(shè)ω＜k+m ?δ+2，即ω?k?1＜m ?δ+ 1，并且當(dāng) j∈U，Pj=?1 ，所以式(19)也可以轉(zhuǎn)化成式(21)。

結(jié)合式(20)和式(21)，可以得出φ(1)=0，然而與φ(1)≠0是矛盾的。因此，假設(shè)ω＜k+m ?δ+2是錯(cuò)誤的，從而ω≥k+m ?δ+2，也就是說中不存在任何重量ω小于k+m?δ+2的碼字，即的最小距離至少為k+m?δ+2。

2) 當(dāng)m^(1+k)≥2n時(shí)，設(shè)整數(shù)d0=k+m?δ+1，假設(shè)C( S1+f)中含有重量ω小于d0的碼字，即ω＜k+m ?δ+1。令為某一重量為ω的碼字的碼多項(xiàng)式，其中，γi∈F2n，0＜si＜N。

因?yàn)閟i≠0，(m, N)=1，所以

令整數(shù)l=b+δ? 1，構(gòu)造如下的等式Ζ。

前面假設(shè)ω＜k+m ?δ+1，即ω?k?1＜m ?δ，當(dāng) j∈U，Pj=?1 ，所以式(24)可以轉(zhuǎn)化成式(26)。

結(jié)合式(25)和式(26)，可以得出φ(1)=0，然而與前面φ(1)≠0是矛盾的。因此假設(shè)ω＜k+m ?δ+1是錯(cuò)誤的，也就是說中不存在任何重量ω小于k+m?δ+1的碼字，即的最小距離至少為k+m?δ+ 1。再根據(jù)定理2和定理3，就得到了定理7。

結(jié)合布爾函數(shù)的代數(shù)免疫度的定義AI( f)=min(MDA( f),MDA(1+f ))以及定理6和定理 7，本文得到了一類布爾函數(shù)的代數(shù)免疫度的一個(gè)下界。

定理8函數(shù)f∶F2n→F2，t、b、k、δ均為正整數(shù)，m為與N互素的正整數(shù)，假設(shè)

于是有如下情況。

1) 當(dāng)m(1+k)＜2n?1時(shí)

① 如果 f(0)=0，則AI( f)≥min(p, p^?1)；

② 如果 f(0)=1，則AI( f)≥min(p?1,p^)。

2) 當(dāng)m(1+k)≥2n時(shí)^

① 如果 f(0)=0，則AI( f)≥min(p, p?^1)；

② 如果 f(0)=1，則AI( f)≥min(p?1,p)。

4 結(jié)束語

布爾函數(shù)在密碼學(xué)中有著重要的作用。一個(gè)好的布爾函數(shù)需要具有高的代數(shù)免疫度以抵抗代數(shù)攻擊。如何構(gòu)造具有高的代數(shù)免疫度的布爾函數(shù)仍然是一個(gè)重要的問題。本文主要研究了布爾函數(shù)零化子與循環(huán)碼最小距離之間的關(guān)系，解決了Mesnager提出的一個(gè)公開問題，即給出特定布爾函數(shù)的零化子次數(shù)的下界，并且給出了一類布爾函數(shù)的代數(shù)免疫度的下界。在未來的工作中，考慮利用一些具有優(yōu)良性質(zhì)的循環(huán)碼來構(gòu)造具有最優(yōu)代數(shù)免疫度的布爾函數(shù)是非常有意義的。

[1]COURTOIS N, MEIER W. Algebraic attacks on stream ciphers with linear feedback[C]//Cryptology-Eurocrypt 2003, LNCS 2656. Berlin:Springer-Verlag, 2003: 345-359.

[2]ARMKNECHT F, KRAUSE M.Algebraic attacks on combiners with memory[C]//Cryptology-Crypto. 2003: 162-175.

[3]MEIER W, PASALIC E, CARLET C. Algebraic attacks and decomposition of Boolean functions[C]//Cryptology -Eurocrypt 2004, LNCS 3027. 2004: 474-491.

[4]DALAI D, MAITRA S, SARKAR S. Cryptographically significant Boolean functions:construction and analysis in terms of algebraic immunity[J]. Fast Software Encryption , 2005, 3557:98-111.

[5]CARLET C, DALAI D, GUPTA C. Algebraic immunity for cryptographically significant Boolean function: analysis and construction[J].IEEE Transactions on Information Theory, 2006, 52(7):3105-3121.

[6]CARLET C, FENG K. An infinite class of balanced functions with optimal algebraic immunity, good immunity to fast algebraic attacks and good nonlinearity[C]//Cryptology-Asiacrypt 2008, LNCS 5350.2008, 5350:425-440.

[7]RIZOMILIOTIS P. On the resistance of Boolean functions against algebraic attacks using univariate polynomial representation[J]. IEEE Trans Information Theory, 2010, 56(8):4014-4024.

[8]TU Z, DENG Y. A conjecture on binary string and its applications on constructing Boolean functions of optimal algebraic immunity [J]. Designs Codes and Cryptography, 2011, 60(1): 1-14.

[9]HELLESTH T, RONJOM S. Simplifying algebraic attacks with univariate analysis[C]//Information Theory and Applications Workshop(ITA). 2011:1-7.

[10]TANG D, CARLET C, TANG X. Highly nonlinear Boolean functions with optimal algebraic immunity and good behavior against fast algebraic attacks[J]. IEEE Trans Inf Theory, 2013, 59(59):653-664.

[11]LIN J, WANG M, LI Y. On annihilators in fewer variables:basic theory and applications[J]. Chinese Journal of Electronics, 2013, 22(3):489-494.

[12]歐智慧, 趙亞群, 李旭. 一類密碼函數(shù)的構(gòu)造與分析[J].通信學(xué)報(bào),2013, 4(4): 106-113.OU Z H, ZHAO Y Q, LI X. Construction and analysis of one class of cryptographic functions[J]. Journal on Communications, 2013, 34(4):106-113.

[13]MESNAGER S. A note on linear codes and algebraic immunity of Boolean Functions[C]//21st International Symposium on Mathematical Theory of Networks and Systems. 2014.

[14]MACWILLIAMS F,SLOANE N. The theory of error-correcting Codes[M]. North-Holland Mathematical Library. Amsterdam, The Netherlands: North-Holland, 1977.

[15]HUFFMAN W, PLESS V. Fundamentals of error-correcting codes[M].Cambridge, UK: Cambridge Univ. Press, 2003.

[16]BETTI E, SALA M. A new bound for the minimum distance of a cyclic code from its defining set[J].IEEE Trans Information Theory,2006, 52(8):3700-3706.

[17]BETTEN A, BRAUN M, FRIPERTINGER H. Error- correcting linear codes[M]. Berlin,Germany: Springer- Verlag, 2006.

[18]GAO J, HU Y, LI X. Linear span of the optimal frequency hopping sequences from irreducible cyclic Codes[J]. Chinese Journal of Electronics, 2015, 24(4): 818-823.

[19]DING C, DU X, ZHOU A. The bose and minimum distance of a class of BCH codes[J]. IEEE Trans Information Theory, 2015, 61(5): 2351- 2356.

[20]FENG X,GONG G. On algebraic immunity of trace inverse functions on finite fields of characteristic two[J]. Journal of Systems Science and Complexity, 2016, 29(1):272-288.

[21]WU D,QI W. On the spectral immunity of periodic sequences restricted to binary annihilators[J]. Designs Codes and Cryptography,2016, 78(2):533-545.

[22]DING C.A construction of binary linear codes from Boolean functions[J]. Discrete Mathematics, 2016, 339(9): 2288-2303.

New bound of algebraic immunity of a class of Boolean function

TIAN Ye1, ZHANG Yu-qing1,2, HU Yu-pu1, WU Gao-fei1
(1. State Key Laboratory of Integrated Services Networks, Xidian University, Xi’an 710071, China;2. National Computer Network Intrusion Protection Center, University of Chinese Academy of Sciences, Beijing 101408, China)

Algebraic immunity quantified the resistance of a Boolean function to the algebraic attack. Recently, Mesnager,et al showed that there were direct linked between the annihilators used in algebraic attacks and the coding theory. They showed that the lower bound of the algebraic immunity of Boolean functions could been derived from the minimum distance of the associated cyclic codes. An open problem proposed by Mesnager is settled with a detailed proof. Also, a lower bound of algebraic immunity of a class of Boolean functions will be introduced.

cryptography, Boolean functions, annihilators, algebraic immunity, cyclic code, minimum distance

s:The National Natural Science Foundation of China (No.61572460, No.61272481), The National Key Research and Development Project (No.2016YFB0800703), The National Information Security Special Projects of National Development, The Reform Commission of China (No.(2012)1424), China 111 Project (No.B16037)

TN918

A

10.11959/j.issn.1000-436x.2016200

2016-05-11；

2016-08-24

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61572460, No.61272481）；國(guó)家重點(diǎn)研究計(jì)劃基金資助項(xiàng)目（No.2016YFB0800703）；國(guó)家發(fā)展改革委員會(huì)信息安全專項(xiàng)基金資助項(xiàng)目（No.(2012)1424）；國(guó)家111計(jì)劃基金資助項(xiàng)目（No.B16037）

田葉（1987-），女，山西平遙人，西安電子科技大學(xué)博士生，主要研究方向?yàn)椴紶柡瘮?shù)、序列密碼的分析與構(gòu)造。

張玉清（1966-），男，陜西寶雞人，博士，中國(guó)科學(xué)院大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)榫W(wǎng)絡(luò)與信息系統(tǒng)安全。

胡予濮（1955-），男，河南濮陽人，西安電子科技大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)樾蛄忻艽a與分組密碼、網(wǎng)絡(luò)安全協(xié)議的設(shè)計(jì)與分析。

伍高飛（1987-），男，河南靈寶人，西安電子科技大學(xué)博士生，主要研究方向?yàn)樾蛄性O(shè)計(jì)和密碼學(xué)。