8
$\begingroup$

I am aware that,(in theory) in order to proof that a scheme is secure using simulation based proof we replace an adversary in real world with a simulator in ideal world. Then we try to show that their view are (computationally) indistinguishable (if the scheme is secure).

What I need is some simple examples (in zero knowledge or secure multi party computation) that use this idea to proof. So how the simulator is constructed, why sometime we use an adversary to interact with the simulator are not clear to me. Any reference to a paper or explanations would be much appreciated.

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
9
$\begingroup$

The simplest example I know of is actually for a pathological case. Namely, it is presented in Chapter 2 of the book of Hazay and Lindell as an example of a two-party MPC protocol which is secure against a malicious adversary but not against a semi-honest one (in the classical sense, for this reason they prefer the notion of augmented semi-honest adversaries). The protocol is as follows:

Inputs: the two parties $P_1$ and $P_2$ have two bits $x_1$ and $x_2$ respectively.
Outputs: $P_2$ obtains $x_1\wedge x_2$ (the logical AND of $x_1$ and $x_2$), $P_1$ obtains nothing.

The protocol:

  1. $P_1$ sends $x_1$ to $P_2$.
  2. $P_2$ outputs $x_1 \wedge x_2$.

This protocol is not secure against a semi-honest $P_2$ because the view of $P_2$ contains the message $x_1$, which cannot always be computed from the input of $P_2$ (which is $x_2$) and its output (which is $x_1\wedge x_2$). Namely, in the case where $x_1$ is random (uniform) and $x_2 = 0$, then $x_1 \wedge x_2$ will always be $0$, and the simulator has to guess the value of $x_1$, in which it succeeds with probability at most $1/2$.

This protocol is secure against a malicious $P_2$, however.

  • In the real world, a malicious adversary corrupting $P_2$ first obtains the input $x_1$ of $P_1$, and then outputs whatever it wants from $x_1$ and $x_2$.
  • In the ideal world, the honest $P_1$ sends $x_1$ to the ideal functionality. A malicious adversary corrupting $P_2$ sends $1$. Then the adversary obtains $1\wedge x_1 = x_1$, and outputs whatever the real-world adversary outputs.

The fact that it is secure against a malicious $P_1$ is trivial: the ideal-world adversary just sends to the ideal functionality whatever the real-world adversary sends to $P_2$.

To clarify something, the fact that the above protocol is called "secure" may be counter-intuitive, because $P_2$ obtains the output of $P_1$, which seems to contradict the whole point of MPC. However, the definition of secure computation (against a malicious adversary) does not say that the (real-world) adversary must not obtain anything. It says that the real-world adversary must not obtain anything which the ideal-world adversary cannot obtain. And indeed, here we show that the ideal-world adversary corrupting $P_2$ can also obtain the input of $P_1$, hence the fact that the real-world adversary obtains it does not contradict the security of the protocol.

Improve this answer
$\endgroup$
11
  • $\begingroup$ Thank you for the answer. Where can I find some more simple examples using simulation based proofs? :) $\endgroup$
    – user13676
    Commented Jul 18, 2015 at 20:38
  • 1
    $\begingroup$ In your answer, you separated simulator in the ideal world with the adversary in real world (that is good). But in the textbook page 27, when proving the scheme, the simulator is interacting with adversary and this makes me confused. I need to know why it is done that way. $\endgroup$
    – user13676
    Commented Jul 19, 2015 at 16:57
  • $\begingroup$ We can view the ideal-world adversary $\mathcal{S}$ as a simulator which is able to trick the real-world adversary $\mathcal{A}$ into believing it is running in the real world (at it is supposed to) when in fact it is running in the ideal world. For example in the case $\mathcal{A}$ corrupts $P_2$, it expects to receive $x_1$ from $P_1$, but in fact it receives it from $\mathcal{S}$ (which itself receives it from the ideal functionality). $\endgroup$
    – fkraiem
    Commented Jul 19, 2015 at 17:14
  • $\begingroup$ Am I right to say, we have an adversary $A$, in both real world and ideal world. However, in the real world it interacts with the honest part, and in the ideal world it interacts with simulator $S$. It is not clear to me why we can view this way, as this is not explicitly defined in multi party computation model. $\endgroup$
    – user13676
    Commented Jul 20, 2015 at 9:10
  • 1
    $\begingroup$ FYI: Foundation of cryptography volume 2, page 660 has a good and simple example answering the questions, too. $\endgroup$
    – user13676
    Commented Jul 21, 2015 at 18:11
18
$\begingroup$

I have written a tutorial on how to write simulation-based proofs. I think that it should be helpful.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ I've just read Prof. Lindell tutorial and I could say it can give you all illuminated examples you need. The text is fantastically didactic! $\endgroup$
    – Crypto Learner
    Commented Feb 8, 2016 at 18:31

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.