Welcome to the resource topic for 2003/041
Title:
A new statistical distinguisher for the shrinking generator
Authors: Jovan Dj. Golic, 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.
ePrint: https://eprint.iacr.org/2003/041
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .