I am trying to understand the simulation-based security proofs (as well as the UC framework), I find that there is a basic assumption when proving the security, i.e., the simulator could extract the secret input of corrupted parties, even if the corrupted parties' input is encrypted or in secret shared form. I have two questions:

  1. Is there any additional requirement or restriction along with this assumption?
  2. Why can/should we rely on this assumption? Currently, I only focus on the semi-honest setting.

Any advice and explanation would be highly appreciated. Thanks.


@WYC, I suggest you take a look at the Lindell tutorial on https://eprint.iacr.org/2016/046.pdf

To answer you #1 question, I'll get from that tutorial the following requirements for the simulator:

  • It must generate a view for the real adversary that is indistinguishable from its real view;
  • It must extract the effective inputs used by the adversary in the execution; and
  • It must make the view generated be consistent with the output that is based on this input.

To answer your #2 question: the simulator is doing a mimic of the adversary. We can say it is a comparision: whatever the adversary do in the real world the (simulated) adversary must be able to do in the ideal world. Therefore, do not read this as a proof of the protocol's flaw. The point is: do you agree that the adversary chooses its inputs? So how simulate it in an indistinguishable way?

  • $\begingroup$ Thanks a lot. I can understand deterministic function in semi honest model, but not for the probabilistic function. Consider two parties to convert a threshold homomorphic ciphertext Enc(x) into two shares. Ideally, the input is Enc(x) and keys, the output is two shares $x_1, x_2$. In the real world, each party has a local random share and use homomorphic properties to do the conversion. Actually, the simulator can easily make the view and output distribution indistinguishable from the real view. But does it need to also make sure the simulated outputs $x_1', x_2'$ satisfy $x_1' + x_2' = x$? $\endgroup$
    – WYC
    Apr 3 '20 at 12:49
  • $\begingroup$ Yes. The point is that all the simulated protocol transcripts (inputs, outputs, randomness) must be indistinguishable of the real world protocol transcription. This artificial game is something like: if everything the protocol can do a simulator can do (by itself), so, the real adversary learns nothing. $\endgroup$ Apr 3 '20 at 16:44

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.