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 mMm \in M and kKk \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(kc(n))=0H\left(k \mid c^{(n)}\right)=0. Derive the formula

U=logKlogΣ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=1HlogΣR=1-\frac{H}{\log |\Sigma|}. If a language has zero redundancy what is the unicity of any cryptosystem?