= Solution
Choose any candidate <digital signature> $s$, compute $y=g(\mathit{pk},s)$, and invoke the granted algorithm to find $x$ with $h(x)=y$. Output $(x,s)$. Every chosen $s$ now leads to a valid message, with no need to search for a digest on which inversion happens to work.
$$
\boxed{\text{Every-digest inversion gives an existential forgery under key-only attack.}}
$$
This is stronger coverage than the generic failure discussed in <3/e/i/solution>, but it does not by itself give a <universal forgery>. For a target message $x_*$ fixed beforehand, the adversary needs $s$ satisfying $g(\mathit{pk},s)=h(x_*)$, which inverts the trapdoor map $g$. Inverting $h$ instead produces some message for a chosen digest and does not compute that $s$.
Nor does an arbitrary preimage algorithm necessarily produce a message different from $x_*$ when invoked on $h(x_*)$: it may return $x_*$ itself. Thus a <universal forgery> under a <chosen-message signature attack> needs an additional alternative-preimage guarantee, precisely the distinction supplied in <3/e/iv/solution>.
Back to article page
