CRHF + One-time signature ⇒ DS

Fully-black-box reduction · standard model · Mer89 · security loss: additive: the collision-finding advantage plus $2^h$ times the one-time-signature advantage, from planting the one-time challenge key at a uniformly random one of the $2^h$ leaves

Statement

A collision-resistant hash function and a one-time signature scheme yield a stateful many-time signature scheme: the public key is the root of a Merkle tree over $2^h$ one-time verification keys — a single $O(\lambda )$-bit hash — and the $i$-th signature is a one-time signature under the $i$-th key together with that key and its authentication path of $h$ hashes, so signatures have size $O(h\lambda )$ plus one one-time key and signature — Mer89.

Sketch

The reduction plants the one-time challenge key at a random leaf. A forgery under index $i$ either carries a verification key or authentication path other than the honest ones, and then it and the honest path hash to the same root, giving a collision at some tree node; or it carries the honest ${\mathsf{vk}}_i$ and path, and then its one-time signature, on a message never signed under ${\mathsf{vk}}_i$, is a one-time forgery, against the challenge key when that leaf is $i$.

Notes

• One-time signatures exist from one-way functions (OWF ⇒ One-time signatures (Lamport)) — Lam79.
• Universal one-way (target-collision-resistant) hash functions, obtainable from any one-to-one one-way function, suffice for many-time signatures — NY89.
• Any one-way function suffices for many-time signatures (OWF ⇒ DS) — Rom90.