**Authors:**
Vadim Lyubashevsky,
Daniele Micciancio

International Colloquium on Automata, Languages and Programming - Proceedings of ICALP 2006, Venice, Italy. Springer LNCS 4052, pp. 144-155 (July 2006)

DOI:10.1007/11787006

[BibTeX]
[Postscript]
[PDF]

**Abstract:**
The generalized knapsack problem is the
following: given *m* random elements *a[1],...,a[m] *in
*R* for some ring *R*, and a target *t* in *R*,
find elements *z[1],...,z[m]* in *D* such that *a[1] z[1] +
... + a[m] z[m] = 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
*on the average* is as hard as solving certain *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 *ideal
lattices*, a new class of lattices that includes cyclic lattices as a
special case.