Collision-Free Hashing from Lattice Problems
Oded Goldreich, Shafi Goldwasser, and Shai Halevi
Abstract: Recently Ajtai described a construction of one-way functions whose security is equivalent to the difficulty of some well known approximation problems in lattices. We show that essentially the same construction can also be used to obtain collision-free hashing.
Keywords: Complexity, Collision-Free Hashing, Lattice Reduction.
comment: received July 26th, 1996. Revised Nov. 19th, 1996.
contact author: oded@theory.lcs.mit.edu
Fetch PostScript file of the full paper.