My research is to propose highly secure MPC protocol with some conditions.

Especially, I want to consider that

  1. security against malicious (active) adversary
  2. dishonest majority setting
  3. information-theoretic security

I know SPDZ family that achieve 1 and 2 above and some protocols that achieve 1 and 3 above.

Could you tell me the MPC that achieves 1, 2 and 3 above? I want to know this type of MPC as an example, however, I cannot find it.

I think this type of MPC cannot exist if it doesn't have very strong conditions.

The answer "I don't know this type of MPC" is also welcome.


1 Answer 1


What you are asking for is not possible, not even if you ask for passive security. Here is a sketch of a proof.

Suppose for sake of contradiction you have an $n$-party MPC protocol $\Pi$ for $f(x_1, \ldots, x_n) = x_1 \land x_n$, where the $x_i$'s are bits. This protocol is secure against a computationally unbounded adversary who can passively corrupt $\ge n/2$ parties.

You can take this $n$-party protocol $\Pi$ and construct a related 2-party protocol $\Pi^*$. Player 1 in $\Pi^*$ plays the role of parties 1 through $n/2$ in $\Pi$, and Player 2 in $\Pi^*$ plays the role of parties $n/2+1$ through $n$ in $\Pi$. So $\Pi^*$ is a 2 party protocol that takes input $x_1$ for Party 1 and $x_n$ for Party 2 and computes $x_1 \land x_n$.

The 2-party protocol $\Pi^*$ is secure against 1 corrupt party. Corrupting 1 party in $\Pi^*$ is like simultaneously corrupting $n/2$ parties in $\Pi$, and by our assumption $\Pi$ is secure in that scenario.

So now we have a 2-party protocol $\Pi^*$ for securely computing the AND of two bits, which is secure against a passive, computationally unbounded adversary (who corrupts 1 party). But this is known to be impossible. If you're asking about perfect security, it was proven in:

The proof was later generalized to statistical security in:


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.