In this paper:


the authors use peudorandom permutation in the protocols and proof rather than pseudorandom function. On page 31 (last two lines) they say:

"We also note that for the purposes of the simulation, we need to use a pseudorandom permutation rather than any pseudorandom function."

Question: Why can we use pseudorandom permutation in the simulation but we cannot use pseudorandom function?

  • $\begingroup$ I only read the abstract, but my guess is that the reason is $\hspace{2.35 in}$ "Pseudorandom functions usually have collisions.". ​ ​ $\endgroup$
    – user991
    Sep 7, 2016 at 22:15

1 Answer 1


I happened to be talking to one of the authors and asked about this. The short answer is: Eventually on page 34 they are considering a malicious adversary. The simulator has to extract the adversary's effective input but it only knows the messages sent by the adversary, which in this case are just the PRP outputs. The simulator knows the PRP key so it can invert the PRP to determine the adversary's effective input. A PRF wouldn't allow this, although a PRF is indeed enough for the semi-honest variant of the protocol starting on page 31.

  • $\begingroup$ Thank you for the answer. I sent an email to professor Kamara, but I haven't got anything back so far. $\endgroup$
    – user153465
    Sep 8, 2016 at 21:47
  • $\begingroup$ Using your correct answer can I say that they use PRP because they consider malicious Client , but if they consider only malicious server they would not need to use PRP as the server has no input and output. $\endgroup$
    – user153465
    Sep 9, 2016 at 11:48
  • 1
    $\begingroup$ That sounds correct to me. $\endgroup$
    – Mikero
    Sep 9, 2016 at 15:58

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.