Past exam of the computer science course of the University of Oxford / 2015 / Computer security / 3 / e / i

The standard attack on this raw trapdoor construction chooses a candidate digital signature $s$ first, computes $y=g(pk,s)$, and uses a failure of preimage resistance to find $x$ with $h(x)=y$. Thenso $(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.

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 solution removes the coverage qualification by explicitly granting inversion at every digest.