I understood the meaning of interactive assumption from What is the notion of an interactive assumption? . However, I am not sure why there exists a research field of constructing PRF from standard assumption.

What is the advantage of standard assumption over interactive model in general and especially for PRF?


1 Answer 1


The advantage of a non-interactive assumption is that you prove something in general . In contrast in an interactive assumption you prove a specific instantiation of the problem. Think a variety of DL problems like DDH. The game starts with the challenger choosing the challenge. The challenge is given to the adversary and then the later is trying to solve it. That means for any instance of the problem. In contrast in an interactive assumption there is a learning phase like in CPA proof whereby the adversary is learning: is asking queries to the encryption oracle. That being said the proof is specific for that interaction. In some sense it is weaker because you cannot predict if there is a craft query that will break the system.

  • $\begingroup$ I disagree with the statement that interactice is weaker. Because in any game, you could say the adversary does his random coins and queries before the game starts. And then it is effectively non-interactive. Giving the adversary additional information before his coin tosses just makes the resulting assumption stronger. I think the main reason is just, that non-interactive systems are much, much simpler to analyze. $\endgroup$
    – tylo
    Dec 14, 2019 at 16:32
  • $\begingroup$ Thank you for your comments! What would be the implication of simpler analysis? $\endgroup$
    – mallea
    Dec 16, 2019 at 1:29

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.