Computing the Error Linear Complexity Spectrum of a Binary Sequence of Period 2n

Lauder, Alan; Paterson, Kenneth

HPL-1999-128R1

Keyword(s): cryptography; stream cipher; error linear complexity spectrum; algorithm; decoding; Reed-Muller code

Abstract: Please Note. This abstract contains mathematical formulae which cannot be represented here. Binary sequences with high linear complexity are of interest in cryptography. The linear complexity should remain high even when a small number of changes are made to the sequence. The error linear complexity spectrum of a sequence reveals how the linear complexity of the sequence varies as an increasing number of the bits of the sequence are changed. We present an algorithm which computes the error linear complexity for binary sequences of period l=2n using 0 (l(log l)2) bit operations. The algorithm generalises both the Games- Chan and Stamp-Martin algorithms, which compute the linear complexity and the k-error linear complexity of a binary sequence of period l=2n , respectively. We also discuss an application of an extension of our algorithm to decoding a class of linear subcodes of Reed-Muller codes. Notes: Alan Lauder, Junior Research Fellow at Wolfson College, Oxford, OX2 6UD and a member of the Mathematical Institute, Oxford University, Oxford, OX1 3LB, UK

13 Pages

Back to Index