Perfect Secrecy in Cryptography

Introduction

If you want to know what perfect secrecy means in cryptography, then you are at the right place. This blog will discuss perfect secrecy with mathematical expressions and examples.

But first, let's talk about cryptography in brief.

Cryptography

Cryptography is one of the subjects in computer science that focus on secure communication between the sender and receiver and also discusses the methods we can use to secure digital data like digital signature uploaded on the internet.

With cryptography, we do not need to worry about the confidentiality and integrity of the data during transmission.

You need to know a few terms we will frequently use during the explanation.

• Plaintext: The normal text we will convert into a non-readable format.
   
• Ciphertext: The text we will generate after converting the plain text by applying cryptography techniques.
   
• Key: A key is a string of characters or bits that helps us convert plain text into cipher text and is only known to the sender and receiver.
   
• Encryption: Encryption converts plain text into cipher text with the help of a secret key.
   
• Decryption: Decryption converts cipher text into normal or plain text with the help of a secret key.
   

Now let's get started with perfect secrecy.

Perfect Secrecy

Perfect secrecy in cryptography means that no computational power can guess or obtain any information about the plain text or secret keys from encrypted or cipher text. Let's say the attacker has information about the encrypted text or ciphertext. Still, he cannot get any information from the ciphertext to generate the plaintext, which is called perfect secrecy.
 

Claude Shannon first proposed the term perfect secrecy in 1946. Claude Shannon introduced a theorem known as Shannon's theory which defines perfect secrecy and how we can achieve it. 

According to Shannon's theorem

Pr( M =m | C =c) = Pr(M =m)

In the above expression, M stands for the given message space, which contains the message text like M = { m0,m1, m2, m3…mn} and C stands for the Ciphestext space, which contains the ciphertext. The ciphertext will be generated with the keys taken from the Keyspace K =  { k0,k1, k2…kn}. 
 

The above expression represents that if the probability of a message space with message m1 with a given cipher text space with cipher text c1 is equal to the probability of the message space with message m1, it is perfect secrecy.
 

In simple terms, you calculated the probability of Pr( M =mi | C =ci), and the result is as same.

Things you should keep in mind when applying Shannon's theorem.

• Every key in keyspace will be used with an equal probability of 1/k.
• The key will be unique for every plain text and cipher text.
• The keyspace should be at least the same as the size of the message space.
   

Let's understand this theorem with an example

Let,

Message space M = {0,1,2}

Key Space K = {0,1,2,3}.

The key will be selected uniformly from the key space.

 

Encryption will be Encr(K, M) = (k+m mod 3) = c

Decryption will be Decr(K, M) = (c-k mod 3)

 

Here, k is the key from space, m is the message from message space, and c is the cipher text from cipher space.
 

After applying the encryption technique, we will get the following result

Cipher text	0	1	2
0	0	1	2
1	1	2	3
2	2	0	1
3	0	1	2

We will get the result we have collected in the form of a matrix. The message is in the purple column, and in the pink column, it is the key.
 

Let's apply the Shannon theorem for M = 0 and C = 0.  

This means we need to prove Pr( M = 0 | C =0 ) = Pr( M = 0).
 

Now before we do the calculation, you need to know that

Pr( M = m | C = c) = ( Pr(C= c | M = m) * Pr(M =m) ) / Pr(C = c) by Bayes Law.  

 

If the result of the above expression is equal to Pr( M = 0), we have achieved perfect secrecy.

Now we have M = 0 and C = 0 this means

Pr( M = 0 | C = 0 ) = ( Pr( C = 0 | M = 0) * Pr( M = 0) ) / Pr(C = 0).

 

We need to calculate the probability of each term mentioned in the expression one by one.

Pr( M = 0 ) = 1/3.

Now for Pr( C = 0)  = Pr(K =1)*Pr(M = 2) + Pr(K = 2)*Pr(M = 1) + Pr(K = 0)* Pr(M = 3) + Pr(K= 3)*Pr( M = 3) 

 

Pr( C = 0 ) = 4 * 1/3* 1/4 = 1/3.

 

Now for Pr( C = 0 | M = 0) = Pr( K = 1) + Pr(K = 3) = 1/4 + 1/4 = 1/2.

As we can see in the table, C = 0 can be achieved with M = 0 only if K = 1 or K = 3.

 

Let's add all the results in Pr( M = 0 | C =0 ) = ( Pr( C = 0 | M = 0) * Pr( M = 0) ) / Pr(C = 0).

 = (1/2 * 1/3 ) / 1/3

= 1/2.

Pr( M = 0 | C =0 ) = 1/2 and Pr( M = 0) = ⅓ which are not equal.

The above result means that perfect secrecy using these encryption or key spaces cannot be achieved because our cipher text gives some information.

Is there a technique available that has achieved perfect secrecy? The answer is yes.

One-time Pad

The one-time pad is a technique that has achieved perfect secrecy and cannot break. In a one-time pad, we convert the message bit by bit using the shared secret key into the ciphertext using an encryption algorithm.

 But there are some conditions you need to know or follow to implement the one-time pad.

• The key must be at least long as the size of the plaintext.
   
• You must not use the key as a whole or in part. You will use the key bit by bit to convert the plaintext into ciphertext.
   
• The most important thing is that the key you choose must be completely random and not follow any familiar pattern. 
   
• The key should be uniform and independent from the plaintext.
   

Example

Plain text = NINJA

Key = WSDEX

Here size(plaintext) = size(Key)

Now let's convert the character of plaintext and key into numbers equivalent to 0-25.

N I N J A = 13 8 13 9 0

W S D E X = 22 18 3 4 23

Now we perform the addition of each number uniformly and perform mod 26 to each number.

13 8 13 9 0

+

22 18 3 4 23
 

35 26 16 13 23 mod 26

 

Result = 9 0 16 13 23

Convert it into characters
 

Cipher text = H A O L V 

As you can see, we cannot get any information about the plaintext from the generated cipher text. You only need to remember that the receiver and sender should maintain the key.