Paper 2003/041
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.
Metadata
- Available format(s)
- PS
- Category
- Secret-key cryptography
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- cryptanalysisstream ciphers
- Contact author(s)
- golic @ inwind it
- History
- 2003-03-03: received
- Short URL
- https://ia.cr/2003/041
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2003/041,
author = {Jovan Dj. Golic and Renato Menicocci},
title = {A new statistical distinguisher for the shrinking generator},
howpublished = {Cryptology ePrint Archive, Paper 2003/041},
year = {2003},
note = {\url{https://eprint.iacr.org/2003/041}},
url = {https://eprint.iacr.org/2003/041}
}
