Abstract:
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.