Tech Report: HPL-1999-128R1: Computing the Error Linear

Lauder, Alan ; Paterson, Kenneth

HP Development Company

关键词: cryptography;    stream cipher;    error linear complexity spectrum;    algorithm;    decoding;    Reed-Muller code;   

RP-ID  :  HPL-1999-128R1

学科分类：计算机科学（综合）

美国|英语

来源: HP Labs

【 摘 要 】

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