1
$\begingroup$

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?

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.