Next: Property Testing in Bounded
Up: Sabbatical at MIT (1996-1998)
Previous: On Universal Learning Algorithms
This work provides a survey of Ajtai's construction of one-way functions
based on the assumption that certain approximation problems in lattices
are difficuly in the worst-case.
It is also shown that essentially the same construction
can be used to obtain collision-free hashing.
Comments:
Authored by O. Goldreich, S. Goldwasser and S. Halevi. Appeared in
ECCC, TR95-042, 1996.
Oded Goldreich
2003-07-30