**Authors:** Ran Canetti, Daniele Micciancio and Omer
Reingold

Proceedings of the 30th Annual ACM Symposium on Theory of Computing - STOC 1998. May 23-26, Dallas, Texas. pp. 131-140.

**Abstract:** Probabilistic hash functions that hide all
partial information on their input were recently introduced. This new
cryptographic primitive can be regarded as a function that offers "perfect
one-wayness", in the following sense: Having access to the function value on
some input is equivalent to having access only to an oracle that answers
"yes" if the correct input is queried, and answers "no" otherwise.
Constructions of this primitive (originally called oracle hashing and here
re-named *perfectly one-way functions*) were given based on certain
strong variants of the Diffie-Hellman assumption. In this work we present
several constructions of perfectly one-way functions; some constructions are
based on claw-free permutation, and others are based on any one-way
permutation. One of our constructions is simple and efficient to the point of
being attractive from a practical point of view.