What is Perfect Secrecy?

You might have heard the term “perfect secrecy” while learning some cipher examples such as Caesar’s cipher, simple substitution cipher, one-time pad and Vigenère cipher. One-time pad is one of the example encryption methods that has perfect secrecy. But what does perfect secrecy mean and what does it mean to have perfect secrecy for an encryption method?

Perfect secrecy is a term coined by Claude Shannon in his paper “Communication Theory of Secrecy Systems” in 1949 (which was actually written by Shannon in 1945 and was a classified report until 1949). In the paper, this is how Shannon defines perfect secrecy:

“Perfect Secrecy” is defined by requiring of a system that after a cryptogram is intercepted by the enemy the a posteriori probabilities of this cryptogram representing various messages be identically the same as the a priori probabilities of the same messages before the interception.

In other words,  having the cipher text should not give the attacker any advantage on recovering the plaintext. To put it another way, the ciphertext should not give any information on the plaintext.

Consider the ciphertext 0d788da1e7a7eedfe035c95c which was produced by XOR’ing the plaintext and the key (one-time pad). Since you have no other information on the plaintext, the possibility of the message is “attack at dawn” (with the key as 6c0cf9c084cc8fab8454be32) and the message is “attack at dusk” (with the key as 6c0cf9c084cc8fab8440ba37) are exactly the same: 1/2^{96} (12-byte message and the key). In fact, this is true for every possible plaintext. This shows that one-time pad has perfect secrecy.

(Note that the key space and the message space for this example was chosen in \{0,1\}^{96}, this is one of the requirements of the perfect secrecy.)

 

Leave a comment

search previous next tag category expand menu location phone mail time cart zoom edit close