IACR paper details
Title  A new statistical distinguisher for the shrinking generator 

Booktitle  IACR Eprint archive 

Pages  

Year  2003 

URL  http://eprint.iacr.org/2003/041 

Author  Jovan Dj. Golic 

Author  Renato Menicocci 

Abstract 
The shrinking generator is a wellknown keystream generator composed
of two linear feedback shift registers, LFSR$_1$ and LFSR$_2$, where
LFSR$_1$ is clockcontrolled 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
lowweight 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.


Search for the paper
@misc{eprint200311758,
title={A new statistical distinguisher for the shrinking generator},
booktitle={IACR Eprint archive},
keywords={secretkey cryptography / cryptanalysis, stream ciphers},
url={http://eprint.iacr.org/2003/041},
note={ golic@inwind.it 12114 received 3 Mar 2003},
author={Jovan Dj. Golic and Renato Menicocci},
year=2003
}
Download a complete BibTeX file.