Tuesday, September 13, 2016

XOR encryption is a randomized algorithm

We exactly describe that One Time Pad (OTP) encryption, that uses XOR operation, is a randomized algorithm.

Below is the definition of Randomized Algorithms:


A cipher (E, D) over (K, M, C) is OTP, so that
c = E (k, m) = k xor m
K = M = C = {0, 1}^n

For the definition of Randomized Algorithms, if k and c are uniform random variables, the OTP encryption, E, is a randomized algorithm. 

The k, selected in K, must be a uniform random variable for the reason,

Why is the c, calculated by the OTP encryption, also a uniform random variables? The question is same to proof the below formula that is the definition of uniform random variable.

Pr [c = c0] = 1 / |C|

Please remember that a random variable is really a function. So transform the formula to display the function E (k, m0),

Pr [c = c0] = 
Pr [E (k, m0) = c0] =

OTP encryption uses XOR operation.

Pr [k xor m0 = c0] = 
Pr [k = c0 xor m0] =
Pr [k = k0] = 1 / |K|

because there is only one k0  that encrypts m0 to generate c0. 

Pr [c = c0] = 1 / |K| = 1 / |C|  
because |K| = |C| = 2^n

We proof that the OTP encryption is a randomized algorithm.

-Count

No comments:

Post a Comment