Perfectly one-way probabilistic hash functions (preliminary version)
Ran Canetti, Daniele Micciancio, Omer Reingold · 1998
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 oneway permutation. One of our constructions is simple and efficient to the point of being attractive from a practical point of view.