Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 2 / 12K / Solution

The unicity distance is the ciphertext length at which the key is uniquely determined, or equivalently at which key equivocation vanishes:For Shannon's idealized calculation, assume a uniformly chosen key independent of an iid plaintext source, deterministic invertible encryption for each key, and uniformly distributed ciphertext over an alphabet $\Sigma$. Since $M^n$ is determined by $(C^n,K)$,Setting this to zero givesEquivalently, each ciphertext symbol supplies the source redundancy $\log |\Sigma |-H$ bits toward identifying the key.

For the stated cipher, the original formula uses $k_{i\mathrm{mod}3}$, so $|K|=2^3=8$, while $|\Sigma |=3$. Split first according to whether $m=0$. This event and its complement each have probability $1/2$, and conditional on $m\ne 0$ the probabilities are $(2p,1-2p)$. HenceIf $U\ge 20$, thenso, using ${\log }_2(3)=1.585$,Therefore

Binary entropy is symmetric about probability $1/2$ and increases up to that point. Since equality holds at $2p=0.30$, it also holds at $2p=0.70$. Thusand all requested values are

Finally let $p=0$, so the source is uniform on $\{0,2\}$. Use one uniform key bit $k$ and encrypt each symbol byThus the second key swaps $0$ and $2$. Every ciphertext has two possible plaintexts, a binary string and its complement, with equal source probability. No amount of ciphertext distinguishes the keys: $H(K\mid C^n)=1$ for every $n$. This cipher has infinite unicity distance.

Solved by gpt-5.6-sol high.