Question

Explain the mathematical proof that One time pad (OTP) is perfectly secure under Ciphertext Only attack (COH).

Answer 1

The OTP is an encryption technique that cannot be cracked, but it requires the use of a one-time pre-shared key the same size as, or longer than, the message being sent. In this technique, a plain text is paired with a random secret key. Then, each bit or character of the plain text is encrypted by combining it with the corresponding bit from the pad using modular addition.
The resulting ciphertext are going to be impossible to decrypt or break if the subsequent given below four conditions are met:

1. The Key must be truly random.
2. The Key must be a minimum of as long because the plaintext.
3. The Key must not be ever reused in whole or partially
4. The key must be kept completely secret.

It has also proven that any cipher with the property of perfect secrecy must use keys with effectively the same requirements as OTP keys. Digital version of one-time pad cipher are employed by nation for critical diplomatic and military communication, but the issues of secure key distribution have made them impractical for many applications.

Example:

Suppose Joy wishes to send the message "HELLO" to Roy. Assume two pad of paper containing identical random sequences of the letters were previously produced and securely issued to both of them. Joy chooses the appropriate unused page from the pads. The way to do this, normally arranged for in advance, as for instance "use the next available sheet for the next message".

The material that is on the selected sheet is the key for the message. Each letter from the pad will be combined in a predetermined way. (It is commonly used way, but not required, to assign each letter a numerical value, "A" is 0, "B" is 1, "C" is 3 and so on.)

The technique to combine the key and the message using modular addition. The numerical values of corresponding message and key letters are added together, modulo 26. So, if key material begins with "XMCKL" and the message is "HELLO", then the coding be done as follows:

   H       E       L       L       O → (message)
   7 (H)   4 (E)  11 (L)  11 (L)  14 (O) → (message)
+ 23 (X)  12 (M)   2 (C)  10 (K)  11 (L) → (key)
= 30      16      13      21      25   →  (message + key)
=  4 (E)  16 (Q)  13 (N)  21 (V)  25 (Z) → (message + key) mod 26
      E       Q       N       V       Z  → (ciphertext)

If number is larger than 25, then the remainder after subtraction of 26 is taken in modular arithmetic fashion. This means that if the computations "go past" of Z, the sequence starts again from A.

The ciphertext to be sent to Roy is thus "EQNVZ". Roy use the matching key page and the same process, but in reverse, to obtain plain text(message sent by joy will be decrypted). Here the key is subtracted from the ciphertext, again using modular arithmetic fashion:

       E       Q       N       V       Z → (ciphertext)
    4 (E)  16 (Q)  13 (N)  21 (V)  25 (Z) → (ciphertext)
-  23 (X)  12 (M)   2 (C)  10 (K)  11 (L) → (key)
= -19       4      11      11      14   → (ciphertext – key)
=   7 (H)   4 (E)  11 (L)  11 (L)  14 (O) → (ciphertext – key) mod 26
       H       E       L       L       O  → (message)

from the above, if a number is negative, then 26 is added to make the number zero or higher.

Thus Roy recovers Joy's plain text, the message "HELLO". Both Joy and Roy destroy the key sheet immediately after use, thus preventing reuse and attack against the cipher.

Mathematical Proof:

Claude Shannon proved, that the one-time pad has a property he termed perfect secrecy; that is, the ciphertext C gives absolutely no additional information about the plain text. This is because, given a truly random key that is used only once for the message and than destroyed, a ciphertext can be translated into any plain text of the same length, and all are equal. Thus, the priori probability of a plaintext message M is the same as the a posteriori probability of a plaintext message M given the ciphertext.

Mathematically, this is expressed as H(M)=H(M|C) , where H(M) is the information entropy of the plaintext and H(M|C) is the conditional entropy of the plaintext for the given ciphertext C.  Η is the capital Greek letter eta. This implies that for every message M and its corresponding ciphertext C, there must be at least one key K that will bind them as a one-time pad. Mathematically, this means , where K,C,M are the distinct quantity of key, cipher and message

Another way of saying that perfect secrecy is based on the idea that for all messages m1,m2 in message space M, and for all ciphers c in cipher space C, we have

where Pr represents the probabilities, taken over a choice k in key space K over the coin tosses of a probabilistic algorithm, E. Perfect secrecy is a strong notion of the cryptanalytic difficulty.