TR05-158 Authors: Chris Peikert, Alon Rosen

Publication: 19th December 2005 11:47

Downloads: 3262

Keywords:

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.