1
$\begingroup$

In the book titled "Secure Multiparty Computation and Secret Sharing" stated that MPC protocol is not secure when the adversary $t>n/2$. This was proved by using a 2 party protocol, but I can't understand why the same applies when $n<2$.

For example, when $n=6$ and $t=3$, the adversary might know the multiplication of the output for the 3 honest players, but as long as their individual inputs are not known, doesn't that consider as secure? Could someone please help me with this problem?

$\endgroup$
2
$\begingroup$

First, it's important to understand that MPC is not possible for $t \geq n/2$ in the information-theoretic setting (where the adversary is computationally unbounded). In the computational setting, where the adversary is polynomial-time, it is possible to achieve MPC under cryptographic hardness assumptions.

Regarding your specific question, I assume you are referring to a case where we have a polynomial of degree $t$ to share a secret. Indeed, it is possible to share a secret securely for any $t\leq n$. However, the problem is that you need to be able to process that secret. So, if $t=3$ and $n=6$ and you have a degree-3 polynomial, then the first step of multiplication yields a polynomial of degree-6. In order to reconstruct the values, 7 points are needed for a degree-6 polynomial. However, there are only 6 parties and only 6 points. So, this cannot be done.

Of course, the above just says why this approach doesn't work. However, it's possible to prove that no approach can work, and I believe that this also appears in the book.

$\endgroup$
  • $\begingroup$ Thank you Professor, but what if the multiplication is performed using another approach that does not increase the polynomial degree (for example, scalar value * polynomial), does the corruption bound still apply? And also, does this limitation also apply for addition using MPC? $\endgroup$ – amin Jul 24 '17 at 15:20
  • $\begingroup$ @amin, are you saying you are doing a single operation, either scalar multiplication or addition? $\endgroup$ – mikeazo Jul 24 '17 at 23:02
  • $\begingroup$ @amin As I described in my answer, I only showed that the polynomial approach doesn't work. However, I also explained that it's possible to prove that no approach can work. You can find a proof of this in the book you mentioned. $\endgroup$ – Yehuda Lindell Jul 25 '17 at 3:41
  • $\begingroup$ @YehudaLindell Ohh, I get it. Thank you very much for your reply. $\endgroup$ – amin Jul 25 '17 at 6:32
  • $\begingroup$ @mikeazo yes, I'm curious whether by doing single operation such as scalar multiplication or addition would lead to the same limitation such as the one in polynomial multiplication. $\endgroup$ – amin Jul 25 '17 at 6:34

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.