TL;DR
This paper presents a new protocol for fully secure multiparty computation (MPC) in the "honest majority" setting (where more than half of the parties are honest). It achieves a significant reduction in communication rounds to $O(\text{depth}(C))$, matching the efficiency of protocols for smaller corruptions ($t < n/3$), while maintaining linear communication complexity. This is achieved by introducing a novel technique for efficiently reconstructing robustly secret-shared values, avoiding the costly "dispute control" mechanisms previously required.
What Problem Does This Paper Address?
Secure multiparty computation (MPC) allows a group of parties to jointly compute a function on their private inputs without revealing anything beyond the function's output. A key challenge in MPC is achieving "guaranteed output delivery" (G.O.D.), meaning honest parties are guaranteed to receive the correct output even if some parties are malicious.
The paper focuses on the "honest majority" setting, where the number of corrupt parties $t$ is less than $n/2$ (where $n$ is the total number of parties). While G.O.D. is achievable in this setting with statistical security using a broadcast channel, existing protocols suffer from a significant drawback: a round complexity of $\Omega(\text{depth}(C) + n^2)$. This $n^2$ overhead, stemming from techniques like "dispute control," makes these protocols impractical for large numbers of parties or when communication latency is high.
In contrast, for the $t < n/3$ setting, protocols with $O(\text{depth}(C))$ rounds are known, either by allowing superlinear communication or by assuming correlated randomness (the "preprocessing model"). The paper's central question is whether this $O(\text{depth}(C))$ round complexity can be achieved for the $t < n/2$ honest majority setting, without resorting to dispute control, and ideally while maintaining linear communication.
Methods
The paper introduces a new MPC protocol for the $t < n/2$ setting that operates in the preprocessing model, leveraging correlated randomness. The core of their contribution lies in a novel technique for efficiently reconstructing robustly secret-shared values.
Key aspects of their approach include:
- Avoiding Dispute Control: Instead of relying on dispute control mechanisms to handle malicious behavior and ensure output delivery, the protocol uses a different approach based on robust secret-sharing.
- Robust Secret-Sharing: The protocol utilizes a robust secret-sharing scheme that guarantees reconstruction of a secret even if some shares are corrupted, albeit with a higher communication cost in its basic form.
- Efficient Batch Reconstruction: The main technical innovation is a method for reconstructing a batch of robustly secret-shared values with linear communication per secret. This is achieved by cleverly batching openings and using compressed authentication tags.
- Preprocessing Model: The protocol assumes access to correlated randomness, which is established during an initial preprocessing phase. This allows for more efficient computation in the subsequent "online" phase.
- Gate-by-Gate Computation: Similar to many MPC protocols, computation proceeds gate-by-gate, with addition gates handled locally and multiplication gates requiring reconstruction of intermediate values.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Robust Secret-Sharing as a Replacement for Dispute Control: The paper demonstrates that robust secret-sharing, when combined with clever batching and compression techniques, can provide the necessary guarantees for G.O.D. in the honest majority setting, circumventing the need for dispute control and its associated $n^2$ round overhead.
- The Power of Batching for Communication Efficiency: The core insight is that by batching the reconstruction of multiple secret-shared values, the communication overhead associated with authentication tags can be amortized, leading to linear communication per secret.
- Bridging the Gap for Honest Majority MPC: This work significantly closes the efficiency gap between MPC protocols for $t < n/3$ and $t < n/2$ in terms of round complexity, making honest majority MPC more practical.
- Circuit Width Requirement: While achieving $O(\text{depth}(C))$ rounds, the protocol requires circuits to have a width of $\Omega(n^2)$, which is a notable difference from the $t < n/3$ case where $\Omega(n)$ width is sufficient. This highlights an area for future research.
Key Results
- $O(\text{depth}(C))$ Round Complexity: The protocol achieves a round complexity that is linear in the depth of the circuit, independent of the number of parties $n$.
- Linear Communication Complexity: The protocol maintains linear communication complexity, $O(n|C|)$, for circuits of width $\Omega(n^2)$.
- Fully Secure G.O.D.: The protocol provides statistically secure, fully secure G.O.D. in the honest majority setting ($t < n/2$).
- Preprocessing Model: The protocol operates in the preprocessing model, requiring correlated randomness.
Limitations and Future Work
- Circuit Width Requirement: The paper acknowledges that their protocol requires circuits to have a width of $\Omega(n^2)$, whereas protocols for $t < n/3$ only require $\Omega(n)$ width. A key future direction is to reduce this gap, ideally to $\Omega(n)$ width for the $t < n/2$ case.
- Constant Number of Rounds: While the paper claims a constant number of rounds in Theorem 1, the proof details and the protocol description (LinRec) suggest a dependency on the number of secrets being reconstructed, which might imply a dependency on $n$ in practice for certain interpretations of "constant number of rounds." However, the primary goal of $O(\text{depth}(C))$ is achieved.
- Field Size: The statistical security parameter $k$ implies a required field size $|F| > \text{poly}(n) \cdot 2^k$. The proof of correctness relies on this field size being sufficiently large to avoid overwhelming probability of error.
Summary updated