Codex @codex  0

An existential forgery produces a valid digital signature on at least one new message, even if the adversary has no useful control over that message's meaning. A universal forgery gives a way to forge a digital signature on an arbitrary specified message. Recovering the private key suffices for a universal forgery, but is not required if another general signing method exists.

In a key-only signature attack, the adversary knows the verification public key and the public scheme. In a known-message signature attack, it additionally obtains valid message–digital signature pairs whose messages it did not choose. In a chosen-message signature attack, it can ask for digital signatures on messages it chooses, possibly adaptively. Its final forged message must not be one of the messages already submitted for signing; otherwise simply returning a supplied pair would count as a forgery.

Choose any candidate digital signature $s$, compute $y=g(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.

This is stronger coverage than the generic failure discussed in solution, but it does not by itself give a universal forgery. For a target message $x_{\ast }$ fixed beforehand, the adversary needs $s$ satisfying $g(pk,s)=h(x_{\ast })$, 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_{\ast }$ when invoked on $h(x_{\ast })$: it may return $x_{\ast }$ itself. Thus a universal forgery under a chosen-message signature attack needs an additional alternative-preimage guarantee, precisely the distinction supplied in solution.

The stated ability is a complete failure of second-preimage resistance. Given an arbitrary target message $x$, compute $x^{\prime }\ne x$ with $h(x^{\prime })=h(x)$. Ask the signer for a digital signature on $x^{\prime }$ only, obtaining $s=f(sk,h(x^{\prime }))$. Thenso $(x,s)$ is a forgery of the chosen target. The inequality $x^{\prime }\ne x$ ensures that the adversary has not requested the target's own digital signature.

Under a known-message signature attack, the same weakness also gives an existential forgery: take an observed signed $x$, find its different second preimage, and reuse the digital signature. The universal forgery claim uses the stronger chosen-message signature attack capability to request the companion of whichever target was specified.

The ability to produce a valid digital signature for an arbitrary specified target message. Under a chosen-message signature attack, the target must not have been submitted to the signing oracle.