兩類最優(yōu)跳頻序列集的線性復雜度

高軍濤，胡予濮，李雪蓮，向上榮

(1. 西安電子科技大學 計算機網(wǎng)絡與信息安全教育部重點實驗室，陜西 西安 710071；2. 中國科學院 軟件研究所 信息安全國家重點實驗室，北京 100190；3. 西安電子科技大學 應用數(shù)學系，陜西 西安 710071；4. 西安電子科技大學 計算機學院，陜西 西安 710071)

1 引言

跳頻(FH)序列在擴頻通信和碼分多址(CDMA)通信系統(tǒng)中都有廣泛的應用。跳頻碼分多址系統(tǒng)(FH-CDMA)被廣泛地應用于藍牙、雷達系統(tǒng)等方面。在這些系統(tǒng)中，信號接收者面臨的主要問題就是信號之間的相互干擾。針對這種情況，人們一般采用具有低Hamming相關的跳頻序列集來降低干擾，提高系統(tǒng)的性能。除此之外，在實際應用中，特別是在軍用系統(tǒng)中，人們不希望自己傳送的信息被懷有敵意的人獲得或者蓄意干擾。為了抵抗干擾和增加保密性，跳頻序列除了應該具有低的Hamming相關以外，還應該具有較大的線性復雜度[1]。線性復雜度是衡量序列安全性的一個重要指標。如果一個序列的線性復雜度很低，即使它有大的周期，也很容易受到Berlekamp-Massey算法的攻擊，因而序列的使用者就沒有秘密可言。另一方面，為了降低通信收發(fā)雙方的實現(xiàn)復雜度，跳頻序列的實現(xiàn)應該盡量簡單。因此設計實現(xiàn)簡單，低Hamming相關且高線性復雜度的跳頻序列集就具有重要的意義。

當前有許多種類的最優(yōu)跳頻序列集[2～11]，這些跳頻序列集有的是用代數(shù)方法設計的[2～6]，有的則是用組合數(shù)學方法設計的[7～11]。所有這些集合中序列間的Hamming相關滿足Lempel-Greenberger界[12]或 Peng-Fan界[13]。在這些序列集中有些序列的線性復雜度很小[2～4]，有些序列的線性復雜度仍然沒有結論[7～11]，使得這些跳頻序列不能應用于保密通信中[14]。雖然當前存在具有高線性復雜度的最優(yōu)跳頻序列集[5,6]，但這些序列集是通過廣義 Bent函數(shù)或者多項式環(huán)構造的，實現(xiàn)相對比較困難。因此如何將低線性復雜度的最優(yōu)跳頻序列集變換為具有高線性復雜度的最優(yōu)序列集，同時保證序列實現(xiàn)簡單，就成為一個亟待解決的問題。

為了提高跳頻序列的線性復雜度，Ding和Yin[2]指出人們可以使用有限域中的冪置換[15]將一個具有低線性復雜度的跳頻序列集變換為一個具有較高線性復雜度的跳頻序列集。在文獻[16]中，Wang研究了三類最優(yōu)跳頻序列集在冪置換下的線性復雜度，指出這三類序列集中序列的線性復雜度在冪置換下可以大幅增加。Wang同時指出：“除了冪置換以外，其他類型的置換多項式也有可能增加序列的線性復雜度，但計算這些序列線性復雜度的精確值并不容易”。

本文利用有限域中另一類置換多項式δ(x)來提高序列的線性復雜度，通過理論證明給出了置換以后得到的序列線性復雜度的精確值。結果表明，這類置換多項式可以使變換后序列的 Hamming相關保持最優(yōu)，而且還大幅度地增加了序列的線性復雜度。因此證明了Wang提出的命題，即其他類型的置換多項式也可以提高序列的線性復雜度，得到序列線性復雜度的精確值。本文得到的新型跳頻序列集的工程實現(xiàn)是比較簡單的，同時具有高的線性復雜度。與現(xiàn)有的具有大線性復雜度的跳頻序列集[5,6,16]相比，本文的序列具有如下的優(yōu)點：①相比于文獻[5,6]中最優(yōu)跳頻序列集，我們這類序列集的實現(xiàn)更為簡單。②與文獻[16]中冪置換后的最優(yōu)跳頻序列集相比，本文給出的新型最優(yōu)跳頻序列集的實現(xiàn)復雜度與冪置換后序列的實現(xiàn)復雜度相當，而線性復雜度比大部分冪置換給出的序列的線性復雜度要更高，比少數(shù)冪置換給出的序列線性復雜度低。詳細的對比情況參見本文第4節(jié)。

2 基礎知識

2.1 最優(yōu)跳頻序列

設 l是一個正整數(shù)，一個有限集合 F定義為F={f0, f1,…, fl-1}。令長度為 n 的序列 X=x0x1… xn-1，其中xi∈F。長度為n的所有跳頻序列組成的集合記為 S={X| X=x0x1…xn-1，其中 xi∈F}。?X, Y∈S，它們之間的Hamming相關定義如下：

其中，如果xi=yi+t，則h[xi, yi+t]=1；否則h[xi, yi+t]=0。由式(1)集合S中的Hamming相關可以定義如下[1]：

一個跳頻序列的Hamming相關如果滿足式(5)，稱其滿足Lempel-Greenberger界。

引理1[12]對于F上的每一個長度為n的跳頻序列X，其Hamming相關滿足

其中，ε是n模l的最小非負剩余，即ε≡n mod l。

滿足Lempel-Greenberger界的單個序列稱為最優(yōu)跳頻序列。

為了判斷一個跳頻序列集是否達到最優(yōu)，還需要用到引理2。

引理2[13]設S是包含N個長度為n的跳頻序列組成的集合，跳頻序列中分量取自集合F。定義，則

并且

一個跳頻序列集的Hamming相關值如果滿足式(6)或者式(7)，則稱這類序列集滿足Peng-Fan界。滿足Peng-Fan界的跳頻序列集稱為最優(yōu)跳頻序列集。

2.2 序列的線性復雜度

設GF(q)表示含有元素個數(shù)為q的有限域，GF(q)*表示GF(q)中所有的非零元，這里q=pr，p是一個素數(shù)，r≥1是一個正整數(shù)。對于一個元素取自GF(q)上的序列s=s0s1…，其線性復雜度可以定義為產(chǎn)生該序列最短的線性反饋移位寄存器(LFSR)的長度。設序列s由一個LFSR生成，并滿足遞歸關系式：sn+l=cl-1sn+l-1+cl-2sn+l-2+…+ c0sn，n≥0。多項式c(x)=clxl+ cl-1xl-1+…+ c1x+c0稱為序列s的特征多項式。顯然滿足上述遞歸關系的特征多項式有很多，其中具有最低次數(shù)L的特征多項式稱為序列s的最小多項式。序列s的線性復雜度還可以定義為其最小多項式的次數(shù)，記為LS(s)=L。

線性復雜度是衡量序列安全性的一個重要指標。如果一個序列具有較低的線性復雜度，那么序列可以由較短的LFSR來生成，攻擊者利用Berlekamp-Massey算法可以很容易得到生成該序列最短的LFSR長度和它的反饋邏輯，因此，高線性復雜度是序列安全的一個必要條件。從工程角度來說，線性復雜度可以認為是利用LFSR生成序列的困難程度。

3 主要結果

對于一個最優(yōu)跳頻序列或者最優(yōu)跳頻序列集來說，線性復雜度是一個重要的指標。當前存在具有較高線性復雜度的跳頻序列集[5,6]，但這些跳頻序列是通過廣義bent函數(shù)或者多項式環(huán)設計的，在實際應用中實現(xiàn)并不簡單。在文獻[16]中，Wang利用有限域GF(q)上的冪置換：x→xσ，這里x∈GF(q)，gcd(σ, q-1)=1，提高幾類序列的線性復雜度。Wang同時指出“或許”可以利用其他類型的置換多項式來提高序列的線性復雜度，但計算線性復雜度并不像冪置換那么容易。本文利用下面的置換研究兩類最優(yōu)跳頻序列的線性復雜度。

引理3[15]當q為奇數(shù)時，多項式x(q+1)/2+bx∈GF(q)[x]是GF(q)上的一個置換多項式當且僅當b=(c2+1)(c2-1)-1，這里c∈GF(q)，c≠0，c2≠1。

上述引理中的置換多項式和冪置換顯然是不同的。因此給出的具有高線性復雜度的最優(yōu)跳頻序列集是一類新的跳頻序列集。

3.1 第一類跳頻序列集

設p是個奇素數(shù)，q=pr，r是一個正整數(shù)，m≥3是一個奇數(shù)。假設α是GF(qm)*的生成元，n= (qm-1)/2，d是一個整數(shù)滿足gcd(d, qm-1)=1。令β=α2d，?a∈GF(qm)，定義一個序列sa如下：

其中，Tr(x)=x+xq+…+xqm-1是GF(qm)→GF(q)上的跡函數(shù)。文獻[3]已經(jīng)證明：sa是一個((qm-1)/2,(qm-1-1)/2; q)最優(yōu)跳頻序列。{sa, sa’}是一個(( qm-1)/2,2, (qm-1-1)/2; q) 最優(yōu)跳頻序列集，這里a是GF(qm)*中某個元素的平方，而a’不能表示為GF(qm)*中某個元素的平方。文獻[16]證明了這些序列的線性復雜度等于m。相比于序列的周期( qm-1)/2來說，該序列的線性復雜度非常低，下面證明可以利用置換多項式來得到具有大線性復雜度的跳頻序列集。

引理4[17]

引理5[18]設f(x) ∈GF(q)[x]，f(x)在其分裂域上的全部根記為α1，α2，…，αn。序列a=a0a1…以f(x)為特征多項式當且僅當存在一組元素λ1，λ2，…，λn，使得

序列a的線性復雜度等于上式中不等于0的那些λi的個數(shù)。

該引理表明一個序列中的元素可以由序列特征多項式的根來表示，并且序列的線性復雜度也可以由序列根表示的數(shù)目確定。

引理6[19]設f(x) ∈GF(q)[x]，f(x)在其分裂域上無重根。則f(x)可以表示為f(x)= f1(x) f2(x)…fk(x)，k＞0，fi(x)，i=1,2,…k，是GF(q)上不同的不可約多項式。設序列s是以f(x)為極小多項式生成的序列，則序列s可以表示為s=s(1)+s(2)+…+s(k)，其中s(i)是以fi(x)為極小多項式生成的序列。

定理1 設序列sa由式(8)給出，b=(c2+1)(c2-1)-1，這里c∈GF(q)，c≠0，c2≠1。設δ(x)= x(q+1)/2+bx，定義

0≤t≤(qm-1)/2-1則

1) (δ(sa), δ(sa’))組成一個((qm-1)/2, 2, (qm-1-1)/2;q) 最優(yōu)跳頻序列集。

2) δ(sa)的線性復雜度為

證明

定理1中的1)是顯然成立的。因為δ(x)：GF(q)→GF(q)是GF(q)上的置換多項式，所以序列δ(sa)是序列sa的置換序列。根據(jù)式(1)中Hamming相關的定義，δ(sa)滿足引理1中的最優(yōu)界。下面證明定理1中的2)部分。

因為q=pr，(q+1)/2可以表示為

所以

根據(jù)引理4，

所以

根據(jù)引理5，需要給出式(9)中β的系數(shù)模qm-1有多少是互不相同的。對于不同的λi,j，λ′i,j考慮式(10)：

因為λi,j≤ηi，λ'i,j≤ηi并且當q＞3時有：

由式(10)可知，

對于上式把等號兩邊模q得到：

顯然，式(12)等號兩邊的值都是小于q的，所以mod q可以省去。得到λ0,0=λ′0,0, λ1,0=λ′1,0, …,λr-1,0=λ′r-1,0。同理，對式(11)兩端同時模qk, k=2,3, …, m-1, 可以得到 ?i, j, λi,j=λ′i,j，這與λi,j≠λ′i,j矛盾。因此證明了式(9)中β的次數(shù)是互不相同的。

下面證明序列bTr(aβt)中的β的次數(shù)與式(9)中β的次數(shù)是互不相同的。因為

所以，Tr(aβt)中β的次數(shù)形式為qkt。假設存在λi,j使下式成立：

顯然上式左邊和qk都是小于qm-1的，所以mod(qm-1)可以省略。因為所有的0≤λi,j≤ηi，要使得上式成立，必須有λ0k=1且其余的λi,j=0，這就意味著 η0=1，ηi=0， i=1, 2,…, r-1，即(q+1)/2=1。這與p是奇素數(shù)，q是p的冪次矛盾。因此Tr(aβt)(q+1)/2與bTr(aβt)中β的次數(shù)都互不相同。

為了計算δ(sa)的線性復雜度，根據(jù)引理5必須給出δ(sa)的表示中系數(shù)不為0的β的個數(shù)。因為

根據(jù)組合數(shù)公式[17]，共有：

個方式將ηi表示為滿足條件的λi,j的和。

因此，Tr(aβt)(q+1)/2中共含有以下數(shù)目的項：

又因為bTr(aβt)中β的冪次與Tr(aβt)(q+1)/2中的完全不同，由引理6序列δ(sa)的線性復雜度為

從式(13)可以看出，線性復雜度的提高依賴于(q+1)/2的分解。因為q=pr，所以

因此可以確定

當p、r、m 3個參數(shù)固定時，δ(sa)的線性復雜度是固定的，即

顯然，相比于原來的線性復雜度，置換以后的序列線性復雜度有明顯的提高。證畢。

3.2 第二類跳頻序列集

設p是一個素數(shù)，q=pr，r是一個正整數(shù)。設m和d是2個正整數(shù)，滿足d | qm-1，并且gcd((qm-1)/(q-1), d)=1。假設α是GF(qm)*的生成元，β=αμd，μ是一個正整數(shù)滿足gcd(qm-1, μ)=1，設n= (qm-1)/d，對于每一個0≤i≤d-1，可以定義下面的序列：

文獻[2]已經(jīng)證明了由序列

組成的序列族S={si|0≤i≤d-1}是一個((qm-1)/d, d,( qm-1-1)/d; q)最優(yōu)跳頻序列集。

由參數(shù)β，α，d，μ的定義可以看出，式(14)中的序列是式(8)中序列的一種廣義描述。第二類跳頻序列集中要求gcd(qm-1, μ)=1，d | qm-1；而第一類跳頻序列集中gcd(qm-1, d)=1，2 | qm-1；第一類序列可以看作是第二類序列中d=2時的一個特例，因此第二類跳頻序列集可以看作是第一類跳頻序列集的推廣。文獻[16]證明這些序列的線性復雜度等于m。相比于序列的周期來說，該線性復雜度顯然是非常低的。利用的置換多項式δ(x)和第一類序列集同樣的方法，可以改進第二類序列集的線性復雜度，所以有定理2。

定理2 設序列si由式(14)給出，b=(c2+1)(c2-1)-1，這里c∈GF(q)，c≠0，c2≠1。設δ(x)=x(q+1)/2+bx，定義

則

2) δ(sa)的線性復雜度為

定理2的證明與定理1類似，略去。

可以看出，利用置換多項式δ(x)可以將低線性復雜度的最優(yōu)跳頻序列集轉化為高線性復雜度的最優(yōu)跳頻序列集。例如：當p=7，q=73，m=5，在原序列集中線性復雜度僅為5，而經(jīng)過δ(x)=x(q+1)/2+bx置換以后得到的新跳頻序列集的線性復雜度等于85 755，顯然大幅度增加了序列的線性復雜度。

4 比較和實現(xiàn)

本節(jié)主要將本文給出的最優(yōu)跳頻序列集與現(xiàn)有的具有高線性復雜度的最優(yōu)跳頻序列集[5,6,16]從線性復雜度和工程實現(xiàn)2個角度進行對比，說明本文給出的跳頻序列集具有的優(yōu)勢。

由式(8)和式(14)可以看出，置換前的兩類跳頻序列集都可以通過跡函數(shù)來實現(xiàn)。眾所周知，當跡函數(shù)中只包含一個元素的冪次時，其工程實現(xiàn)是非常簡單的。但由于這兩類跳頻序列集的線性復雜度太低，因此只能限制在保密要求很低的環(huán)境中使用。本文置換以后的跳頻序列集，是在原序列集上增加了一個(q+1)/2乘冪次運算(即增加的乘法次數(shù)約為log ((q+1)/2)次)，而后與原序列輸出相加。這種改變僅僅增加了一個簡單的乘法電路和一次加法運算，其中加法運算由于運算量非常小是可以忽略不計的，可見置換以后跳頻序列的工程實現(xiàn)仍然是非常簡單的，以增加非常少量的實現(xiàn)復雜度來獲得較高的線性復雜度是非常值得的。

文獻[5]利用廣義bent序列和廣義bent函數(shù)構造了兩類具有高線性復雜度的最優(yōu)跳頻序列集。其中第一類最優(yōu)跳頻序列集的線性復雜度并不是太高(當周期為p的冪次時，線性復雜度僅為p)，第二類最優(yōu)跳頻序列集的線性復雜度相比于第一類較高。然而因為這兩類序列集都是基于廣義 bent函數(shù)或者廣義bent序列構造的，所以實現(xiàn)是比較復雜的[20]。

文獻[6]的目的也是構造具有高線性復雜度的最優(yōu)跳頻序列集，這種構造主要是基于代數(shù)中的多項式環(huán)理論，相比于文獻[2,3]中利用有限域構造的最優(yōu)跳頻序列集來說，這種基于環(huán)構造的最優(yōu)跳頻序列本身更加的復雜，并且實現(xiàn)也不簡單，但這種構造可以獲得較高的線性復雜度，在保密性要求較高的環(huán)境中可以使用該類跳頻序列集。

文獻[16]是利用冪置換將具有低線性復雜度的最優(yōu)跳頻序列集置換為具有高線性復雜度的最優(yōu)跳頻序列集，其工程實現(xiàn)也相對簡單，僅僅是在原序列上增加一個σ (滿足 gcd(σ, q-1)=1) 的冪次運算，增加的乘法次數(shù)約為log σ次。而本文給出的新型最優(yōu)跳頻序列的實現(xiàn)大約需要增加 log ((q+1)/2)次乘法和一次加法運算。因此本文序列的實現(xiàn)復雜度與文獻[16]中序列的實現(xiàn)復雜度大致相當。在線性復雜度方面，由文獻[16]中的結論，置換后序列線性復雜度的值取決于σ 的 p元表示，而且當σ=pr-pj-1時，序列的線性復雜度取到最大。本文利用置換多項式δ(x)得到置換后跳頻序列線性復雜度的值依賴于(q+1)/2的p元表示，因此有限域給定時，置換后序列的線性復雜度就是給定的。由本文定理1、定理2和文獻[16]中定理5、推論6、定理9、推論 10中的結論可以看出：本文給出的新型最優(yōu)跳頻序列的線性復雜度要小于冪置換σ =pr-pj-1時序列的線性復雜度，但要大于大多數(shù)使用其他冪置換得到的最優(yōu)跳頻序列的線性復雜度。

綜上所述，利用δ(x)可以將兩類低線性復雜度的最優(yōu)跳頻序列集變換為具有高線性復雜度的最優(yōu)跳頻序列集，與現(xiàn)有的具有高線性復雜度的最優(yōu)跳頻序列集相比，增加了非常少的實現(xiàn)復雜度，獲得了較高的線性復雜度。

5 結束語

本文主要證明了Wang給出的命題[16]，即除冪置換以外，其他類型的置換多項式也可以給出具有大線性復雜度，實現(xiàn)相對簡單的最優(yōu)跳頻序列集，并且可以給出置換后序列線性復雜度的精確值。由定理1和定理2的結論可以看出，利用置換多項式δ(x)= x(q+1)/2+bx可以將低線性復雜度的最優(yōu)跳頻序列集轉化為具有高線性復雜度，實現(xiàn)簡單的最優(yōu)跳頻序列集。通過計算序列表示中α不同冪次的數(shù)目，給出了這些序列線性復雜度的精確值。本文利用的置換δ(x)與文獻[16]中使用的冪置換顯然是不同的，因此得到的是新型的最優(yōu)跳頻序列集。

[1] SIMON M K, OMURA J K, SCHOLZ R A, et al. Spread Spectrum Communications Handbook[M]. New York: McGraw-Hill, 2002.

[2] DING C, YIN J. Sets of optimal frequency-hopping sequences[J].IEEE Transactions on Information Theory, 2008, 54(8): 3741-3745.

[3] DING C, MOISIO M J, YUAN J. Algebraic constructions of optimal frequency-hopping sequences[J]. IEEE Transactions on Information Theory, 2007, 53(7): 2606-2610.

[4] DING C, FUJI-HARA R, FUJIWARAY et al. Sets of frequency hopping sequences: bounds and optimal constructions[J]. IEEE Transactions on Information Theory,2009, 55(7):3297-3304.

[5] KUMAR P V. Frequency-hopping code sequence designs having large linear span[J]. IEEE Transactions on Information Theory, 1988, 34(1):146-151.

[6] UDAYA P, SIDDIQI M U. Optimal large linear complexity frequency hopping patterns derived from polynomial residue class rings[J]. IEEE Transactions on Information Theory, 1998, 44(4): 1492-1503.

[7] CAO Z, GE G, MIAO Y. Combinatorial characterizations of one-coincidence frequency- hopping sequences[J]. Design Codes and Cryptography, 2006, 41(2): 177-184.

[8] CHU W, COLBOURN C J. Optimal frequency-hopping sequences via cyclotomy[J]. IEEE Transactions on Information Theory, 2005, 51(3):1139-1141.

[9] GE G, FUJI-HARA R, MIAO Y. Further combinatorial constructions for optimal frequency hopping sequences[J]. Journal of Combinatorial Theory Ser A, 2006, 113: 1699-1718.

[10] GE G, MIAO Y, YAO Z. Optimal frequency hopping sequences: autoand cross-correlation properties[J]. IEEE Transactions on Information Theory, 2009, 55(2): 867- 879.

[11] FUJI-HARA R, MIAO Y, MISHMA M. Optimal frequency hopping sequences: a combinatorial approach[J]. IEEE Transactions on Information Theory, 2004, 50(10): 2408- 2420.

[12] LEMPEL A, GREENBERGER H. Families of sequences with optimal Hamming correlation properties[J]. IEEE Transactions on Information Theory, 1974, 20(1): 90-94.

[13] PENG D, FAN P. Lower bounds on the Hamming auto- and crosscorrelations of frequency-hopping sequences[J]. IEEE Transactions on Information Theory, 2004, 50(9): 2149-2154.

[14] BERLEKAMP E. Algebraic Coding Theory[M]. New York: McGraw-Hill, 1968.

[15] LIDL R, NIEDERRERTER H. Finite Fields[M]. London: Addison-Wesley, 1983.

[16] WANG Q. Optimal sets of frequency hopping sequences with large linear spans[J]. IEEE Transactions on Information Theory, 2010, 56(4):1729-1736.

[17] BOGRART K, STEIN C, DRYSDALE R L. Discrete Mathematics for Computer Science[M]. College Publishing, 2005.

[18] 李超, 屈龍江. 密碼學講義[M]. 科學出版社, 2010.CHAO L, QU L J. Lectures on Cryptology[M]. Science Press, 2010.

[19] GOLOMB S W, GUANG G. Signal design for Good Correlation, for Wireless Communication, Cryptography, and Radar[M]. Cambridge Univ Press, 2005.

[20] 胡予濮, 張玉清, 肖國鎮(zhèn). 對稱密碼學[M]. 北京：機械工業(yè)出版社,2002.HU Y P, ZHANG Y Q, XIAO G Z. Symmetric Key Cryptography[M].Beijing: China Machine Press, 2002.