Is there any examples of information-theoretic secure MPC for dishonest majority against malicious adversary?

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

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: