Powers of Subfield Polynomials and Algebraic Attacks on Word-Based Stream Ciphers.
Sondre Rønjom · 2015
Abstract. In this paper we investigate univariate algebraic attacks on filter generators over extension fields Fq = F2n with focus on the Welch-Gong (WG) family of stream ciphers. Our main contribution is to break WG-5, WG-7, WG-8 and WG-16 by combining results on the so-called spectral immunity (minimum distance of certain cyclic codes) with prop-erties of the WG type stream cipher construction. The spectral immunity is the univariate analog of algebraic immunity and instead of measuring degree of multiples of a multivariate polynomial, it measures the mini-mum number of nonzero coecients of a multiple of a univariate polyno-mial. Based on the structure of the general WG-construction, we deduce better bounds for the spectral immunity and the univariate analog of algebraic attacks. 1