TransWikia.com

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

Cryptography Asked by shoy700 on October 24, 2021

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.

One 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:

Answered by Mikero on October 24, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP