Paper 2026/283

Malicious Security Comes Free in SPDZ

Abstract

We study the communication complexity of SPDZ-type MPC protocols in the dishonest majority setting with maximum corruption, where $t=n-1$ out of $n$ parties can be corrupted. In the semi-honest setting, the state-of-the-art SPDZ protocol achieves an amortized communication cost of $4n$ field elements per multiplication gate, assuming a pseudorandom correlation generator (PCG) that prepares random Beaver triples silently in the offline phase. However, achieving security against malicious adversaries typically incurs a substantial overhead. Existing works either blow up the communication by incurring $10n$ field elements per gate or an additional overhead of $O(\sqrt{|C|}\cdot n^3)$, or additionally require an additively homomorphic encryption scheme. In this work, we construct a maliciously secure SPDZ-type protocol with the same amortized communication complexity as the semi-honest variant, i.e., $4n$ field elements per multiplication gate, assuming a PCG for \emph{tensor-product} correlations. We note that the tensor-product correlations come free in communication as by-products from almost all existing constructions of PCGs for random Beaver triples, although additional local computation is required. These by-products allow us to construct an efficient preprocessing phase and a recursive check protocol, which enables an online evaluation of the circuit without authenticating all the wire values. The recursive check requires sublinear communication in $|C|$, though it incurs an $O(k)$ overhead on the online computational cost compared to the semi-honest baseline.