In this paper we present a new algorithm for the recovery of the initial state of a linear feedback shift register when a noisy output sequence is given. Our work is focussed on the investigation of the asymptotical behaviour of the recovery process rather than on the construction of an optimal recovery procedure. Our results show the importance of low-weight checks and show also that the complexity of the recovery problem grows less than exponentially with the length of the shift register, even if the number of taps grows linearly with the register length. Our procedure works for shift register with arbitrary feedback polynomial.
|Title of host publication||Advances in Cryptology—EUROCRYPT 1991|
|Subtitle of host publication||Workshop on the Theory and Application of Cryptographic Techniques, Proceedings|
|Editors||Donald W. Davies|
|Number of pages||10|
|Publication status||Published - 1991|
|Event||Workshop on the Theory and Application of Cryptographic Techniques, EUROCRYPT 1991 - Brighton, United Kingdom|
Duration: 1991 Apr 8 → 1991 Apr 11
|Name||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Conference||Workshop on the Theory and Application of Cryptographic Techniques, EUROCRYPT 1991|
|Period||1991/04/08 → 1991/04/11|
Bibliographical noteFunding Information:
The first author would like to thank the USSR Academy of Sciences, the Royal Swedish Academy of Sciences, and the Department of Information Theory in Lund for their support and making this work possible.
© Springer-Verlag Berlin Heidelberg 1991.
Subject classification (UKÄ)
- Computer Science
- Control Engineering