TL;DR
This paper introduces a more efficient and scalable approach to secure multi-party computation (MPC) in the YOSO (You Only Speak Once) model. By leveraging packed secret-sharing and a slight relaxation of security assumptions (allowing for a small "gap" in adversarial corruptions), they achieve significantly reduced communication complexity, making YOSO MPC more practical for large-scale distributed systems like blockchains.
What Problem Does This Paper Address?
Secure multi-party computation (MPC) allows multiple parties to jointly compute a function on their private inputs without revealing those inputs. However, traditional MPC protocols can be communication-intensive, especially in large-scale settings like blockchains. The YOSO model addresses this by using smaller, rotating committees of parties to perform computations, rather than requiring all parties to participate in every step.
A key challenge in YOSO MPC has been that the communication complexity still scales with the size of these committees. Previous work typically assumed a "honest majority" where at most half the parties in a committee could be corrupt. This paper tackles the problem of achieving better scalability by considering a scenario where the adversary can corrupt slightly less than half the parties in a committee (i.e., $t < n(1/2 - \epsilon)$ for some small $\epsilon > 0$). This "gap" allows for significant efficiency gains, particularly in reducing the communication overhead during the online phase of the computation. Additionally, the paper explicitly considers "fail-stop" adversaries (parties that stop participating rather than acting maliciously), which is a more realistic threat model in large-scale systems and further improves efficiency.
Methods
The core of the paper's contribution lies in combining and adapting existing cryptographic techniques:
- Packed Secret-Sharing: This technique allows multiple secrets to be encoded into a single sharing, significantly reducing communication overhead. The paper extends prior work on packed secret-sharing to the YOSO setting.
- YOSO Model Adaptation: The authors adapt the Turbopack protocol (an efficient non-YOSO MPC protocol) to fit the YOSO model. This involves carefully handling the rotation of committees and ensuring that preprocessed information can be securely passed to future committees without knowing their identities in advance.
- Keys for Future (KFF): To bridge the gap between the offline preprocessing phase (where committee members are unknown) and the online phase (where they are known), the paper uses a "Keys for Future" mechanism. This allows secret information to be encrypted for future roles, which can then be decrypted and re-encrypted for the actual committee members.
- Linearly Homomorphic Key Rerandomizable Threshold Encryption (TE): This cryptographic primitive is used extensively for encryption, decryption, and homomorphic operations during the offline phase.
- Non-Interactive Zero-Knowledge Arguments of Knowledge (NIZKAoK): These are used to prove the correctness of computations performed by parties, ensuring that even with a relaxed corruption threshold, the protocol remains secure.
- Relaxed Corruption Threshold: The key innovation is exploiting the "gap" where $t < n(1/2 - \epsilon)$. This allows for more efficient committee selection and reduces the communication burden.
- Fail-Stop Adversary Support: Explicitly handling fail-stop adversaries, rather than treating them as fully malicious, leads to further efficiency improvements.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- The "Gap" is Key to Scalability: The most significant insight is that a small "gap" in adversarial corruptions (i.e., $t < n(1/2 - \epsilon)$) is not just a minor security relaxation but a crucial enabler for achieving communication complexity that is independent of the committee size in the online phase.
- YOSO and Packed Secret-Sharing Synergy: The paper demonstrates how packed secret-sharing, which is efficient in standard MPC, can be effectively integrated into the YOSO framework to achieve substantial communication savings.
- Fail-Stop Adversaries are Realistic and Exploitable: Recognizing that parties might fail non-maliciously is important for practical systems. The paper shows that this realistic assumption can be leveraged for efficiency gains, unlike previous YOSO work that treated fail-stop parties as fully malicious.
- Committee Size vs. Communication Trade-off: While introducing a "gap" might slightly increase committee sizes, the resulting reduction in online communication is disproportionately large, leading to a net efficiency gain, especially for larger committees.
Key Results
- Constant Online Communication: The proposed YOSO MPC protocol achieves $O(1)$ online communication complexity per gate, independent of the committee size $n$. This is a significant improvement over prior YOSO protocols where communication scaled linearly with $n$.
- $O(n)$ Offline Communication: The offline communication complexity remains $O(n)$ elements per gate, which is comparable to prior work.
- Significant Speedups: The paper demonstrates substantial communication improvements. For example, with 20% global corruptions, their protocol can achieve over $1000 \times$ online communication improvement compared to prior work by using a slightly larger committee (20k vs. 18k).
- Support for Fail-Stop Parties: The protocol is designed to tolerate fail-stop adversaries, which is a more practical security model for large-scale systems.
Limitations and Future Work
- Trusted Setup: The current framework relies on a trusted setup for generating keys, which is a common limitation in many cryptographic protocols. The authors suggest exploring class group-based solutions to remove this trusted setup.
- Preprocessing Inefficiency: The preprocessing phase does not benefit from the packing parameter $k$, which is an inherent limitation inherited from the Turbopack protocol. Removing this limitation is identified as a relevant future work direction.
- Role Assignment Impact: While the paper adapts role assignment mechanisms to accommodate the "gap," further investigation into the impact of this condition on more recent role assignment protocols is suggested.
- Information-Theoretic Security: Exploring the impact of the "gap" in the context of information-theoretic security (without computational assumptions) is proposed as a feasibility study.
Summary updated