**Finding Low Weight Polynomial Multiples Using Lattices**

*Laila El Aimani and Joachim von zur Gathen*

**Abstract: **The low weight polynomial multiple problem arises in the context of stream ciphers
cryptanalysis and of efficient finite field arithmetic, and is believed to be difficult. It can be formulated as follows: given
a polynomial $f \in \F_2[X]$ of degree $d$, and a bound $n$, the task is to find a low weight multiple of
$f$ of degree at most $n$. The best algorithm known so far to
solve this problem is based on a time memory trade-off and runs in time
${\cal O}(n^{ \lceil {(w - 1)}/{2} \rceil})$ using ${\cal O}(n^{ \lceil
{(w - 1)}/{4} \rceil})$ of memory, where $w$ is the estimated minimal weight.
In this paper, we propose a new technique to find low weight multiples using
lattice basis reduction. Our algorithm runs in time ${\cal O}(n^6)$ and uses
${\cal O}(nd)$ of memory. This improves the space needed and
gives a better theoretical time estimate when
$w \geq 12$ . Such a situation is plausible when the bound $n$, which represents the
available keystream, is small.
We run our experiments using the NTL library on some known polynomials in
cryptanalysis and we confirm our analysis.

**Category / Keywords: **stream ciphers analysis, low weight polynomial multiples, lattices, shortest vector.

**Publication Info: **stream ciphers analysis, low weight polynmial multiples, lattices, shortest vector

**Date: **received 11 Nov 2007, last revised 17 Aug 2009

**Contact author: **elaimani at bit uni-bonn de

**Available format(s): **PDF | BibTeX Citation

**Version: **20090817:085850 (All versions of this report)

**Short URL: **ia.cr/2007/423

[ Cryptology ePrint archive ]