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