周期序列復雜度的分布.pdf

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

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

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

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

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

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

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

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

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