OWF ⇒ One-time signatures (Lamport)

Fully-black-box reduction · standard model · Lam79 · security loss: a factor 2ℓ, from guessing which of the 2ℓ key slots the forgery opens

Statement

If $\mathsf{H}$ is a one-way function, Lamport’s scheme on $\ell$-bit messages is a one-time signature: EUF-CMA-unforgeable against all efficient adversaries making at most one signing query. The signing key is $2\ell$ uniform preimages $x_{i,b}$, the verification key is their images $y_{i,b}=\mathsf{H}(k,x_{i,b})$, and the signature on $m$ reveals $(x_{i,m_i}{)}_{i\le \ell }$ — Lam79.

Sketch

A forgery on $\hat{m}\ne m$ reveals a preimage of some $y_{i,1-m_i}$ that the signature on $m$ did not open. The reduction plants its one-wayness challenge at a uniformly random one of the $2\ell$ slots, aborts if the signing query opens it, answers that query with the preimages it holds, and inverts $\mathsf{H}(k,\cdot )$ whenever the forgery opens it — a factor-$2\ell$ loss.

\begin{algorithm}
\algname{Algorithm}
\caption{$\KeyGen(1^\secpar)$}
\begin{algorithmic}
\State $k \getsr \calK$
\For{$i = 1, \dots, \ell$ and $b \in \bits$}
\State $x_{i,b} \getsr \calD$; $y_{i,b} \gets \hash(k, x_{i,b})$
\EndFor
\Return $(\sk, \vk) := \big((x_{i,b})_{i,b},\ (k, (y_{i,b})_{i,b})\big)$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\algname{Algorithm}
\caption{$\Sign(\sk, m \in \bits^\ell)$}
\begin{algorithmic}
\Return $\sigma := (x_{1,m_1}, \dots, x_{\ell,m_\ell})$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\algname{Algorithm}
\caption{$\Vrfy(\vk, m, \sigma)$}
\begin{algorithmic}
\Return $[\hash(k, \sigma_i) = y_{i,m_i} \text{ for all } i \in \{1,\dots,\ell\}]$
\end{algorithmic}
\end{algorithm}

Notes

• The Winternitz variant signs several message bits per hash chain, trading $\mathsf{H}$ evaluations for signature size — Mer89.
• Efficiency: for $\ell$-bit messages the keys hold $2\ell$ preimages and images and a signature holds $\ell$ preimages; signing evaluates nothing and verification evaluates $\mathsf{H}$ $\ell$ times. Signing a collision-resistant hash of the message makes $\ell =O(\lambda )$ — standard.