Statistical MPC with a Constant Communication Overhead

본문 미리보기

We study the feasibility of constant communication-overhead statistically-secure MPC tolerating malicious adversaries in the synchronous setting and guaranteed output delivery (GOD). We propose a protocol with $n = 3t + 1$ for SIMD circuits with a communication overhead of ${\cal O}(1)$ and round complexity ${\cal O}(D)$ for circuit depth $D$, where $n$ is the number of parties and $t$ is the maximum number of corruptions. Moreover, our protocol achieves GOD. This is the first MPC protocol