周期序列線性復(fù)雜度與-錯復(fù)雜度的數(shù)學(xué)期望
On the Expected Value of the Linear Complexity and the k-Error Linear Complexity of Periodic Sequences
-
摘要: 密碼學(xué)意義上強的序列不僅應(yīng)該具有足夠高的線性復(fù)雜度,而且當(dāng)少量比特發(fā)生改變時不會引起線性復(fù)雜度的急劇下降,即具有高的-錯復(fù)雜度.該文以多項式的因式分解為主要工具研究了任意有限域GF(q)上,周期N與p互素以及N=v這兩種情況下,計數(shù)函數(shù)NN,0(c)的值,并給出了線性復(fù)雜度的數(shù)學(xué)期望EN,0的值以及-錯復(fù)雜度的數(shù)學(xué)期望EN,的一個有用的下界,這里p是有限域GF(q)的特征.
-
關(guān)鍵詞:
- 流密碼;周期序列;線性復(fù)雜度;-錯復(fù)雜度
Abstract: Cryptographically strong sequences not only should have a large linear com-plexity, but also no a significant decrease of the linear complexity when a few terms are changed. This requirement leads to the concept of the /c-error linear complexity of periodic sequences. In the following two cases: (1) gcd(N,p) = 1; (2) N= pv, where p denotes the characteristic of the finite field GF(q), the counting function NN,o(c), i.e., the number of N-periodic sequences with given linear complexity c, is showed, the expected value of the linear complexity En,o is determined, and a useful lower bound on the expected value of the k-errov linear complexity EN, is established. -
Ding C, Xiao G, Shan W. The stability theory of stream ciphers. Lecture Notes in Computer Science. Vol.561, Berlin: Springer-Verlag, 1991.[2]Stamp M, Martin C F. An algorithm for the k-error linear complexity of binary sequences of period 2n. IEEE Trans. on Information Theory, 1993, IT-39(4): 1398-1401.[3]Kaida T, Uehara S, Imamura K. A new algorithm for the k-error linear complexity of sequences over GF(pm) with period pn. In Sequences and Their Applications. Ding C, Helleseth T, Niederreiter H. Eds. London, U. K.: Springer, 1999: 284-296.[4]Rueppel R A.Analysis and Design of Stream Ciphers. Berlin: Springer-Verlag, 1986.[5]Meidl W, Niederreiter H. On the expected value of the linear complexity and the k-error linear complexity of periodic sequences. IEEE Trans. on Information Theory, 2002, IT-48(11): 2817-2825.[6]Wei S, Zhang Y, Xiao G. Distribution of linear complexity for periodic sequences. CrypTEC99,Hong Kong, July 1999: 250-253. -
計量
- 文章訪問數(shù): 2434
- HTML全文瀏覽量: 143
- PDF下載量: 781
- 被引次數(shù): 0
下載:
