Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR05-142 | 1st December 2005 00:00

Generalized Compact Knapsacks are Collision Resistant


Authors: Vadim Lyubashevsky, Daniele Micciancio
Publication: 5th December 2005 01:48
Downloads: 3720


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.

ISSN 1433-8092 | Imprint