I know the GMW Protocol is secure in the case of a semi honest adversary which control all the parties except one.

However I want to proof that it is also secure in the case the semi honest adversary control all the parties except two.

Does anyone have an idea (even if not formally) how to proof the second case?

  • 2
    $\begingroup$ Isn't it just a particular case? you can regard the case in which the adversary controls $n-2$ parties as corrupting $n-1$, where the messages of one of the parties are forwarded honestly by the adversary $\endgroup$
    – Daniel
    Jun 16, 2017 at 20:18
  • $\begingroup$ @Daniel: want to write that up an an answer? I can't think of much else you could add... $\endgroup$
    – poncho
    Jun 16, 2017 at 20:41
  • $\begingroup$ I have found a proof for the first case: docdro.id/Q2bmWoY, slides 13-15, however I can't manage to expand it to the second case... $\endgroup$
    – Jjang
    Jun 16, 2017 at 21:01
  • $\begingroup$ These are basically the slides from the 1st Bar Ilan winter school, you should take a look at the lectures to clarify your question (these are available online here ) $\endgroup$
    – Daniel
    Jun 16, 2017 at 21:13
  • $\begingroup$ @Daniel I'd like to show a proof (probably a modification of the proof I posted above) to the second case, and not decude it's security from the security of the first case like you mentioned... $\endgroup$
    – Jjang
    Jun 16, 2017 at 21:23

1 Answer 1


Here's my answer:

Suppose that adversary controls the set J of all parties but two parties which is in the set I.
The simulator is given $(x_j,y_j$) for all $P_j\in J$.

Shares of input wires: $\forall j\in J$ choose

  • a random share $r_{j,i}$ to be sent from $P_j$ to any $P_i\in I$
  • and a random share $r_{i,j}$ to be sent from any $P_i\in I$ to $P_j$

Shares of multiplication gate wires:

  • $\forall i'\ne j<i$, choose a random bit as the value learned in the 1-out-of-4 OT with $P_i$.
  • $\forall i'\ne j>i$, choose a random $s_{i,j}$, and set the four inputs of the OT with $P_i$ accordingly.
  • $\forall i\ne j<i'$, choose a random bit as the value learned in the 1-out-of-4 OT with $P_{i'}$.
  • $\forall i\ne j>i'$, choose a random $s_{i',j}$, and set the four inputs of the OT with $P_{i'}$ accordingly.

Output wire $y_j$ of $j\in J$:
Set the message received from any $P_i\in I$ as the XOR of $y_j$ and the shares of that wire held by $P_j\in J$.

Now, the output of the simulation is distributed identically to the view in the protocol.

  • It is true for the random shares $r_{j,i}$ and $r_{i,j}$ sent from and to any $P_i \in I$.
  • OT for $i' \ne j<i$ and $i \ne j<i'$: output is random as in the protocol.
  • OT for $i' \ne j>i$ and $i \ne j>i'$: input to the OT defined as in the protocol.

  • Output wires: message from any $P_i \in I$ distributed as in the real protocol.

Any comments?

  • $\begingroup$ The random shares of the inputs look ok. On the other hand, I think you must be more careful with the multiplication gates. Suppose that $P_{i}, P_{i'}$ are the honest parties, then you cannot force any particular behavior on what these parties share to each other. That's why you should say "for $i'\neq j< i$... for $i'\neq j> i$..." and so on, instead of the generic "for $j<i$" (which may include the case $j = i'$) $\endgroup$
    – Daniel
    Jun 19, 2017 at 23:16
  • $\begingroup$ @Daniel Is this correct now? $\endgroup$
    – Jjang
    Jun 22, 2017 at 5:50
  • $\begingroup$ Im not sure regarding the output wires, doesnt seem to distribute like the real protocol... $\endgroup$
    – Jjang
    Jun 22, 2017 at 5:56

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.