Saturday, January 14, 2017

Why is 1-bit PRP with XOR secure?

The Stanford on-line course, Cryptography I, describes that the following 1-bit PRP is secure.

X = {0, 1}
E: K x X ---> Y
E(k, x) = x xor k
E is a secure PRP

How do we understand it?

Permutation.

A function f: X ---> Y is a permutation means that it is an one-to-one and onto function, and the domain X is equal to the codomain Y.

Pseudo Random Permutation (PRP)

The function E(k, .) is a PRP means that E(k, .) is a permutation and k is a random variable that defines the permutation.

Secure PRP.

The function E(k, .) is a Secure PRP means that it is indistinguishable from a random function in the set of all permutations.

The above 1-bit PRP is secure.

We can imagine that there are two worlds as the below picture, World 0 and Word 1. World 0 is for 1-bit PRP and World 1 is for truly random permutation for the 1-bit.



There are two permutations in World 0 and they are same in World 1. We can say that World 0 is equals World 1. An adversary cannot distinguish both worlds.  Therefore the 1-bit PRP is secure.

-Count

No comments:

Post a Comment