Abstract: The shrinking generator is a pseudorandom bit generator based on the combination of two linear feedback shift registers of maximum period. These registers are synchronized with a common clock and produce binary sequences with good statistical properties. Due to its simplicity and efficient implementation, the shrinking generator is particularly suitable for stream cipher cryptographic schemes and most proposed attacks rely on the properties of the generator. Furthermore, its analysis serves as the foundation for other interleave constructions. In our work, we present a new algorithm which allows to compute the linear complexity for shrunken sequences in an efficient way together with a closed formula for the linear complexity of its output in certain conditions. Additionally, we establish the first bound on its linear complexity profile and a conjecture about the values of the linear complexity of these sequences. Our techniques involve two-dimensional arrays and their interleave structure, which could prove valuable for other pseudorandom bit generators.

Autoría

Descargar referencia