Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR05-158 | 12th December 2005 00:00

Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices



The generalized knapsack function is defined as $f_{\a}(\x) = \sum_i
a_i \cdot x_i$, where $\a = (a_1, \ldots, a_m)$ consists of $m$
elements from some ring $R$, and $\x = (x_1, \ldots, x_m)$ consists
of $m$ coefficients from a specified subset $S \subseteq R$.
Micciancio (FOCS 2002) proposed a specific choice of the ring $R$
and subset $S$ for which inverting this function (for random
$\a,\x$) is at least as hard as solving certain worst-case problems
on cyclic lattices.

We show that for a different choice of $S \subset R$, the
generalized knapsack function is in fact \emph{collision-resistant},
assuming it is infeasible to approximate the shortest vector in
$n$-dimensional cyclic lattices up to factors $\tilde{O}(n)$. For
slightly larger factors, we even get collision-resistance for
\emph{any} $m\geq 2$.
This yields \emph{very} efficient collision-resistant hash
functions having key size and time complexity almost linear in the
security parameter $n$. We also show that altering $S$ is necessary,
in the sense that Micciancio's original function is \emph{not}
collision-resistant (nor even universal one-way).

Our results exploit an intimate connection between the linear
algebra of $n$-dimensional cyclic lattices and the ring
$\mathbb{Z}[\alpha]/(\alpha^n-1)$, and crucially depend on the
factorization of $\alpha^n-1$ into irreducible cyclotomic
polynomials. We also establish a new bound on the discrete Gaussian
distribution over general lattices, employing techniques introduced
by Micciancio and Regev (FOCS 2004) and also used by Micciancio in
his study of compact knapsacks.

ISSN 1433-8092 | Imprint