TR05-142 Authors: Vadim Lyubashevsky, Daniele Micciancio

Publication: 5th December 2005 01:48

Downloads: 2879

Keywords:

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.