 Solution

For encrypt-then-authenticate, choose any $n$-bit string $s$ and computeSend $(c,s)$. The receiver's correct check for this composition is $g(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(sk,c)$, without the adversary ever evaluating $f$.

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.