**A new statistical distinguisher for the shrinking generator**

*Jovan Dj. Golic and Renato Menicocci*

**Abstract: **The shrinking generator is a well-known keystream generator composed
of two linear feedback shift registers, LFSR$_1$ and LFSR$_2$, where
LFSR$_1$ is clock-controlled according to regularly clocked LFSR$_2$.
The keystream sequence is thus a decimated LFSR$_1$ sequence.
Statistical distinguishers for keystream generators are algorithms whose objective is to distinguish the
keystream sequence from a purely random sequence.
Previously proposed statistical distinguishers for the shrinking generator
are based on detecting binary linear relations in the keystream sequence that hold
with a probability sufficiently different from one half.
In this paper a novel approach which significantly reduces the required computation time is introduced.
It is based on a probabilistic reconstruction of the bits in the regularly
clocked LFSR$_1$ sequence that satisfy the LFSR$_1$ recurrence
or any linear recurrence derived from
low-weight multiples of the LFSR$_1$ characteristic polynomial.
The keystream sequence length and the computation time required for a reliable statistical distinction
are analyzed both theoretically and experimentally.

**Category / Keywords: **secret-key cryptography / cryptanalysis, stream ciphers

**Date: **received 3 Mar 2003

**Contact author: **golic at inwind it

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

**Version: **20030303:215141 (All versions of this report)

**Short URL: **ia.cr/2003/041

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]