Simplifying algebraic attacks with univariate analysis
Tor Helleseth, Sondre Rønjom · 2011
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.