3
$\begingroup$

This example is from “Efficient Secure Two-Party Protocols-Carmit Hazay-Yehuda Lindell”.

Example of Secure Computation of AND

And the security proof of the above example is this:

Proof of the above security protocol

I have drawn a picture that is deduced from the above security proof.

Picture1:

[P1 is corrupted-picture1[3]

Picture 2:

P2 is corrupted-picture2

I have several questions:

  1. Please, explain to me how the simulator and the adversary interact with each other? I mean what kind of requests can the simulator send to the adversary and vice versa. (what kind of requests can the adversary send to the simulator).

  2. According to the security proof and the picture 1, why does the simulator get input x from the adversary and not from corrupted P1?

  3. Should simulator trust the adversary? I mean is it possible that the adversary, in picture 1, modifies input x, deliberately, and then give it to the simulator? If yes, how will the simulator figure out this modification?

  4. Would you please explain to me what is the real view for P1 and P2 in both pictures? Please explain to me what must the simulator simulate in picture 1 and picture 2?

Definition 2.3.1

Page 24: Definition of security in the malicious model

According to the above definition 2.3.1 and the description on page 24, I think the answer is like this:

Case1: When P1 is corrupted: real view of P1 is (x) and real view of P2 is (x, y, x ^ y) And simulator must simulate P1’s view and P2’s output.

Case2: When P2 is corrupted: real view of P1 is (x) and real view of P2 is (x, y, x ^ y) And simulator must simulate P2’s view and P1’s output.

If my answers are not correct, please correct them.

$\endgroup$
  • 1
    $\begingroup$ There seems to be a small terminology inconsistency in the book. In the malicious model, the "adversary" and the "simulator" are the same thing. Note that the word "simulator" never appears in the definition of security in the malicious model (Definition 2.3.1), but it suddenly appears in the proof of Claim 2.3.3. The "simulator" $\mathcal S$ there is the adversary in the ideal model, which must simulate the output of the real-model adversary $\mathcal A$. In particular, $\mathcal S$ and $\mathcal A$ do not interact with each other at all; they live in different worlds. $\endgroup$ – fkraiem Aug 31 '18 at 11:19
  • $\begingroup$ Mr. fkraiem, you mean that there is a problem with the definition 2.3.1 or the claim 2.3.3 ? $\endgroup$ – AmirHosein Adavoudi Aug 31 '18 at 11:24
  • 1
    $\begingroup$ No, I say that they introduce the term "simulator" perhaps a bit suddenly, and that could be the source of your confusion, so I have clarified its meaning. $\endgroup$ – fkraiem Aug 31 '18 at 11:26
  • 1
    $\begingroup$ By the way, note also that the view of the parties is considered in the semi-honest model, and not (explicitly) in the malicious model. In the malicious model, we only care about the output (although this implicitly includes the view, since any algorithm can output its own view) $\endgroup$ – fkraiem Aug 31 '18 at 15:33
1
$\begingroup$

Without meaning any offense to the authors, this proof could perhaps have been written a bit more clearly; probably, since this is a fairly minor result, they didn't expend too much effort on it. Here is a longer but hopefully clearer rewording which should clear your terminological confusion.

Corrupted $P_1$

The real-world adversary $\mathcal A$ corrupting $P_1$ has input $x$ and auxiliary input $z$. It sends some value $x'$ to $P_2$ and outputs some value $x''$; both $x'$ and $x''$ are computed from $x$ and $z$. Since $P_2$ is honest, it computes and outputs $x' \wedge y$, for its received value $x'$ and input $y$, as instructed by the protocol; the output pair is $(x'', x' \wedge y)$.

The ideal-world adversary $\mathcal S$ (aka the simulator) again has input $x$ and auxiliary input $z$; it first computes $x'$ and $x''$ from $x$ and $z$ just like $\mathcal A$ does*. It then sends (or instructs $P_1$ to send) $x'$ to the trusted party; the honest $P_2$ sends $y$. The trusted party returns $\varepsilon$ (the empty string) to $\mathcal S$ and $x' \wedge y$ to $P_2$. $\mathcal S$ outputs $x''$ and $P_2$ outputs $x' \wedge y$; the simulation is perfect.

Corrupted $P_2$

The real-world adversary $\mathcal A$ corrupting $P_2$ has input $y$ and auxiliary input $z$. It receives $P_1$'s input $x$ and outputs some value $y'$ computed from $x$, $y$ and $z$. Since $P_1$ is honest, it outputs $\varepsilon$ as instructed by the protocol; the output pair is $(\varepsilon, y')$.

The simulator $\mathcal S$ again has input $y$ and auxiliary input $z$; it sends $1$ to the trusted party, and the honest $P_1$ sends $x$. The trusted party returns $\varepsilon$ to $P_1$ and $x \wedge 1 = x$ to $\mathcal S$. The honest $P_1$ outputs $\varepsilon$, and $\mathcal S$ computes and outputs $y'$ just like $\mathcal A$ does; the simulation is perfect.

* This is basically what they mean by "$\mathcal S$ receives [...] from $\mathcal A$." You could consider that $\mathcal S$ is given black-box or oracle access to $\mathcal A$: it sends $\mathcal A$ the values $x$ and $z$ and $\mathcal A$ returns $x'$ and $x''$ like it does in the real world. It's a bit awkward, however, because such black-box/oracle access has not been defined at this point in the book, and in particular does not appear in the security definitions.

$\endgroup$

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.