王喜鳳，張　偉，周建欽安徽工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 馬鞍山 243002

?

具有第二下降點(diǎn)6錯(cuò)線性復(fù)雜度的2n周期序列*

王喜鳳，張偉+，周建欽
安徽工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 馬鞍山 243002

WANG Xifeng,ZHANG Wei,ZHOU Jianqin.2n-periodic binary sequences with 6-error linear complexity as the second descent point.Journal of Frontiers of Computer Science and Technology,2016,10(6):838-846.

摘要：線性復(fù)雜度和k錯(cuò)線性復(fù)雜度是衡量流密碼強(qiáng)度的重要指標(biāo)，通常這兩個(gè)指標(biāo)越大就越能抗擊明文攻擊。為了更進(jìn)一步地研究密鑰流序列，利用構(gòu)造方法和方體理論分析了具有第二下降點(diǎn)6錯(cuò)線性復(fù)雜度的2n周期序列，得到了所有可能6錯(cuò)線性復(fù)雜度的取值形式。分析并推導(dǎo)了具有2錯(cuò)線性復(fù)雜度為第一次下降點(diǎn)且6錯(cuò)線性復(fù)雜度為第二次下降點(diǎn)的2n周期序列的計(jì)數(shù)公式。使用這種方法也可以推導(dǎo)出其他具有第二次下降點(diǎn)或者第三次下降點(diǎn)的k錯(cuò)線性復(fù)雜度序列的相關(guān)性質(zhì)。

關(guān)鍵詞：周期序列；線性復(fù)雜度；k錯(cuò)線性復(fù)雜度；方體理論

ISSN 1673-9418CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10(06)-0838-09

E-mail:fcst@vip.163.com

http://www.ceaj.org

Tel:+86-10-89056056

1　引言

將能夠產(chǎn)生序列s的最短的線性反饋移位寄存器（linear feedback shifting register，LFSR）的級(jí)數(shù)稱為序列s的線性復(fù)雜度，記為L(s)。線性復(fù)雜度L(s)及其穩(wěn)定性在衡量流密碼的強(qiáng)度時(shí)具有重要作用。通常線性復(fù)雜度足夠大就越能抗擊明文攻擊，但是有些序列的線性復(fù)雜度不穩(wěn)定，改變一個(gè)周期內(nèi)的若干個(gè)元素就能使序列的線性復(fù)雜度產(chǎn)生極大的變化。為了更好地衡量流密碼的強(qiáng)度，我國學(xué)者Ding等人[1]率先提出了重量復(fù)雜度和球體復(fù)雜度。隨后，國外學(xué)者Stamp等人[2]又提出了k錯(cuò)線性復(fù)雜度的概念。k錯(cuò)線性復(fù)雜度Lk(s)反映了序列線性復(fù)雜度的穩(wěn)定性[3-6]。

為了研究一個(gè)序列s的k錯(cuò)線性復(fù)雜度在哪些點(diǎn)下降。Etzion等人[7]最早提出了關(guān)鍵線性復(fù)雜度分布（critical error linear complexity spectrum，CELCS）的概念，CELCS由一系列關(guān)鍵錯(cuò)誤點(diǎn)(k,Lk(s))構(gòu)成，滿足k

本文以Games-Chan算法[14]為基礎(chǔ)，利用方體理論，研究了具有2錯(cuò)線性復(fù)雜度為第一次下降點(diǎn)且6錯(cuò)線性復(fù)雜度為第二次下降點(diǎn)的周期序列的性質(zhì)；分析了兩次線性復(fù)雜度下降的關(guān)系，給出了6錯(cuò)線性復(fù)雜度的取值形式，并且給出了滿足這種情況的序列的計(jì)數(shù)公式。

2　預(yù)備知識(shí)與引理

首先介紹幾個(gè)重要的引理和定義，然后介紹基于Games-Chan算法的方體理論，以及如何用篩選法確定關(guān)鍵錯(cuò)誤線性復(fù)雜度分布。

設(shè)有限域GF（2）上的兩個(gè)向量分別為：α=(x1,x2, …,xn)和 β=(y1,y2,…,yn)，則定義 α+β=(x1+y1,x2+ y2,…,xn+yn)，本文討論的序列都是在有限域GF（2）中的序列，其中“+”和“⊕”運(yùn)算都為模2運(yùn)算。

2.1相關(guān)定義和引理

文獻(xiàn)[15-20]具體介紹了方體理論及相關(guān)性質(zhì)，這里只給出下文將要用到的相關(guān)定義。

引理1[15]設(shè)周期N=2N的二元序列s，其線性復(fù)雜度L(s)=2n，當(dāng)且僅當(dāng)該序列的一個(gè)周期中漢明重量為奇數(shù)。

引理2[16]設(shè)周期N=2N的二元序列s1和s2，若L(s1)=L(s2)，則L(s1+s2)

則映射具有以下性質(zhì)：

注：WH(s(n))意為序列s(n)的漢明重量。

引理4[18]設(shè)滿足線性復(fù)雜度為L,0≤L≤2n的二元周期序列的個(gè)數(shù)N(L)為：

定義1[19]設(shè)存在正整數(shù)x和y，若二進(jìn)制周期序列s中兩個(gè)元素位置差為(2x+1)×2y，則稱這兩個(gè)元素的距離為2y。

定義2[19]設(shè)周期為2n的二元序列s中有2m個(gè)非零元素，其中0≤i1

引理5[20]設(shè)s為周期為2n的二元序列且為m方體，若m方體的邊長分別為2i1,2i2,…,2im且0≤i1< i2<…

2.2篩選法

設(shè)c為二元序列s的k錯(cuò)線性復(fù)雜度，e是漢明重量為k的誤差序列，那么設(shè)s=t+e，L(t)=c。若有如下框架：設(shè)T={t|L(t)=c}，E={e|WH(e)=k}，TE={t+e| t∈T,e∈E}，其中e是WH(e)=k的序列，t是線性復(fù)雜度為c的序列。使用篩選法，目的是從TE中篩選出Lk(t+e)=c的序列t+e。

對(duì)于給定線性復(fù)雜度c，求滿足Lk(t+e)=c的序列t+e，需要排除一些不滿足條件的序列。此時(shí)不滿足條件的序列有兩類：一類是 t+u∈TE，但Lk(t+u)

對(duì)于Lk(t+u)

對(duì)于 Lk(x+u)=Lk(y+v)=c，但 x+u=y+v的情況。由x+u=y+v可知x+y=u+v；又因?yàn)長(x)=L(y)= c,根據(jù)引理2知L(x+y)

3　具有第二下降點(diǎn)6錯(cuò)線性復(fù)雜度的周期序列計(jì)數(shù)

首先使用方體理論來分析k錯(cuò)線性復(fù)雜度的第一次和第二次下降的關(guān)系，并給出所有可能的取值形式。然后給定序列線性復(fù)雜度的第一次下降點(diǎn)和第二次下降點(diǎn)，求出滿足條件的所有可能序列的計(jì)數(shù)。

定理1 設(shè)周期二元序列 s(n)，若 L6(s(n))

證明 利用反證法進(jìn)行證明，假設(shè)i0?{i,j,k}。

存在2n周期二元序列s(n)，序列s(n)改變兩個(gè)元素得到序列u={1111 0000 1111 0000}。此時(shí)序列u的線性復(fù)雜度L(u)=L2(s(n))=2n-(20+21+23)，可知i=0, j=1,k=3。若存在i0?{i,j,k}，那么i0=2或i0=4。

當(dāng)i0=2時(shí)，因?yàn)樾蛄?s(n)的線性復(fù)雜度 L(s(n))= 2n-2i0，所以存在序列v={1000 1000 0000 0000}使得u+v={0111 1000 1111 0000}，并且序列s(n)的線性復(fù)雜度L(s(n))=L(u+v)=2n-22。此時(shí)序列s(n)改變兩個(gè)元素后線性復(fù)雜度出現(xiàn)第一次下降且L(u)=L2(s(n))= 2n-(20+21+23)=5，根據(jù)序列性質(zhì)知第二次下降點(diǎn)Lk(s(n))

式中“…”代表L(u+v+t)，并且

可以看出，只有當(dāng)k=8時(shí)，即WH(t)=8時(shí)，序列線性復(fù)雜度才出現(xiàn)第二次下降，此時(shí)與條件矛盾。

當(dāng)i0=4時(shí)，序列s(n)的線性復(fù)雜度L(s(n))=2n-24，因?yàn)閚=i0=4，根據(jù)方體理論的性質(zhì)，當(dāng)i0=4時(shí)，兩個(gè)非零元素的距離為24=16。因?yàn)樾蛄械拈L度為16，所以兩個(gè)非零元素的最長距離為8。從而不存在i0=4這種情況。

綜上所述，只有當(dāng)k=8時(shí)，即WH(t)=8時(shí)，序列線性復(fù)雜度才出現(xiàn)第二次下降，此時(shí)與條件矛盾。因此假設(shè)不成立，則i0∈{i,j,k}。

定理2已知周期為2n的二元序列 s(n)，且L(s(n))<2n，則：

（1）L6(s(n))L(c2)>…，其中c1是1方體，c2是3方體，且c1、c2的非零元素均不重合，或有一個(gè)重合，或有兩個(gè)重合這3種情況。其中有兩個(gè)重合這種情況等價(jià)于c1是1方體，c2是2方體，且c1、c2的非零元素均不重合。

（2）L6(s(n))

證明（1）①必要性：由Kurosawa[4]知，一個(gè)周期為s(n)的二元序列s，線性復(fù)雜度為：

存在kmin=2m使得序列s的k錯(cuò)線性復(fù)雜度小于L(s(n))。因c1是1方體，c2是3方體，則L5(s(n))=L4(s(n))=L2(s(n))。

當(dāng)c1、c2的非零元素均不重合時(shí)，去掉c1的兩個(gè)非零元素線性復(fù)雜度第一次下降。在c1上增加6個(gè)1將變成一個(gè)3方體，和c2形成一個(gè)4方體，此時(shí)線性復(fù)雜度第二次下降，即L6(s(n))

當(dāng)c1的非零元素和c2的一個(gè)非零元素重合時(shí)，將c2中重合的位置加上非零元素，將c1中沒有重合的非零元素去掉，即將序列s(n)中的c1去掉，此時(shí)L2(s(n))

當(dāng)c1的非零元素和c2非零元素都相交時(shí)，將c2中兩個(gè)重合的位置加上非零元素，此時(shí)3方體c2決定著此時(shí)序列的線性復(fù)雜度，故L2(s(n))

②充分性：假設(shè)c1、c2、c3均為1方體，其中3個(gè)方體的非零元素互不重合，且在c1、c2、c3中添加兩個(gè)非零元素時(shí)，不能構(gòu)成一個(gè)方體。首先去掉c1時(shí)，線性復(fù)雜度下降；再同時(shí)去掉c1和c2時(shí)，線性復(fù)雜度再次下降，即L4(s(n))

假設(shè)c1為1方體，c2為2方體，c1和c2的非零元素可以不重合，可以有一個(gè)重合，也可以有兩個(gè)重合。當(dāng) c1和 c2的非零元素可以不重合時(shí)，如{1111 1100 0000 0000}，此時(shí)等價(jià)于c1為1方體，c2為3方體，且c1和c2非零元素有兩個(gè)重合。當(dāng)c1和c2非零元素有兩個(gè)重合時(shí)，分別去掉c1和c2非零元素，則線性復(fù)雜度下降，即L4(s(n))

假設(shè)c1為1方體，c2為4方體，c1和c2的非零元素可以不相交，可以有一個(gè)重合，可以有兩個(gè)重合。因?yàn)閏2為4方體，所以第二次下降至少需要改變14個(gè)非零元素線性復(fù)雜度才下降，即L14(s(n))

綜上所述，只有當(dāng)c1為1方體，c2為3方體時(shí)滿足上述情況。

（2）由（1）易知L6(s(n))

定理3設(shè)序列s(n)為周期為2n的二元序列，如果L6(s(n))

證明 T={t|L(t)=L}，E={e|L(e)=6}，TE={t+e|t∈T,e∈E}，其中L(t)=L6(s(n))，WH(e)=6，L2(s(n))=2n-(2i+ 2j+2k)，使用篩選法，從TE中篩選出L6(t+e)=L的序列t+e。關(guān)于L6(t+e)

當(dāng)i0=i時(shí){i1,i2,i3}不包含{i,j},{i,k}。假設(shè)n=5，i01，i=0，j=1，k=3。

則存在序列

則存在序列

同理可證：當(dāng)i0=j時(shí){i1,i2,i3}不包含{i,j},{j,k}；i0= k時(shí){i1,i2,i3}不包含{i,k},{j,k}。

同理，v={0101 0000 1100 0000 0101 0000 0000 0000}時(shí)，可證i1≠i；v={0111 0000 0100 0000 1000 0000 1000 0000}時(shí)，可證i1≠k;v={0111 1000 0100 1000 0000 0000 0000 0000}時(shí)，可證i2≠k。

定理4設(shè)s(n)是2n周期的二元序列，線性復(fù)雜度為2n。

（1）L2(s(n))=2n-(2i+2j+2k),L6(s(n))

①當(dāng)i0=i時(shí)

（2）若L6(s(n))=0，則滿足上述條件的2n周期的二元序列s(n)的個(gè)數(shù)有如下3種情況：

①當(dāng)i0=i時(shí)

②當(dāng)i0=j時(shí)

③當(dāng)i0=k時(shí)

證明 定理4的證明過程中，首先利用構(gòu)造法分析出L6(s(n))=0的情況的具體個(gè)數(shù)，然后利用篩選法，篩選出符合條件的L6(s(n))≠0的序列，具體過程如下：

（1）由引理知，線性復(fù)雜度L(t)=L的2n周期二元序列t的個(gè)數(shù)是2L-1。

（2）下面推導(dǎo)當(dāng)i0=i時(shí)序列e的個(gè)數(shù)，其中WH(e)=6且L2(e)=2n-(2i+2j+2k)。

步驟1設(shè)s(i)是周期為2i的二元序列，線性復(fù)雜度為2i且WH(s(i))=1，則s(i)的個(gè)數(shù)為2i。

步驟2設(shè)s(i+1)是周期為2i+1的二元序列，線性復(fù)雜度為2i+1-2i=2i且WH(s(i+1))=2，則s(i+1)的個(gè)數(shù)為2i。

步驟3當(dāng) j>i時(shí)，設(shè)s(j)是周期為2j的二元序列，線性復(fù)雜度為2j-2i且WH(s(j))=2，則s(j)的個(gè)數(shù)為2i×(22)j-i-1。

步驟4設(shè)s(j+1)是周期為2j+1的二元序列，線性復(fù)雜度為2j+1-(2i+2j)且WH(s(j+1))=4，則s(j+1)的個(gè)數(shù)為2i×(22)j-i-1。

步驟5當(dāng)k>j時(shí)，設(shè)s(k)是周期為2k的二元序列，線性復(fù)雜度為2k-(2i+2j)且WH(s(k))=4，則s(k)的個(gè)數(shù)為2i×(22)j-i-1×(24)k-j-1。

步驟6已知序列s(k)中已經(jīng)有4個(gè)非零元素分別是p1、p2、p3、p4，在序列s(k+1)上加兩個(gè)非零元素p5、p6，構(gòu)成周期為2k+1的二元序列s(k+1)。因p5、p6的距離為2k-2i，使p5、p6和 p1、p2、p3、p4任意元素的距離為2k，則一共有4種方案，若p1、p2和p5、p6的距離為2k，則剩下的兩個(gè)元素p3、p4有22種選擇，則s(k+1)序列的個(gè)數(shù)為2i×(22)j-i-1×(24)k-j-1×4×22。

步驟7當(dāng)s>k時(shí)，設(shè)s(n)是周期為2n的二元序列，線性復(fù)雜度為2n-(2i+2j+2k)且WH(e)=6，則序列s(n)的個(gè)數(shù)是2i×(22)j-i-1×(24)k-j-1×4×22×(26)n-k-1。

由上可知，當(dāng)i0=i時(shí)，滿足e∈E，L(e)=2n-2i0，L2(e)=2n-(2i+2j+2k)，i0=i的序列e的個(gè)數(shù)為：

同理可證，當(dāng)i0=j時(shí)，滿足e∈E，L(e)=2n-2i0，的序列e的個(gè)數(shù)：

當(dāng) i0=k時(shí)，滿足 e∈E，L(e)=2n-2i0，L2(e)= 2n-(2i+2j+2k)，i0=k的序列e的個(gè)數(shù)為：

由上可知，當(dāng)L6(s(n))=0時(shí)，滿足條件的周期為2n的二元周期序列s(n)在i0=i,i0=j,i0=k這3種情況下的個(gè)數(shù)。

（3）因s+u,t+v∈SE，L6(s+u)=L6(t+v)=L，其中s≠t，u≠v，但s+u=t+v，檢查是否存在序列v，WH(u)=WH(v)=6，使L(u+v)=L(s+t)

①序列v的個(gè)數(shù)與參數(shù)α、β相關(guān)，其中β<α

下面討論i0=i時(shí)重復(fù)序列的具體個(gè)數(shù)：任給u∈E，存在1個(gè)序列v，使L(u+v)=2n-(2i+2α+2k)< L，此時(shí) λi=1；存在2個(gè)序列 v，使 L(u+v)=2n-(2α+2k)

下面舉例證明，假設(shè)n=5，i0=1，i=1，j=2，k=4，α=3

則存在序列

使L(u(5)+v(5)1)=2n-(2i+2α+2k)=25-(21+23+24)<25-(20+23+24)=L，則存在

同理可得，i0=j時(shí)，任給u∈E，存在1個(gè)序列v，使L(u+v)=2n-(2j+2α+2k)

下面分別舉例說明i0=i，i0=j，i0=k的情況：

當(dāng)i0=i時(shí)，假設(shè)n=5，i0=1，i=1，j=2，k=3，已知序列

則存在序列

同理可證：

綜上所述，定理4得證。

下面舉例來進(jìn)一步驗(yàn)證定理4，并且其正確性已用計(jì)算機(jī)程序進(jìn)行了驗(yàn)證。

例1n=5，i0=0，i=0，j=1，k=3，i1=1，i2=2，

例2n=5，i0=3，i=0，j=1，k=3，i1=0，i2=2，

4　結(jié)論

本文在Games-Chan算法和篩選法的基礎(chǔ)上，用方體理論和篩選法研究周期為2n的二進(jìn)制序列s(n)的6錯(cuò)線性復(fù)雜度的相關(guān)性質(zhì)，其中序列s(n)的2錯(cuò)線性復(fù)雜度是第一次下降，序列s(n)的6錯(cuò)線性復(fù)雜度是第二次下降。給出了6錯(cuò)線性復(fù)雜度的所有可能的取值形式，并且推導(dǎo)出了完整的計(jì)數(shù)公式。對(duì)于其他具有第二次下降點(diǎn)k錯(cuò)線性復(fù)雜度序列，也能使用此種方法。同理可研究具有三次下降點(diǎn)k錯(cuò)線性復(fù)雜度的序列。

References:

[1]Ding Cunsheng,Xiao Guozhen,Shan Weijuan.The stability theory of stream ciphers[M]//Lecture Notes in Computer Science 561.Berlin,Heidelberg:Springer,1991:85-88.

[2]Stamp M,Martin C.F.An algorithm for the k-error linear.co mplexity of binary sequence with period2n[J].IEEE Transactions on Information Theory,1993,39(4):1398-1401.

[3]Kurosawa K,Sato F,Sakata T,et al.A relationship between linear complexity and k-error linear complexity[J].IEEE Transactions on Information Theory,2000,46(2):694-698.

[4]Tan Lin,Qi Wenfeng.Linear complexity and k-error linear complexity for2mpn-periodic binary sequences[J].Journal on Communication,2008,29(7):44-49.

[5]Zhou Jianqin.On the 3-error linear complexity of2n-periodic binary sequences with linear complexity2n[J].Acta MathematicaeApplicatae Sinica,2013,36(3):399-413.

[6]Fu Fangwei,Niederreiter H,Su Ming.The characterization of2n-periodic binary sequences with fixed 1-error linear complexity[C]//LNCS 4086:Proceedings of the 4th International Conference on Sequences and Their Applications,Beijing,China,Sep 24-28,2006.Berlin,Heidelberg:Springer, 2006:88-103.

[7]Etzion T,Kalouptsidis N,Kolokotronis N,et al.Propertics of the error linear complexity spectrum[J].IEEE Transactions on Information Theory,2009,55(10):4681-4686.

[8]Pi Fei,Qi Wenfeng.The 4-error linear complexity of binary periodic sequences[J].Acta Electronica Sinica,2011,39 (12):2914-2920.

[9]Niu Zhihua,Guo Danfeng.New algorithm for computing minerror linear complexity ofpn-periodic binary sequences[J]. Journal of ComputerApplications,2013,33(1):12-14.

[10]Wang Hongcui,Zhou Jianqin.Original sequence counting functions ofpnperiodic sequence 3-error linear complexity[J]. Journal of Hangzhou Dianzi University,2013(6):37-40.

[11]Zhou Jianqin.On the 2-error linear complexity of2n-periodic balanced binary sequences[J].Journal of Suzhou University of Science and Technology:Natural Science Edition,2013, 30(4):1-7.

[12]Zhou Jianqin,Liu Wanquan,Wang Xifeng.Structure analysis on the k-error linear complexity for2n-periodic binary sequence[J/OL].arXiv:1312.6927v2(2014-08-09)[2015-03-11].http://arxiv.org/pdf/1312.6927.pdf.

[13]Games R A,Chan A H.A fast algorithm for determining the complexity of a binary sequence with period2n[J].IEEE Transactions on Information Theory,1983,29(1):144-146.

[14]Zhou Jianqin,Liu Wanquan.On the k-error linear complexity for2n-periodic binary sequences via cube theory[J].arXiv: 1309.1829v1(2013-09-07)[2015-03-11].http://arxiv.org/ pdf/1309.1829.pdf.

[15]Zhou Jianqin,Liu Wanquan.The k-error linear complexity distribution for2n-periodic binary sequences[J].Designs, Codes and Cryptography,2014,73(1):55-75.

[16]Meidl W.On the stablity of2n-periodic binary sequences[J]. IEEE Transactions on Information Theory,2005,51(3): 1151-1155.

[17]Rueppel R A.Analysis and design of stream ciphers[M]. Berlin:Springer-Verlag,1986.

[18]Zhou Jianqin,Dai Xiaoping.On the stable k-error linear complexity of periodic sequences[J].Journal on Communication,2011,32(11A):213-220.

[19]Zhu Fengxiang,Qi Wenfeng The 2-error linear complexity of 2n-periodic binary sequences with linear complexity2n-1[J]. Journal of Electronics,2007,24(3):390-395.

[20]Zhou Jianqin,Ouyang Kongli.On k-error linear complexity ofpn-periodic sequences overGF(q)[J].Journal of Jishou University:Natural Science Edition,2013,34(6):41-46.

附中文參考文獻(xiàn)：

[4]譚林,戚文峰.2mpn周期二元序列的線性復(fù)雜度和k錯(cuò)線性復(fù)雜度[J].通信學(xué)報(bào),2008,29(7):44-49.

[5]周建欽.具有2n線性復(fù)雜度的2n周期二元序列的3錯(cuò)線性復(fù)雜度[J].應(yīng)用數(shù)學(xué)學(xué)報(bào),2013,36(3):399-413.

[8]皮飛,戚文峰.二元周期序列的4-錯(cuò)線性復(fù)雜度[J].電子學(xué)報(bào),2011,39(12):2914-2920.

[9]牛志華，郭丹峰.計(jì)算pn周期二元序列的最小錯(cuò)線性復(fù)雜度新算法[J].計(jì)算機(jī)應(yīng)用,2013,33(1):12-14．

[10]王洪翠,周建欽.pn周期序列3錯(cuò)線性復(fù)雜度原序列計(jì)數(shù)公式[J].杭州電子科技大學(xué)學(xué)報(bào),2013(6):37-40.

[11]周建欽.2n周期平衡二元序列的2錯(cuò)線性復(fù)雜度[J].蘇州科技學(xué)院學(xué)報(bào):自然科學(xué)版,2013,30(4):1-7.

[18]周建欽,戴小平.具有穩(wěn)定k錯(cuò)線性復(fù)雜度的周期序列[J].通信學(xué)報(bào),2011,32(11A):213-220.

[20]周建欽,歐陽孔禮.GF(q)上pn-周期序列的k錯(cuò)線性復(fù)雜度[J].吉首大學(xué)學(xué)報(bào):自然科學(xué)版,2013,34(6):41-46.

WANG Xifeng was born in 1980.She is a lecturer at Anhui University of Technology.Her research interests include communication,information security and cryptography,etc.

王喜鳳（1980—），女，山東成武人，碩士，安徽工業(yè)大學(xué)講師，主要研究領(lǐng)域?yàn)橥ㄐ牛畔踩?，密碼學(xué)等。

ZHANG Wei was born in 1989.He is an M.S.candidate at Anhui University of Technology.His research interests include information security and cryptography,etc.

張偉（1989—），男，安徽合肥人，安徽工業(yè)大學(xué)碩士研究生，主要研究領(lǐng)域?yàn)樾畔踩?，密碼學(xué)等。

ZHOU Jianqin was born in 1963.He received the M.S.degree from Fudan University in 1989.Now he is a professor at Anhui University of Technology.His research interests include communication,information security and cryptography,etc.

周建欽（1963—），男，山東巨野人，1989年于復(fù)旦大學(xué)獲得碩士學(xué)位，現(xiàn)為安徽工業(yè)大學(xué)教授，主要研究領(lǐng)域?yàn)橥ㄐ?，信息安全，密碼學(xué)等。

*The National Natural Science Foundation of China under Grant No.61300059(國家自然科學(xué)基金);the Natural Science Foundation of Anhui Province under Grant No.1208085MF106(安徽省自然科學(xué)基金);the Natural Science Research Project of Anhui Colleges under Grant No.KJ2013Z025(安徽省教育廳自然科學(xué)研究項(xiàng)目);the Youth Foundation Project of Anhui University of Technology under Grant No.QZ201412(安徽工業(yè)大學(xué)青年基金項(xiàng)目).

Received 2015-04,Accepted 2015-09.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2015-10-14,http://www.cnki.net/kcms/detail/11.5602.TP.20151014.1722.002.html

+Corresponding author:E-mail:waynezh89@163.com

文獻(xiàn)標(biāo)志碼：A

中圖分類號(hào)：TN918.1

doi:10.3778/j.issn.1673-9418.1504035

2n-Periodic Binary Sequences with 6-Error Linear Complexity as the Second Descent Point?

WANG Xifeng,ZHANG Wei+,ZHOU Jianqin
Computer Science and Technology School,Anhui University of Technology,Ma’anshan,Anhui 243002,China

Abstract:The linear complexity and the k-error linear complexity are important indicators to measure the strength of stream ciphers,and the higher of those two indicators could resistance the plaintext attack than others,generally. In order to research the sequence of stream cipher,this paper uses a structural approach and cube theory in investigating the 2n-periodic binary sequences with 6-error linear complexity as the second descent point,and gets all the possible value forms of 6-error linear complexity.This paper analyzes and derives the complete counting functions of 2n-periodic binary sequences with the given first descent point 2-error linear complexity and second descent point 6-error linear complexity.With the method proposed in this paper,other second or third descent point of the k-error linear complexity for 2n-periodic binary sequences can be obtained.

Key words:periodic sequence;linear complexity;k-error linear complexity;cube theory