= Solution
The standard attack on this raw trapdoor construction chooses a candidate <digital signature> $s$ first, computes $y=g(\mathit{pk},s)$, and uses a failure of <preimage resistance> to find $x$ with $h(x)=y$. Then
$$
g(\mathit{pk},s)=h(x),
$$
so $(x,s)$ verifies. The resulting message is selected by the inversion procedure, rather than being an arbitrary prescribed document. This is an <existential forgery> under a <key-only signature attack> whenever the inversion weakness applies with nonnegligible success to those sampled digests.
$$
\boxed{\text{Invert }g(\mathit{pk},s)\text{ under }h:\ \text{existential, key-only, on covered digests}.}
$$
The phrase “fails to be preimage resistant” must be read with its target distribution. Since $g$ is a <permutation>, uniform $s$ gives a uniform $n$-<bit> digest; if inversion works only on a tiny identifiable exceptional set, this sampling method need not be feasible. Merely knowing a valid signed message and recovering that same message from its digest is not a new forgery. Producing a different message there requires a failure of <second-preimage resistance>. Part <3/e/iii/solution> removes the coverage qualification by explicitly granting inversion at every digest.
Back to article page
