Suppose there is a secure PRF $F: K \times X \to Y$. Then is $F': X \times K \to Y$, defined by $F'(x,k):=F(k,x)$, a secure PRF?

In my opinion it should be because exchanging the keyspace with the message space shouldn't effect the security. As we were choosing a random key from the key space, similarly we can choose a key from message space randomly and can use to compute $F'$. However, I am not sure about my intuition.

  • 2
    $\begingroup$ Have you tried to construct an $F$ for which $F(Key, Message)$ is a secure PRF, but $F(Message, Key)$ is not? $\endgroup$ – poncho Apr 14 '14 at 19:35
  • $\begingroup$ Actually, I thought a lot but every time I got stuck to the point that we are choosing "key" randomly from message space so it should not matter to security of PRG. $\endgroup$ – user2771151 Apr 14 '14 at 19:49

In general this is not the case. Consider a PRF F which ignores the first bit of the key. Then you can distinguish F'(k,.)=F(.,k) from a random function (and thus break its security as a PRF) by querying it on inputs x and x', where with x' we denote x with the first bit flipped. Note that the outputs of F'(k,.) will collide on inputs x and x' as F(x,k)=F(x',k).

| improve this answer | |

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.