Perfect Secrecy & One Time Pad

Prof. Ashok K Bhateja, IIT Delhi

2
Security Evaluation Models
 Unconditional security
 Cryptographic system is secure against all attacks, assuming adversary
have unlimited computational resources.
 Provable security
 if it can be shown that the analysis of the system is essentially as
difficult as solving a well-known difficult problem.
 Computational security or Practical security
 if the computation required to crack the system, using the best-known
attack exceeds, by a comfortable margin, the computational resources
of the hypothesized adversary.
i.e., Cost of best-known attack exceeds adversary power

AK Bhateja IIT Delhi

3 A priori and A posteriori Probabilities

 P(X = m): A priori probability of a plaintext.

 P(Z = k): A priori probability of the key.
 Let c = Ek (m), i.e., cipher text generated by applying the encryption
scheme.
 P(X = m|Y = c): A posteriori probability of plaintext m given the
ciphertext c.

AK Bhateja IIT Delhi

 Probability Theory
4
Let P(C = r) = 4/10, and
P(C = b) = 6/10
P(B = g|C = r) = 1/4
P(B = o|C = r) = 3/4
P(B = g|C = b) = 3/4
P(B = o|C = b) = 1/4

𝑃 𝐶 = 𝑏 𝑃(𝐵 = 𝑔|𝐶 = 𝑏)
Bayes theorem: 𝑃 𝐶=𝑏𝐵=𝑔 =
𝑃(𝑔)
6 3
𝑃 𝐶 = 𝑏 𝑃(𝐵 = 𝑔|𝐶 = 𝑏) ∙ 9
= = 10 4 =
𝑃 𝐶 = 𝑟 𝑃 𝐵 = 𝑔 𝐶 = 𝑟 + 𝑃 𝐶 = 𝑏 𝑃(𝐵 = 𝑔|𝐶 = 𝑏) 4 1 6 3 11
∙ + ∙
10 4 10 4
AK Bhateja IIT Delhi
5 Perfect Secrecy

A cryptosystem has perfect secrecy if for every probability

distribution X over M, every plaintext mM and
ciphertexts cC,
P(X = m) = P(X = m|Y = c)
a priori probabilities = a posteriori probabilities
In other words, a ciphertext c gives no information about
the plaintext.

AK Bhateja IIT Delhi

6 Perfect Secrecy-Equivalent formulation
Lemma: An encryption scheme over a message space M is perfectly secret iff
for every probability distribution X over M, every message m  M, and every
ciphertext c  C:
P(Y = c | X = m) = P(Y = c)
Proof: The encryption scheme is perfectly secure
 P(X = m|Y = c) = P(X = m), multiply both sides by P(Y = c)/ P(X = m)

𝑃(𝑋 = 𝑚|𝑌 = 𝑐) ∙ 𝑃(𝑌 = 𝑐)

= 𝑃(𝑌 = 𝑐)
𝑃(𝑋 = 𝑚)
Using Bayes theorem
P(Y = c|X = m) = P(Y = c)

AK Bhateja IIT Delhi

7 One Time Pad

 Let Zm ={0, 1, …, m-1} be the set of alphabets.

 Plaintext space = Ciphtertext space = Key space = (Zm) n
 The key is chosen uniformly randomly
 Plaintext X = (m1 m2 … mn)
 Key K = (k1 k2 … kn )
 Ciphertext Y = (c1 c2 … cn)
 Encryption of X : EK (X) = (m1 + k1 m2 + k2 … mn + kn ) mod m
 Decryption of Y : DK (Y) = (c1 - k1 c2 - k2 … cn - kn ) mod m

AK Bhateja IIT Delhi

8 Conditions for OTP to be unbreakable

 Key is random
 Length of key  length of plaintext
 Key non reusable
 Secret Key Distribution

AK Bhateja IIT Delhi

9 The One-Time Pad (Vernam's Cipher)
M = C = K = {0, 1}n
message m  {0, 1}n, key k  {0, 1}n & ciphertext c  {0, 1}n

Plaintext length n

Ciphertext length n

Key length n Encryption: m  k = c

Decryption: c  k = m
AK Bhateja IIT Delhi
 Theorem: The one-time pad is a perfectly-secret encryption scheme.
10 Proof: Let M = {0, 1}n . For any m  M and any c  C we have
𝑃(𝑚 ∧ 𝑐)
𝑃 𝑚𝑐 =
𝑃(𝑐)
𝑃(𝑐|𝑚) ⋅ 𝑃(𝑚)
= … (1)
𝑃(𝑐)
Using Bayes theorem
𝑃 𝑐 = ෍ 𝑃(𝑐|𝑚) ⋅ 𝑃(𝑚)
𝑚∈𝑀
For any m and c we have
𝑃 𝑐 𝑚 =𝑃 𝑘 = 𝑐⊕𝑚 = 2−𝑛
𝑃 𝑐 = 2−𝑛 ෍ 𝑃 𝑚 = 2−𝑛
𝑚∈𝑀
Therefore, eq (1) imples 𝑃 𝑚 𝑐 = 𝑃(𝑚). Hence OTP is perfectly secure.

AK Bhateja IIT Delhi

11 Theorem: If an encryption scheme with message space M and key space K is
perfectly secure then |K|  |M|
Proof: Suppose |K| < |M| and the scheme is perfectly secure.
Let c be a ciphertext that corresponds to a possible encryption of m
i.e., there exists a k  K such that Ek (m) = c. Also, Dk (c) = m.
If |K| < |M|, then there is at least one message m  M for which
P(c|m) = 0
i.e., P(c|m) = 0  P(c)
and so, the scheme is not perfectly secret.
i.e., for every m ∈ M and c ∈ C, there exists at least one key k ∈ K s.t. Ek (m) = c

AK Bhateja IIT Delhi

12 Shannon’s Theorem
If |K| = |C| = |M| then the system provides perfect secrecy iff
(1) every key is used with equal probability 1/|K|,
(2) for every m ∈ M and c ∈ C, there exists a unique key k ∈ K such
that Ek (m) = c
Proof: (Part 1) Perfect secrecy ⇒ Condition 2 :
Perfect Secrecy  P(X = m|Y = c) = P(X = m)  m and c
Unless P(m) = 0, there must be enough keys so that any ciphertext can
be decoded as a given plaintext, that is, |K|  |C|.
but by supposition, equality must hold.
Hence there is a unique key for every (m, c) pair.

AK Bhateja IIT Delhi

 Shannon’s Theorem
13 If |K| = |C| = |M| then the system provides perfect secrecy iff
(1) every key is used with equal probability 1/| K|,
(2) for every m ∈ M and c ∈ C, there exists a unique key k ∈ K such
that Ek (m) = c

Proof (Part 1) Perfect secrecy ⇒ Condition 1

Suppose keys k1, k2, ... are the unique keys such that 𝐷𝑘𝑖 (c) = mi.
Using Bayes law:
𝑃(𝑌 = 𝑐|𝑋 = 𝑚𝑖 ) ⋅ 𝑃(𝑚𝑖 )
𝑃 𝑋 = 𝑚𝑖 𝑌 = 𝑐 =
𝑃(𝑐)
Perfect Secrecy  P(Y = c | X = mi) = P(Y = c)
Hence each ki must occur with the same probability i.e., 1/|K|.
AK Bhateja IIT Delhi
14 If | K| = | C| = |M| then the system provides perfect secrecy iff
(1) every key is used with equal probability 1/| K|,
(2) for every m ∈ M and c ∈ C, there exists a unique key k ∈ K s.t. Ek (m) = c
Proof: (Part 2) Condition 1 and 2 ⇒ Perfect secrecy
For arbitrary c and m, P[Y = c | X = m] = P[Z = k] = 1/| K |
𝑃 𝑌 = 𝑐 = ෍ 𝑃 𝑌 = 𝑐 𝑋 = 𝑚 𝑃(𝑋 = 𝑚)
𝑚∈𝑀
1 1
= ෍𝑃 𝑋=𝑚 =
|𝐾| |𝐾|
𝑚∈𝑃
𝑃 𝑌 = 𝑐 𝑋 = 𝑚 𝑃(𝑋 = 𝑚)
𝑃 𝑋 = 𝑚|𝑌 = 𝑐 = = 𝑃(𝑋 = 𝑚)
𝑃(𝑌 = 𝑐)
AK Bhateja IIT Delhi
15 Perfect Security vs. Computational Security
Perfect Security Computational Security
Threat is unbounded Threat is computationally bounded
powerful
Key as large as the message A small key works
A scheme is secure if A scheme is secure if any computationally
P(Y = c | X = m) = P(Y = c) bounded adversary succeeds in ‘breaking’
the scheme with at most ‘some very small
probability
New key for every Key reuse is permitted
encryption

AK Bhateja IIT Delhi