Saturday, October 15, 2016

Understand that, One Time Pad (OTP) has perfect secrecy

A cipher (E, D) over (K, M, C) that is OTP if

K = M = C = {0, 1}^n
c = E(k, m) = k xor m
m = D(k, c) = k xor c
where c in C, k in K, m in M

OTP has perfect secrecy because |k| = |m|.

How do we understand the statement?

We can give a simple example.

K = M = C = {0, 1}^2

Below is the table of the OTP cipher.



We focus on c = 11 to guess the probability of m where k is a uniform random variable.

Pr[E(k, 00) = 11] = 1/4 
Pr[E(k, 01) = 11] = 1/4 
Pr[E(k, 10) = 11] = 1/4 
Pr[E(k, 11) = 11] = 1/4 

It describes that the OTP is perfect secrecy because

Pr[E(k, m) = c] = 1/4, for all c in C,
where k is a uniform random variable.


-Count

No comments:

Post a Comment