Paper 2007/423

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.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. stream ciphers analysis, low weight polynmial multiples, lattices, shortest vector
Keywords
stream ciphers analysislow weight polynomial multipleslatticesshortest vector.
Contact author(s)
elaimani @ bit uni-bonn de
History
2009-08-17: last of 3 revisions
2007-11-18: received
See all versions
Short URL
https://ia.cr/2007/423
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2007/423,
      author = {Laila El Aimani and Joachim von zur Gathen},
      title = {Finding Low Weight Polynomial Multiples Using Lattices},
      howpublished = {Cryptology ePrint Archive, Paper 2007/423},
      year = {2007},
      note = {\url{https://eprint.iacr.org/2007/423}},
      url = {https://eprint.iacr.org/2007/423}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.