Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices
Speaker: Chris Peikert , CIS, CSAIL, MIT
Date: December 2 2005
Time: 10:30AM to 12:00PM
Location: 32-G449, Patil/Kiva, Stata Center, 32 Vassar St.
Contact: Be Blackburn, 3-6098, imbe@mit.edu
Relevant URL:
Collision-resistant hashing is one of the most widely-employed cryptographic primitives. Its applications include integrity checking, user and message authentication, commitment protocols, and more.
In this talk, we will present a very efficient hash function for which finding collisions given a *random* key is at least as hard as approximating the shortest vector (SVP) in a cyclic lattice *in the worst case*. Each evaluation of our function requires only a small number (e.g., 3) of Fast Fourier Transforms. Thus, assuming that SVP is indeed hard for the special case of cyclic lattices, our function is efficient enough to be considered a candidate for practical usage.
Our worst-case to average-case reduction is non-standard, exploiting an intimate connection between the ring algebra of integer polynomials and the linear algebra of cyclic lattices. These new techniques enable us to provide a more efficient and conceptually simpler security reduction than previous ones, and to show tight connections among certain worst-case problems on cyclic lattices.
This is joint work with Alon Rosen.
See other events that are part of
See other events happening in December 2005
