TL;DR
This paper presents new constructions for achieving fully secure multiparty computation (MPC) with significantly improved efficiency, particularly in terms of communication and round complexity. They achieve this by leveraging and extending zero-knowledge fully linear interactive oracle proofs (zk-FLIOPs) over general rings, closing a critical gap for practical MPC.
What Problem Does This Paper Address?
Secure multiparty computation (MPC) allows multiple parties to jointly compute a function on their private inputs without revealing those inputs. While semi-honest security (where parties follow the protocol but can be curious) is relatively easy to achieve, malicious security (where parties can deviate arbitrarily) is much harder. The "holy grail" is full security, which guarantees correctness and output delivery even against malicious adversaries.
Recent advancements have shown that full security can be achieved with only a sublinear communication overhead over semi-honest protocols, by first running a semi-honest protocol and then a verification step using zero-knowledge proofs. However, a key challenge remains: the round complexity of this verification step can become a bottleneck, especially for large but shallow circuits or in wide-area network (WAN) settings where latency is high. Existing methods often add a logarithmic number of rounds, which can be detrimental. This paper aims to close the gap by achieving full security with constant additional rounds and sublinear communication overhead, applicable to a wide range of rings.
Methods
The core of the paper lies in two main contributions:
- A New MPC Framework for Full Security: The authors propose a novel MPC framework that lifts semi-honest protocols to fully secure ones. This framework is remarkably general, working with any linear secret sharing scheme and any finite ring (even non-commutative ones). It relies on a black-box use of zk-FLIOPs and achieves statistical security. A key aspect is its ability to achieve a constant number of additional rounds beyond the underlying semi-honest protocol, while adding only an additive communication overhead of $O(\log |C|)$, where $|C|$ is the number of multiplication gates in the circuit.
- Extensions and Improvements to zk-FLIOPs: To support their MPC framework, the paper introduces new and improved zk-FLIOP constructions.
- General Rings: They extend zk-FLIOPs to work over potentially non-commutative rings, requiring only a specific type of "large enough" exceptional set. This is a significant generalization beyond prior work that focused on fields or specific ring structures.
- Galois Rings: For Galois rings (a generalization of finite fields and $Z_{2^k}$), they present concrete improvements. By leveraging Reverse Multiplication-Friendly Embeddings (RMFEs), they achieve better communication complexity for constant-round proofs, particularly for SIMD (Single Instruction, Multiple Data) circuits.
The MPC framework utilizes a "single-prover" approach for verification, where each party proves its own honest execution. This contrasts with "distributed-prover" approaches and is crucial for achieving constant rounds. The verification process involves agreeing on a compressed transcript, then using zk-FLIOPs to verify specific relations derived from the circuit computation.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Round Complexity is Crucial: The paper highlights that for many practical MPC scenarios, especially with large, shallow circuits or high-latency networks, minimizing the number of communication rounds is as important, if not more so, than minimizing communication bandwidth.
- Generality of Rings: The authors demonstrate that efficient full security can be achieved over a much broader class of rings than previously thought, moving beyond just finite fields. This opens up MPC to more diverse applications.
- zk-FLIOPs as a Versatile Tool: The work showcases the power and flexibility of zk-FLIOPs, not only for enabling full security in MPC but also for driving advancements in the primitive itself.
- RMFEs for Efficiency: The clever application of Reverse Multiplication-Friendly Embeddings (RMFEs) is key to achieving improved communication complexity in specific settings like Galois rings.
- "Single-Prover" Verification: Adopting a single-prover verification strategy is instrumental in achieving constant-round overhead, a significant improvement over prior work.
Key Results
- New MPC Framework: A general framework for achieving fully secure MPC with constant additional rounds and $O(\log |C|)$ communication overhead over semi-honest protocols.
- zk-FLIOP for General Rings: A zk-FLIOP construction for proving statements over potentially non-commutative rings with specific algebraic properties.
- Improved zk-FLIOP for Galois Rings: Optimized zk-FLIOPs for Galois rings, leveraging RMFEs to reduce communication complexity, especially for constant-round proofs.
- Concrete Instantiations: The paper provides three concrete instantiations of their MPC framework, achieving various trade-offs in terms of preprocessing and security settings (e.g., any linear scheme, replicated secret sharing, two-thirds honest majority).
- Addressing Double-Dipping: The framework offers a new solution to the "double-dipping" attack in DN-style protocols without modifying the underlying semi-honest protocol.
Limitations and Future Work
- Open Question for $t < n/2$ and Linear Preprocessing: The paper identifies an open problem: achieving sublinear communication and constant rounds with linear preprocessing for the $t < n/2$ honest majority setting (when $n$ is large). Their current framework requires $O(n^2|C|)$ preprocessing for this setting.
- RMFEs and Non-Constant Rounds: While RMFEs provide benefits for constant-round proofs, the paper notes that they do not directly lead to improvements in the non-constant round setting for zk-FLIOPs, due to an additional cost associated with kernel elements.
- Heuristic Nature of Fiat-Shamir: The paper mentions that using the Fiat-Shamir transform to make interactive protocols non-interactive is a heuristic approach, and its security guarantees degrade with more rounds.
- Future Work: The authors suggest extending their techniques to settings with weaker ring properties and exploring further applications of RMFEs.
Summary updated