UOWHF + One-time signature ⇒ DS (Naor–Yung)

Fully-black-box reduction · standard model · NY89 · security loss: a factor polynomial in the number of signing queries and the tree depth, from guessing where the forgery departs from the signer’s tree

Statement

A universal one-way hash function family and a one-time signature scheme for messages of fixed length together yield an EUF-CMA-unforgeable signature scheme — NY89.

Sketch

A one-time key signs a long message $m$ by signing $(k,{\mathsf{H}}_k(m))$ for a fresh key $k$, which the signer samples only after $m$ is fixed, so a forgery on a different message with the same $(k,{\mathsf{H}}_k(m))$ is a target collision. Many-time signatures authenticate a tree of one-time keys, each node signing the hash of its children’s verification keys; a forgery either forges a one-time signature at some node or finds a target collision there, and the reduction guesses which — Gol04.

Notes

• With collision-resistant instead of universal one-way hashing, the key can be fixed in advance: CRHF + One-time signature ⇒ DS — Mer89.
• Both ingredients follow from one-way functions (OWF ⇒ UOWHF, OWF ⇒ one-time signatures), giving OWF ⇒ DS — Rom90.