Shannon's Perfect and Imperfect Secrecy Theorems
Let \(X,Y,Z\) be the plaintext, ciphertext and symmetric key respectively. For a symmetric encryption scheme we would want the following
- Perfect secrecy: \(I(X;Y)=0\)
- Dechiperability: \(H(X|Y,Z)=0\)
The perfect secrecy theorem states that for the conditions above to hold, we need \(H(Z)\geq H(X)\) i.e. the length of the key is at least the same as the length of the plaintext.
The imperfect secrecy theorem states that the decipherability constraint \(H(X|Y,Z)=0\) implies \(I(X;Y)\geq H(X)-H(Z)\). Here, \(I(X;Y)\) can be viewed as a quantification of information leakage, and if it is 0, it reduces to the perfect secrecy theorem.