This contributions contains a brief overview of methods used for the recovery of the initial state of a linear feedback shift register from a noisy version of the output sequence. Among others a probabilistic recovery algorithm is described where it is assumed that the length of the observed output sequence is close to the unicity distance which is the theoretical lower bound on the average length when recovery is still possible. The presented algorithm makes use of information set decoding of a random linear code. A deterministic algorithm with the same asymptotical complexity is also presented.

Back to Workshop Schedule