Digital Signatures and Public-Key Infrastructure

Let $\mathsf{coll}$ be the event that the forged $m$ satisfies $H^s(m) = H^s(m')$ for some queried $m'$. Then $\Pr[\text{forge}]\le\Pr[\mathsf{coll}] + \Pr[\text{forge}\wedge\neg\mathsf{coll}]$.

• Collision finder $C(s)$: generate $(pk,sk)$ itself, answer signing queries honestly, and output $(m,m_i)$ if they collide. Its success is $\Pr[\mathsf{coll}]$, which is negligible.
• Forger $\mathcal A(pk)$ for $\Pi$: generate $s$ itself, answer query $m_i$ by asking its own oracle for $\mathrm{Sign}_{sk}(H^s(m_i))$, and output $(H^s(m),\sigma)$. Under $\neg\mathsf{coll}$, $H^s(m)$ was never queried, so this is a $\Pi$-forgery.

Both terms are negligible. The same proof works for one-time signatures and gives variable-length MACs too (though Chapter 4 got those without CRHFs).

∎

A forgery on $m\ne m'$ must reveal a preimage at some cell $(i,b)$ with $m_i = b\ne m'_i$, one the signature on $m'$ never revealed. The inverter $I(y)$:

1. pick random $(i^*,b^*)$ and set $y_{i^*,b^*} := y$; generate all other cells honestly;
2. answer the query $m'$ honestly, aborting if $m'_{i^*} = b^*$ (that cell is unknown);
3. if the forgery is “at” $(i^*,b^*)$, output its $i^*$-th component.

Mental experiment: give $I$ the preimage too, so it never aborts. $\mathcal A$’s view is then identical to the real game and independent of $(i^*,b^*)$, so a forgery lands at the planted cell with probability at least $\varepsilon/2\ell$. The real experiment differs only when $m'_{i^*} = b^*$, and then a forgery at $(i^*,b^*)$ is impossible anyway. So $\Pr[\mathrm{Invert}]\ge\varepsilon/2\ell$, and $\varepsilon$ is negligible.

∎

With $\ell^*$ signing queries, at most $\ell = 2n\ell^* + 1$ one-time keys are ever used (each query creates at most $2n$; plus the root). The one-time forger $\mathcal A$ plants its challenge $pk$ at a random position $i^*\in[\ell]$ in the order keys are created, generates the rest itself, and answers queries using its own secret keys, plus its single one-time query for the planted key. Given a forgery from $\mathcal A^*$:

• Case 1: the forged path departs from the real tree. At the first $j$ where the claimed children $pk'_{m|_j0}\Vert pk'_{m|_j1}$ differ from the real ones, $\sigma'_{m|_j}$ is a one-time forgery under $pk_{m|_j}$ (which signed only the true children).
• Case 2: the path matches all the way, so $\sigma'_m$ forges a fresh message under leaf key $pk_m$, which signed nothing.

Either way the forged key is the planted one with probability exactly $1/\ell$ (independent of $\mathcal A^*$‘s view), so the one-time advantage is $\varepsilon/\ell$, and $\varepsilon$ is negligible.

∎

Warm-up (no signing queries): answer one random hash query out of $q$ with the RSA challenge $y^*$ and the rest with random values. A forgery $(m,\sigma)$ on that query gives $\sigma = (y^*)^{1/e}$: success $\varepsilon/q$.

With signing queries (WLOG: no repeated hash queries; every signed or forged $m$ was hashed first): $\mathcal A'(N,e,y^*)$ guesses $j\leftarrow[q]$.

• Hash query $i\ne j$: pick $\sigma_i\leftarrow\mathbb Z_N^*$, answer $y_i = \sigma_i^e\bmod N$, store $(m_i,\sigma_i,y_i)$. Since $x\mapsto x^e$ is a permutation, $y_i$ is uniform: a perfect simulation.
• Hash query $j$: answer $y^*$.
• Signing query on $m_i$: return the stored $\sigma_i$, which is valid ($\sigma_i^e = H(m_i)$) without knowing $d$. If $i = j$, abort.
• Output $\sigma$ if the forgery is on $m_j$.

When the guess is right, $\mathcal A$‘s view is exactly the real game, and $j$ is independent of that view until $\mathcal A$ asks to sign $m_j$, which already means the guess is wrong (it can’t then forge on $m_j$). So $\Pr[\text{RSA solved}] = \varepsilon/q$. (Coron improved the loss to about the number of signing queries; PSS gives a tight reduction and is in PKCS #1 v2.1.)

∎