Strategic attack on the shrinking generator

The shrinking generator is a simple keystream generator with applications in stream ciphers, which is still considered as a secure generator. This work shows that, in order to cryptanalyze it, fewer intercepted bits than indicated by the linear complexity are necessary. Indeed, whereas the linear complexity of shrunken sequences is between A⋅2^(S−2)$A\cdot 2^{(S-2)}$ and A⋅2^(S−1)$A\cdot 2^{(S-1)}$, we claim that the initial states of both component registers are easily computed with fewer than A⋅S$A\cdot S$ shrunken bits located at particular positions. Such a result is proven thanks to the definition of shrunken sequences as interleaved sequences. Consequently, it is conjectured that this statement can be extended to all interleaved sequences. Furthermore, this paper confirms that certain bits of the interleaved sequences have a greater strategic importance than others, which must be considered as a proof of weakness of interleaved generators.