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?

Improve this question
$\endgroup$
7
  • 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
    Commented Nov 4, 2018 at 13:00
  • $\begingroup$ yes, that is the problem. $\endgroup$
    – kelalaka
    Commented Nov 4, 2018 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
    Commented Nov 4, 2018 at 13:24
  • $\begingroup$ @Maeher yes, I do. Why is it wrong? $\endgroup$
    – Nick123
    Commented Nov 4, 2018 at 13:26
  • 1
    $\begingroup$ It's not a PRF. Indistinguishability is part of the definition of PRF. $\endgroup$
    – Future Security
    Commented Nov 4, 2018 at 15:22

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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