Introduction
Secure Multiparty Computation (MPC) is a cornerstone of modern cryptography, enabling multiple parties to compute functions over private data without compromising confidentiality. However, traditional MPC protocols often struggle with scalability and high resource requirements for clients. This paper introduces a highly efficient framework for outsourcing sensitive computations to a group of untrusted workers. By assuming that at least one worker remains honest, the proposed protocol achieves active security while ensuring that the client's workload remains minimal and independent of the computation's complexity.
The Outsourcing Challenge
Existing MPC solutions face two primary hurdles:
- Scalability: Communication overhead typically scales quadratically with the number of participants, making large-scale deployment impractical.
- Resource Constraints: Clients with limited computing power, such as mobile devices, cannot handle the heavy cryptographic operations required for complex functions.
While previous "outsourcing" solutions exist, they often rely on an honest majority of workers or computationally expensive tools like Fully Homomorphic Encryption (FHE). The authors aim to bridge this gap with a protocol that is fast, generic, and secure even if all but one worker are actively malicious.
Methodology: A Modular Framework
The proposed framework is designed to be modular, sitting atop any "reactive" MPC protocol where linear operations (like addition) are computationally inexpensive. Key technical innovations include:
- Secret Sharing and AMD Codes: Clients distribute input "shares" among workers. To prevent tampering, inputs are protected with Algebraic Manipulation Detection (AMD) codes.
- Post-Commitment Key Reveal: To avoid the high cost of verifying Message Authentication Codes (MACs) within the MPC, workers first commit to inputs. The MAC key is revealed only after commitment, simplifying verification into a linear operation that does not bloat the computation circuit.
- Recursive Conflict Resolution: For scenarios involving malicious clients, a recursive algorithm (FIND) identifies bad inputs in $O(\log n)$ multiplications, allowing the computation to proceed without a full abort for the entire system.
Comparative Analysis and Results
The framework's efficiency and security are best understood in comparison to existing literature. As shown in Table 1, the proposed protocol ("This") offers active security for any number of clients ($n$) and any number of workers ($m > 1$), without requiring client interaction during the computation phase. Unlike several competing protocols, it does not rely on non-collusion assumptions between specific sets of workers.
Key results include:
- Minimal Client Work: Client overhead is $O(m \cdot \text{input size})$, making it independent of the function's complexity.
- Optimal Communication: The final output message size is identical to the function's output, eliminating cryptographic "bloat."
- Robust Security: The protocol is proven secure in the Universally Composable (UC) framework against a dishonest majority of workers (requiring only one honest worker).
Conclusion
While the framework provides significant advancements in efficiency and security, it relies on the assumption that at least one worker is honest. Additionally, while it prevents cheating, a single malicious worker can still cause a denial-of-service by forcing an abort. Future work may focus on enhancing robustness against such disruptions and further optimizing the underlying reactive MPC dependencies to ensure broader applicability.
Summary updated