In the full-length proof of PAK scheme, the authors made extensive use of random oracles to extract (guessed) password from the messages generated by the real world adversary for the ideal world simulator.


  1. Are all the random oracle calls $H_i(\cdots)$ in the real world protocol (even called by honest users) controlled by the simulator?

  2. Does the simulator need to make responses for the requests of honest users via the real world adverary's delivering?

  3. Does the simulator make use of the status of honest users? For example, A (either the honest user or impersonated by the real world adversary) sends a password to B and B sets the status of himself as accept or reject. Is B's status watched by the simulator and the real world adversary?

  4. Why the password-extraction from real world messages is so imporant in simulation-based proofs? Is it indeed some kind of zero-knowledge proof for showing these password-related messages in the real protocol are as zero-knowledge as the messages in the ideal world? (as the authors suggested to use NIZK in place of random oracle)

  5. Is there any weaker proof method (which, however, still guarantees us security practically), especially for the password-authenticated key exchange area?


1 Answer 1

  1. In the real-world protocol there is no simulator. There is a real-world adversary and it has access to the exact same (random) oracle as the honest parties. The simulator controls the random oracle in the ideal-model simulation only.
  2. This is not required by the definition, but is the way that things work. Essentially, the simulator plays the role of the honest parties to the real adversary. Of course, it does this without knowing the honest parties' inputs and outputs.
  3. This depends on what information the ideal adversary/simulator gets about the status of the honest parties. If the ideal functionality provides the status to the ideal adversary, then it knows it; otherwise, not.
  4. The natural way to define the ideal functionality is for the parties to send their password to the ideal functionality and if they match then a random session key is provided to them both. In order to simulate a real execution in the ideal model, the simulator must therefore send the ideal functionality the passwords that the adversary (implicitly) uses.
  5. You can define "game based definitions" not via an ideal functionality. In any case, proving the security of password protocols without any setup (like a CRS or PKI) is very difficult. Proving without a random oracle is even harder.

Overall, it seems that you could benefit from taking a step back from PAKE and looking at how ideal/real simulation proofs work. Here is an answer that I wrote that tries to give a bit of an explanation. However, you really need to read some more basic papers. (PAKE is hard place to start.)

  • $\begingroup$ I've read Shoup's famous paper "On Formal Models for Secure Key Exchange" and in the paper, due to the use of powerful cryptographic primitives, its construction of the simulator seems to be too simple to show the entire methodology. Do you have any more detailed sugguestion about reading papers? I always seemingly understand the big picture of the ideal/real paradigm and always fall into confusion when I start to read the concrete proof, sadly ... $\endgroup$
    – phan
    Sep 19, 2015 at 19:02
  • 1
    $\begingroup$ I wish I had a good answer for you. Oded Goldreich's foundation of cryptography volume 2 is of course the best. It's very hard reading, but it's well worth the investment. Otherwise, look for papers on things like coin tossing and oblivious transfer, since these are relatively simple. You can also look at my book with Carmit Hazay on the topic (see cs.biu.ac.il/~lindell/efficient-protocols.html). $\endgroup$ Sep 19, 2015 at 19:21

Your Answer

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

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