-1
$\begingroup$

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?

Improve this question
$\endgroup$
  • 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 '17 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 '17 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 '17 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 '17 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 '17 at 21:23
0
$\begingroup$

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?

Improve this answer
$\endgroup$
  • $\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 '17 at 23:16
  • $\begingroup$ @Daniel Is this correct now? $\endgroup$ – Jjang Jun 22 '17 at 5:50
  • $\begingroup$ Im not sure regarding the output wires, doesnt seem to distribute like the real protocol... $\endgroup$ – Jjang Jun 22 '17 at 5:56

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.