Sunday, January 15, 2017

The 1-bit PRP is not a secure PRF

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

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