= Solution
For encrypt-then-authenticate, choose any $n$-<bit> string $s$ and compute
$$
c=g(\mathit{pk},s).
$$
Send $(c,s)$. The receiver's correct check for this composition is $g(\mathit{pk},s)=c$ before <decryption>, so it passes by construction. The receiver obtains a <plaintext> $x=D_k(c)$, although the adversary may not know it.
The finite domains justify the signature relation: $g\circ f$ is the identity on $2^n$ messages, so $f$ is injective and therefore bijective. Hence $g=f^{-1}$ and also $f\circ g$ is the identity. The chosen $s$ is therefore exactly $f(\mathit{sk},c)$, without the adversary ever evaluating $f$.
$$
\boxed{(g(\mathit{pk},s),s)\text{ is an existential forgery.}}
$$
This is a <key-only signature attack> against raw unrestricted trapdoor signing. It does not invert $g$ at a chosen target and does not contradict the assumption that signing an independently specified new message is hard. It exploits choosing the <digital signature> first. The observation concerns the paper's raw construction, rather than every encrypt-then-authenticate scheme.
Back to article page
