# How to prove the PRF, $F(k,x) = (k \wedge x ) \oplus k$ is PRP?

I am trying to understand PRF's and PRP's. I have got a question where I have to decide whether $$F(k,x) = (k \wedge x ) \oplus k$$ (where $$k$$ and $$x$$ are simple $$1$$ bits (1 or 0)) is PRP or not. I am not sure if I understand PRP's correctly. As I have found:

A Pseudo Random Permutation is a PRF that happens to have the property that every element in the input domain has a single associated member in the output co-domain and vice versa.

So what I have got in my example.

k x F(k,x)
0 0 0
0 1 0
1 0 1
1 1 0


For each couple, I have an associated member in output co-domain, but for each output 0 and 1. I do not have a unique member in the input domain. So this function is not PRP. Am I right?

• As there exists no such F'(k, y) that gives a chance to restore value of x for k = 0 that is the problem? Nov 4, 2018 at 13:00
• yes, that is the problem. Nov 4, 2018 at 13:02
• For some reason you seem to be working under the premise that the function is a PRF. That premise is wrong. Nov 4, 2018 at 13:24
• @Maeher yes, I do. Why is it wrong? Nov 4, 2018 at 13:26
• It's not a PRF. Indistinguishability is part of the definition of PRF. Nov 4, 2018 at 15:22

Your definition tries to say that a permutation must be invertible.

When the key is $$0$$, we can not determine the inverse of 0 and the inverse of 1 doesn't exist.