×

Keystream sequences with a good linear complexity profile for every starting point. (English) Zbl 0734.94010

Advances in cryptology - EUROCRYPT ’89, Proc. Workshop, Houthalen/Belg. 1989, Lect. Notes Comput. Sci. 434, 523-532 (1990).
[For the entire collection see Zbl 0719.00028.]
For a positive integer \(n\) and a sequence \(S\) of elements \(s_ 1,s_ 2,\ldots\) of a field \(F\), the (local) linear complexity \(L_ n(S)\) is defined as the least \(k\) such that \(s_ 1,s_ 2,\ldots,s_ n\) form the first \(n\) terms of a \(k\)th-order linear feedback shift register (LFSR) sequence. Here the zero sequence \(0,0,\ldots\) is viewed as an LFSR sequence of order \(0\). The sequence \(L_ 1(S),L_ 2(S),\ldots\) of integers is called the linear complexity profile (LCP) of \(S\). The LCP is of interest in stream ciphers, where it is one of the requirements that the LCP of a keystream sequence should simulate the LCP of a random sequence. The paper studies a related requirement, namely that a keystream sequence should have an acceptable LCP for every starting point. In other words, if \(S_ m\) is the unified sequence \(s_{m+1},s_{m+2},\ldots\), then \(S_ m\) should have an acceptable LCP for every \(m=0,1,\ldots\).
First, some probabilistic results on the LCP of \(S_ m\) are shown in the case where \(F\) is a finite field. Then \(S\) is defined to have a good LCP if \(L_ n(S)=(n/2)+O(\log n)\), and it is proved that if \(S\) has a good LCP, then every shifted sequence \(S_ m\) has a good LCP. We say that \(S\) has a uniformly good LCP if \(L_ n(S_ m)=(n/2)+O(\log n)\) with an implied constant independent of \(m\). It is demonstrated that this property occurs with probability \(0\), and it is left as an open question whether there actually exists a sequence with a uniformly good LCP. A basic ingredient of the proofs is the connection between the LCP of \(S\) and the continued fraction expansion of the generating function of \(S\). Several auxiliary results are devoted to continued fractions for formal Laurent series over \(F\).

MSC:

94A60 Cryptography
94A55 Shift register sequences and sequences over finite alphabets in information and communication theory

Citations:

Zbl 0719.00028
Full Text: DOI