周期序列线性复杂度与-错复杂度的数学期望
On the Expected Value of the Linear Complexity and the k-Error Linear Complexity of Periodic Sequences
-
摘要: 密码学意义上强的序列不仅应该具有足够高的线性复杂度,而且当少量比特发生改变时不会引起线性复杂度的急剧下降,即具有高的-错复杂度.该文以多项式的因式分解为主要工具研究了任意有限域GF(q)上,周期N与p互素以及N=v这两种情况下,计数函数NN,0(c)的值,并给出了线性复杂度的数学期望EN,0的值以及-错复杂度的数学期望EN,的一个有用的下界,这里p是有限域GF(q)的特征.
-
关键词:
- 流密码;周期序列;线性复杂度;-错复杂度
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. -
计量
- 文章访问数: 2378
- HTML全文浏览量: 127
- PDF下载量: 779
- 被引次数: 0
下载:
