Past exam of the mathematics course of the University of Cambridge / 2020 / ii / Paper 4 / 3I (Coding and Cryptography)

A cipher has perfect secrecy when the conditional probability of every plaintext given a ciphertext equals its prior probability: $\mathrm{Pr}(M=m\mid C=c)=\mathrm{Pr}(M=m)$ whenever $\mathrm{Pr}(C=c)>0$. Equivalently, the plaintext and ciphertext are independent random variables.

Fix a ciphertext $c$ that can occur. Perfect secrecy requires every possible plaintext $m$ to remain possible after observing $c$. For a deterministic decryption rule, two different plaintexts producing $c$ require two different keys, so the key space has cardinality at least that of the message space.

In a one-time pad, the message and key belong to the same finite additive group, the key is uniform and independent of the message, and encryption is $C=M+K$. For every $m,c$ there is exactly one key $k=c-m$, soindependent of $m$. Bayes theorem then gives $\mathrm{Pr}(M=m\mid C=c)=\mathrm{Pr}(M=m)$, proving perfect secrecy.

Perform every addition in the finite field ${\mathbb{F}}_2$. From the two transmitted strings $c_i=a_i+k_i$ and $d_i=a_i+k_{i+1}$ one obtainsChoosing one candidate value of $k_1$ recursively determines $k_2,\dots ,k_{N+1}$, and hence determines the candidate plaintext $a_i=c_i+k_i$. There are only two candidates: changing $k_1$ complements every recovered key bit and every plaintext bit. The information that the message makes sense normally selects the intended candidate.

Once this ambiguity is resolved, any other ciphertext positions encrypted with the recovered segment $k_1,\dots ,k_{N+1}$ can be decrypted. Key bits outside that segment remain independent and uniformly distributed, so this mistake gives no information about messages using only those bits. This is the two-time pad attack: reusing related one-time-pad key material destroys perfect secrecy.