OWF ⇒ UOWHF (Rompel)

Fully-black-box reduction · standard model · Rom90 · security loss: polynomial

Statement

Every one-way function yields a universal one-way hash function family compressing by any polynomial number of bits — Rom90.

Notes

• With UOWHF + one-time signature ⇒ DS and Lamport’s one-time signatures, this gives OWF ⇒ DS — Rom90.
• A complete proof of Rompel’s construction is in KK05. A simpler construction through inaccessible entropy has substantially shorter keys and output — HHR+10.
• For one-way permutations, one evaluation per bit of compression suffices: OWP ⇒ UOWHF — NY89.
• Collision resistance does not follow from one-wayness by any relativizing construction, even from a one-way permutation: No relativizing reduction from OWP to CRHF — Sim98.