Collision-Free Hashing from Lattice Problems
In 1995, 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. This paper contains a self-contained pr...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Nature
2019
|
| Online Access: | https://hdl.handle.net/1721.1/121244 |
| Summary: | In 1995, 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. This paper contains a self-contained proof sketch of Ajtai's result. Keywords: Integer Lattices, One-EWay Functions, Worst-Case to Average-Case Reductions, Collision-Resistent Hashing |
|---|