Simplifying algebraic attacks with univariate analysis

The purpose of this paper is to present a more fine-grained view on cryptanalysis of stream ciphers based on LFSRs in terms of the univariate representation and to provide some connections to cyclic codes. A usual way of presenting such ciphers is in terms of multivariate equations over GF(2). Another way is in terms of the trace-representation of the sequences, but still with respect to GF(2). It is shown that by using the univariate polynomial representation, one gets a much more fine grained picture. Such a view simplifies theory on algebraic attacks on such ciphers and provides an alternative view of the Rønjom-Helleseth attack. With this view, one can show that, 1) the problem of estimating algebraic immunity and spectral immunity is closely connected to determining low-weight codewords in cyclic codes, and 2) the least number of keystream bits needed in an attack is given by Jansen and Boekee´s maximal order complexity. Some general problems are posed with this reformulation.