CryptoDB
Joachim von zur Gathen
Affiliation: B-IT, University of Bonn
Publications
Year
Venue
Title
2007
EPRINT
Finding Low Weight Polynomial Multiples Using Lattices
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(n-d)^5)$ and uses
${\cal O}(nd)$ of memory. This improves the space needed and
gives a better theoretical time estimate when
$w \geq 12$ or when the \textit{excess degree} $n-d$ is small, say, $(n-d)^5 < n^{\lceil
{(w-3)}/{2} \rceil}$. The former situation is plausible when the bound $n$, which represents the
available keystream, is small, whereas the latter one occurs in efficient finite field arithmetic.
We also propose bounds for the minimal weight
of such multiples, supplying in this sense the state-of-the art techniques with a
method to check whether their estimated minimal weight is in the correct
range. This provides a quantitative cryptographic quality criterion for such
polynomials: the fewer low degree low weight multiples a polynomial has, the
harder becomes this type of cryptanalysis of the corresponding stream
cipher. As an example, the Bluetooth polynomial turns out to be of good
quality in this sense.
Moreover, we introduce the corresponding number problem and apply
a similar strategy to find sparse multiples of a given number with respect to the
Hamming weight of their 2-ary representation. Finally, we run our experiments using the NTL library on some known polynomials in
cryptanalysis and we confirm our analysis.\\
\textbf{Keywords: } stream ciphers analysis, low weight polynomial multiples,
lattices, shortest vector.
Coauthors
- Laila El Aimani (1)
- Michael Nöcker (1)