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.