Perfectly one-way probabilistic hash functions

Abstract

Probabilistic hash functions that hide all partial information on their input were recently introduced. This new crypto-graphic 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.