Paper 3, Section I, 3G3 G

Coding and Cryptography | Part II, 2016

Describe in words the unicity distance of a cryptosystem.

Denote the cryptosystem by ⟨M,K,C⟩\langle M, K, C\rangle, in the usual way, and let m∈Mm \in M and k∈Kk \in K be random variables and c=e(m,k)c=e(m, k). The unicity distance UU is formally defined to be the least n>0n>0 such that H(k∣c(n))=0H\left(k \mid c^{(n)}\right)=0. Derive the formula

U=log⁡∣K∣log⁡∣Σ∣−HU=\frac{\log |K|}{\log |\Sigma|-H}

where H=H(m)H=H(m), and Σ\Sigma is the alphabet of the ciphertext. Make clear any assumptions you make.

The redundancy of a language is given by R=1−Hlog⁡∣Σ∣R=1-\frac{H}{\log |\Sigma|}. If a language has zero redundancy what is the unicity of any cryptosystem?

Typos? Please submit corrections to this page on GitHub.