周期序列復(fù)雜度的分布.pdf

1、流密碼學(xué)是一個(gè)古典的課題.近十年來(lái)，對(duì)序列密碼的研究一直比較熱門.自90年代以來(lái)，國(guó)內(nèi)的學(xué)者如丁存生，肖國(guó)鎮(zhèn)，魏仕民，戴宗鐸開展了這方面的研究工作，丁存生的主要工作包括對(duì)特定周期序列的模式分布的研究，肖國(guó)鎮(zhèn)老師的工作主要是針對(duì)特定周期序列如N=2pv周期的周期序列的線性復(fù)雜度快速算法的研究，魏仕民的工作包括對(duì)特定周期的周期序列的k錯(cuò)線性復(fù)雜度快速算法的研究；戴宗鐸老師的工作包括對(duì)周期序列的擾動(dòng)(如添加，刪除)后序列線性復(fù)雜度的變化情況，

2、以及一般情形下的隨機(jī)周期序列的線性復(fù)雜度的期望，方差. 國(guó)外學(xué)者Niederreiter很早就開始了有關(guān)序列復(fù)雜度的研究工作，對(duì)于特定長(zhǎng)度的，特定周期的序列的線性復(fù)雜度有很多的估計(jì)結(jié)果，尤其是給出了周期序列的線性復(fù)雜度的分布，線性復(fù)雜度與k錯(cuò)線性復(fù)雜度之間的關(guān)系；Meidl對(duì)于隨機(jī)周期序列的k錯(cuò)線性復(fù)雜度的統(tǒng)計(jì)性質(zhì)，包括期望的界有了很多的研究結(jié)果.在研究周期序列線性復(fù)雜度，k錯(cuò)線性復(fù)雜度快速算法方面，早期的工作包括Games和C

3、hsq，1983)的工作，對(duì)于N=2v的周期序列給出了一種快速算法，大大優(yōu)于原先的Berlekamp-Massey算法.接著M.StampandC.F.Martin提出了N=2v的周期序列k錯(cuò)線性復(fù)雜度的算法，于是后面引發(fā)了一系列的研究，通過(guò)探詢內(nèi)在的代數(shù)結(jié)構(gòu)，找到遞歸算法的依據(jù)，現(xiàn)在對(duì)于N=2n，N=pb，N=2pv的周期序列都有了類似的快速計(jì)算的方法.此外，還有一些其他的工作，比如K.Kurosawa,F.Sato，T.Sakata

4、,和W.Kishimoto的工作，得到了在特定周期N=2v，pv的周期序列的線性復(fù)雜度發(fā)生最小跳變的錯(cuò)誤值.比如Alan.G.B.LauderandKenneth.G.Paterson的工作，給出一種高效算法得到二元周期序列線性復(fù)雜度的錯(cuò)誤譜并用于Reed-Muller碼的譯碼中. 說(shuō)到這里，要談一談對(duì)研究序列的性質(zhì)的原始動(dòng)機(jī).筆者對(duì)序列的興趣并不是從密碼學(xué)意義角度來(lái)的.當(dāng)時(shí)筆者2002年在微軟亞洲研究院實(shí)習(xí)的時(shí)候，碰到了一個(gè)問

5、題：有一個(gè)研究小組用極長(zhǎng)序列(MaximalLengthSequence)折疊后來(lái)進(jìn)行定位，直觀的說(shuō)，因?yàn)闃O長(zhǎng)序列的冗余很大，這樣做可以用比較少的比特來(lái)實(shí)現(xiàn)定位.但是有這么一個(gè)問題，如果出錯(cuò)了怎樣解決?筆者試圖從編碼理論的角度解決這樣的問題，但是沒有想到這個(gè)問題的難度會(huì)很大，這涉及到序列的穩(wěn)定性的問題.國(guó)外曾經(jīng)有這樣的工作，試圖從線性復(fù)雜度的圖象變化來(lái)進(jìn)行判斷，這種線性復(fù)雜度的躍遷或者是幅度的變化可以給錯(cuò)誤提供一定的判斷信息，從而進(jìn)行糾

6、錯(cuò).這樣的問題引發(fā)了筆者的思考，究竟序列的穩(wěn)定性是怎么進(jìn)行度量和判斷的?興趣引起了對(duì)序列復(fù)雜度性質(zhì)的研究.于是發(fā)現(xiàn)國(guó)內(nèi)國(guó)外有一些這方面的研究工作，特別是對(duì)序列線性復(fù)雜度和k錯(cuò)線性復(fù)雜度的研究. 筆者博士論文中主要的研究工作是對(duì)周期序列線性復(fù)雜度和k錯(cuò)線性復(fù)雜度按照不同的周期類別進(jìn)行了近一步的細(xì)劃，對(duì)隨機(jī)周期序列的線性復(fù)雜度和k錯(cuò)線性復(fù)雜度的統(tǒng)計(jì)性質(zhì)，包括期望，方差的界的一些估計(jì)有一些更緊的結(jié)果.另外還有一些多重序列方面的研究工作

7、.此外，對(duì)于周期為2n的二元隨機(jī)周期序列的k=1，2-錯(cuò)線性復(fù)雜度進(jìn)行了深入的研究，給出了精確的數(shù)學(xué)公式描述分布的規(guī)律；并給出了周期為2n的二元周期序列的1-錯(cuò)線性復(fù)雜度的新算法，另外還在得到了二元隨機(jī)周期序列的線性復(fù)雜度為固定值時(shí)，內(nèi)在結(jié)構(gòu)的一些性質(zhì)基礎(chǔ)之上，提出了新算法去定位這些可能發(fā)生錯(cuò)誤的位置. 事實(shí)上這樣的研究是還是非常的理論的，試圖從序列本身固有的定量的東西(如周期，長(zhǎng)度，錯(cuò)誤值，有限域的元素?cái)?shù)目，分圓陪集的結(jié)構(gòu))來(lái)

8、揭示序列的線性復(fù)雜度和k錯(cuò)線性復(fù)雜度的統(tǒng)計(jì)性質(zhì)，這樣的研究結(jié)果會(huì)很定量而且很深刻；但是這樣的結(jié)果畢竟是太理論了一些；如果能夠參與到一些與數(shù)字版權(quán)相關(guān)的，與安全工程相關(guān)的實(shí)際項(xiàng)目中，會(huì)對(duì)實(shí)際的應(yīng)用背景和要求會(huì)有更深的理解.筆者有幸能夠到微軟亞洲研究院，IBM中國(guó)研究中心參與這樣的一些項(xiàng)目，包括數(shù)字版權(quán)管理，安全存儲(chǔ)，數(shù)字水印的應(yīng)用項(xiàng)目.從中收獲也非常大. 這篇博士論文的結(jié)構(gòu)是這樣的：第一章主要是介紹序列各種復(fù)雜度的基本概念和近幾年

9、國(guó)內(nèi)外對(duì)序列復(fù)雜度研究的方法和進(jìn)展；第二章主要是介紹自己在周期序列線性復(fù)雜度和k錯(cuò)線性復(fù)雜度方面所做的一些研究工作和結(jié)果，以及未來(lái)工作的展望；第三章主要是介紹自己在周期為2n的隨機(jī)周期序列1-錯(cuò)線性復(fù)雜度和2-錯(cuò)線性復(fù)雜度分布及算法方面所做的最新的研究工作；第四章主要是介紹自己在微軟亞洲研究院，IBM中國(guó)研究中心所參與的一些與數(shù)字版權(quán)管理(DRM)相關(guān)的項(xiàng)目和所做的研究工作.最后是附錄，介紹自己獨(dú)立設(shè)計(jì)的周期為2n的周期序列1-錯(cuò)線性復(fù)