Abstract:
The generalized knapsack problem is the following: given $m$ random elements $a_1,\ldots,a_m\in R$ for some ring $R$, and a target $t\in R$, find elements $z_1,\ldots,z_m\in D$ such that $\sum{a_iz_i}=t$ where $D$ is some given subset of $R$. In (Micciancio, FOCS 2002), it was proved that for appropriate choices of $R$ and $D$, solving the generalized compact knapsack problem \emph{on the average} is as hard as solving certain \emph{worst-case} problems for cyclic lattices even for almost constant values of $m$. This immediately yields very efficient one-way functions whose security is based on worst-case hardness assumptions. A problem left open in (Micciancio, FOCS 2002) is whether these functions satisfy stronger security guarantees, such as collision resistance. We show that the function proposed in (Micciancio, 2002) is not collision resistant, but it can be easily modified to achieve collision resistance under essentially the same complexity assumptions on cyclic lattices. Our modified function is obtained as a special case of a more general result, which yields efficient collision resistant hash functions that are at least hard to break as solving the worst case instance of various new problems. These include new problems from algebraic number theory, as well as classic lattice problems (e.g., the shortest vector problem) over {\em ideal lattices}, a new class of lattices that includes cyclic lattices as a special case.