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.