Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
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.
