OWF ⇒ DS

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

Statement

If one-way functions exist, there is an EUF-CMA-unforgeable signature scheme — Rom90. Rompel constructs universal one-way hash functions (UOWHFs) from any one-way function, and UOWHFs give signatures through the tree-based scheme of NY89.

Sketch

A UOWHF compresses messages for a one-time signature, and a tree of fresh one-time keys, each authenticated by its parent (Naor–Yung), turns one-time signatures into a many-time EUF-CMA scheme.

Notes

• Conversely, perfectly correct signatures imply one-way functions (DS ⇒ OWF) — Rom90.
• Signatures from one-to-one one-way functions, via UOWHFs, predate Rompel’s result — NY89.
• Rompel’s STOC paper gives the proof only in outline; the first complete proof is KK05.