1
$\begingroup$

The authors of the book titled "Secure Multiparty Computation and Secret Sharing" claim that there exist functions which cannot be computed with passive perfect security for $t \geq n/2$ corrupt parties, where $n$ is the total number of parties. The authors prove this by showing that no protocol $\pi$ exists for secure 2 party AND with one corrupt party. However, for a 2 party protocol ($n=2$), the threshold of 1 can be written as a function of $n$ as $n/2$ or $(n-1)$, since $n=2$. So how can we guarantee that $n/2$ is the optimal corruption bound?

Can someone please help fill the gap in my understanding?

Improve this question
$\endgroup$
  • $\begingroup$ Can you link to the paper? $\endgroup$ – mikeazo Mar 29 '16 at 16:50
  • $\begingroup$ I was refering to the book by Ronald Cramer, Ivan Damgard, and Jesper Buus Nielsen titled "Secure multiparty computation and secret sharing-an information theoretic approach." $\endgroup$ – Itachi Mar 29 '16 at 16:55
  • $\begingroup$ The draft use to be available online, but now I can't find it. Looks like it is published now, so maybe that is why they took the draft down. There are proofs that for $t<n/2$ we can compute any function. So the optimality of the bound would stem from that. $\endgroup$ – mikeazo Mar 29 '16 at 17:03
  • $\begingroup$ The fact that every function can be securely computed for $t < n/2$ corrupt parties does not prove that there exists a function which cannot be computed securely for $t \geq n/2$ corrupt parties. Am I right? $\endgroup$ – Itachi Mar 29 '16 at 17:19
  • $\begingroup$ That is correct. $\endgroup$ – mikeazo Mar 29 '16 at 18:18
7
$\begingroup$

The way to extend the proof to arbitrary $t,n$ and this threshold is as follows. Assume that there exists a protocol for any $n$ parties that withstands a threshold of $t=n/2$ corrupted parties, for computing $f(x_1,\ldots,x_n)=x_1 \wedge x_{n/2+1}$. (If it withstands $t>n/2$ then it also withstands $t=n/2$, so that's fine.) I will now construct a two-party protocol for securely computing AND that is resilient to one corruption. This will contradict the known impossibility result.

The protocol works as follows. The parties simulate an execution of the $n$-party protocol. Party $P_1$ internally runs parties $P_1,\ldots,P_{n/2}$ and party $P_2$ internally runs parties $P_{n/2+1},\ldots,P_n$. Party $P_1$ puts its input as the input of $P_1$ in the $n$-party protocol, and party $P_2$ puts its input as the input of $P_{n/2+1}$ in the $n$-party protocol. The parties output whatever the multiparty protocol says to output.

In order to argue security, all you really need to notice is that if one party is corrupted then this is equivalent to $t=n/2$ in the multiparty protocol. Therefore, security is maintained.

Improve this answer
$\endgroup$
  • $\begingroup$ That's a very cute and an elegant reduction based proof. Thank you once again professor. :) $\endgroup$ – Itachi Mar 31 '16 at 4:49

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.