Cryptology ePrint Archive: Report 1996/009

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.

Category / Keywords: Complexity, Collision-Free Hashing, Lattice Reduction.

Publication Info: Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive.

Date: received July 26th, 1996.

Contact author: oded at theory lcs mit edu

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

Short URL: ia.cr/1996/009

Discussion forum: Show discussion | Start new discussion