Perfect Secrecy and Entropy

• Perfect Secrecy
  • Examples
  • Proofs of Equivalence
  • Vernam’s Cipher - One Time Pad
• Shannon’s Characterization for Perfect Security
  • Shannon’s Entropy for Encryption
  • Spurious Keys and Unicity Distance
  • Min-Entropy

Claude “Lord” Shannon

Perfect Secrecy

Definition

irrespective of an prior information about $M$, $C$ should leak no additional information on $M$

$\mathrm{Pr}[M_R==M|C_R==C]=\mathrm{Pr}[M_R==M]$

Observing $C$ does not change the attacker’s knowledge about the distribution of $M$

Shannon’s Entropy for Encryption

let $(M,C,K,E,D)$ be an encryption scheme.

$H(K,M,C)=H(C|K,M)+H(K,M)$ and $C$ is obtained deterministically from $K$ and $M$ so $H(K,M,C)=H(K,M)$ and $K$ and $M$ are independent so $H(K,M,C)=H(K)+H(M)$

similarly $H(K,M,C)=H(M|K,C)+H(K,C)$ and $H(K|C)=H(K,C)-H(C)$

substituting in the above thing $H(K|C)=H(K)+H(M)-H(C)$