= Solution
For authenticate-then-encrypt, write the intercepted pair as $(c,t)=(E_k(x),E_k(s))$, where $s=f(\mathit{sk},x)$. Each trial key $k'$ gives
$$
x'=D_{k'}(c),\qquad s'=D_{k'}(t).
$$
The adversary can check the public relation
$$
\boxed{g(\mathit{pk},s')\stackrel{?}=x'.}
$$
The true key always passes. An incorrect key will generally fail, and further intercepted pairs can eliminate accidental matches. This gives a <ciphertext-only attack> with a useful key-testing predicate even when the <plaintext> has no recognisable format. It makes <exhaustive key search> applicable with less prior information; it does not reduce the generic key-space size below $2^m$.
The usual approximate false-pass chance $2^{-n}$ is an ideal-behaviour estimate, not a consequence of the bare permutation identities alone. The decisive point is that the encrypted <digital signature> supplies publicly checkable redundancy once a candidate <decryption> key is tried.
Back to article page
