X = {0, 1}

E: E x X ---> Y

E (k, x) = x xor k

E is a secure PRP

but it is not a secure PRF. How do we explain it? 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 function.

There are two permutations in World 0. and four functions in World 1. An attacker wants to find an algorithm to distinguish both worlds.

**The attacker uses the algorithm A1,**

if f(0) == f(1), then output "1"

The attacker inputs x = 0 and x = 1 to distinguish both worlds.

For World 0, the probability of the algorithm that outputs "1" is 0.

Pr [EXP(0) = 1] = 0

For World 1, the probability of the algorithm that outputs "1" is 1/2.

Pr [EXP(1) = 1] = 1/2

Adv [A1, E] = |0 - 1/2| = 1/2

**The attacker uses the algorithm A2,**

if f(0) != f(1), then output "1"

The attacker inputs x = 0 and x = 1 to distinguish both worlds. We just use the below formulas.

Pr [EXP(0) = 1] = 1

Pr [EXP(1) = 1] = 1/2

Adv [A2, E] = |1 - 1/2| = 1/2

In conclusion, no matter the attacker uses A1 or A2, the Adv is always 1/2. It means that the attacker can easily distinguish both worlds, 1-bit PRP and truly random function. Therefore the 1-bit PRP is not a secure PRF.

-Count

## No comments:

## Post a Comment