Loughborough University
Browse
ima-mbm-final.pdf (302.03 kB)

Modified Berlekamp-Massey algorithm for approximating the k-error linear complexity of binary sequences

Download (302.03 kB)
online resource
posted on 2008-04-21, 13:23 authored by Alexandra Alecu, Ana SalageanAna Salagean
Some cryptographical applications use pseudorandom sequences and require that the sequences are secure in the sense that they cannot be recovered by only knowing a small amount of consecutive terms. Such sequences should therefore have a large linear complexity and also a large k-error linear complexity. Efficient algorithms for computing the k-error linear complexity of a sequence only exist for sequences of period equal to a power of the characteristic of the field. It is therefore useful to find a general and efficient algorithm to compute a good approximation of the k-error linear complexity. We show that the Berlekamp-Massey Algorithm, which computes the linear complexity of a sequence, can be adapted to approximate the k-error linear complexity profile for a general sequence over a finite field. While the complexity of this algorithm is still exponential, it is considerably more efficient than the exhaustive search.

History

School

  • Science

Department

  • Computer Science

Citation

ALECU, A. and SALAGEAN, A.M., 2007. Modified Berlekamp-Massey algorithm for approximating the k-error linear complexity of binary sequences. IN: S. Galbraith (ed.). Proceedings of the 11-th IMA International conference on Cryptography and coding, Cirencester, UK, December. LNCS 4887. Heidelberg : Springer Verlag, pp. 220-232

Publisher

© Springer Verlag

Publication date

2007

Notes

This conference paper is also available from: http://www.springerlink.com/content/105633/

ISBN

9783540772712

ISSN

0302-9743;1611-3349

Book series

Lecture notes in computer science

Language

  • en