6
$\begingroup$

I have seen some examples in "Foundation of cryptography" and "Efficient two party computation", in which simulator can do some things that in the real world model the parties cannot do, for instance:

  1. In "Foundation of..." page 660, Coin Tossing protocol, the simulator first receives the result from trusted third party (TTP) without sending the parties input to it. My question is why can it do so, where in the real protocol the parties exchange their input first.

  2. In "Efficient two..." page 140, full simulation oblivious transfer, the simulator:

    (a) Can receive the adversary input to underlying zero knowledge and extract its secret value. This is not possible for an honest party in the real world model.

    (b) The simulator (despite using some incorrect input to zero knowledge) makes the adversary believe that the zero knowledge proof is verified, where it would not occur in the real world model.

Main question: What can and cannot the simulator do when simulating the real world?

$\endgroup$
10
$\begingroup$

There is quite a bit of confusion in your question. First, differentiate between the real and ideal models. The adversary in the ideal model sends the adversary's input and gets its output (and can also sometimes determine if the honest party gets output, depending on the model). We often call the ideal adversary a "simulator" since this is how we build the security proof. Thus, in the case of coin tossing where no party has input, the simulator begins by getting the output. This is allowed by definition.

Now, the simulator typically works by running the real-world adversary. Here it has power. For example, it can rewind the real-world adversary, can look at its random tape, and so on. (This gets complicated depending on the model. For example, in the common reference string model it's different. But let's leave this for now.)

Finally, in a HYBRID model, there are additional issues. In this model, the parties exchange messages but also have access to a trusted party. When simulating a protocol in this model, the simulator actually runs the trusted party for the adversary. Thus, in the ZK-hybrid model, the simulator gets the adversarial prover's input (which includes the witness). This is allowed by the composition theorem of the model being used.

None of this is straightforward, and it's very hard to learn by yourself. I suggest that you look at some videos online; they may help. For example, the Bar-Ilan Winter Schools from 2011 and 2015 cover secure computation and may help you get started.

$\endgroup$
  • $\begingroup$ I do appreciate for the answer. $\endgroup$ – user13676 Jul 26 '15 at 19:04
  • $\begingroup$ consider a case where two parties send their private data to a malicious server, then it computes the result and sends it back to a party. My question is that in the ideal world, can we allow the adversary escape from detection with the same probability(that is negligible) as it can do in the real world? Or in the ideal world the simulator must detect the adversary's misbehavior with probability of exactly 1? $\endgroup$ – user13676 Jul 29 '15 at 14:20
  • $\begingroup$ Anything negligible won't matter. The ideal adversary can behave differently with negligible probability. But in truth it's very hard to give a proper answer to this without all the information. $\endgroup$ – Yehuda Lindell Jul 29 '15 at 17:06

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.