A Framework for Outsourcing of Secure Computation

Thomas P. Jakobsen, Jesper Buus Nielsen, Claudio Orlandi

TL;DR

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 authors achieve active security (protection against malicious behavior) while ensuring that the client's workload remains minimal and independent of the computation's complexity.

What Problem Does This Paper Address?

Secure Multiparty Computation (MPC) allows parties to compute a function over their private inputs without revealing the inputs themselves. However, traditional MPC protocols face two major hurdles:

  1. Scalability: As the number of participants grows into the thousands or millions, the communication overhead typically scales quadratically, making it impractical for large-scale use.
  2. Resource Constraints: Many users (clients) have limited computing power (e.g., mobile phones) and cannot handle the heavy cryptographic lifting required for complex functions.

Existing "outsourcing" solutions often require a majority of workers to be honest or rely on extremely heavy tools like Fully Homomorphic Encryption (FHE), which are too slow for many real-world applications. The authors aim to bridge this gap by creating a protocol that is fast, generic, and secure even if all but one worker are actively trying to cheat.

Methods

The authors propose a modular framework that can sit on top of any "reactive" MPC protocol (protocols where linear operations like addition are essentially "free"). Their approach uses several key techniques:

  • Secret Sharing: Clients split their inputs into "shares" and distribute them among the workers. No single worker (or even a group of $m-1$ workers) can see the actual data.
  • Algebraic Manipulation Detection (AMD) Codes: To prevent malicious workers from tampering with the inputs, clients attach a special kind of Message Authentication Code (MAC) based on AMD codes.
  • The "Post-Commitment" Key Reveal: This is the paper's most clever trick. Usually, verifying a MAC inside an MPC protocol is computationally expensive. Here, workers first "commit" to the inputs in the MPC. Only after they are committed is the MAC key revealed. This transforms the verification process into a simple linear operation that doesn't bloat the computation circuit.
  • Recursive Conflict Resolution: In the "Malicious Client" extension, the authors provide a recursive algorithm (FIND) to identify which specific client provided a bad input without needing to abort the entire computation for everyone else.

Datasets

Not discussed in the paper. As a theoretical cryptography paper, it focuses on formal security proofs and algorithmic complexity rather than empirical benchmarking on specific datasets.

Key Insights and Ideas

  • Decoupling Input from Computation: The framework separates the "input phase" (getting data from clients to workers) from the "computation phase." This allows the protocol to be used with various underlying MPC engines (like Yao’s garbled circuits or SPDZ).
  • Minimal Interaction: The interaction pattern is optimal. Clients send one message to upload data and receive one message to get the result. They don't need to stay online during the actual computation.
  • The "One Honest Worker" Threshold: By designing for a dishonest majority among workers (requiring only one to be honest), the system is much more robust than "honest majority" systems, which break if just over half the workers collude.
  • Linear Verification: By using AMD codes and revealing the key at the right moment, the authors ensure that the "security tax" paid for verifying input correctness is nearly zero in terms of multiplication gates.

Key Results

  • Security: The protocol is proven secure in the Universally Composable (UC) framework against an active adversary controlling any number of clients and up to $m-1$ workers.
  • Efficiency: Client work is $O(m \cdot \text{input size})$, which is independent of the function $f$ being computed.
  • Communication: The size of the output message from workers to clients is identical to the size of the function's output—there is no cryptographic "bloat" in the final step.
  • Scalability: The framework handles millions of clients efficiently, especially with the recursive FIND algorithm that identifies malicious clients in $O(\log n)$ multiplications.

Limitations and Future Work

  • The "At Least One" Assumption: If every worker is corrupted, the privacy of the inputs is lost. While this is a standard trade-off for efficiency, it remains a trust requirement.
  • Denial of Service: While the protocol ensures that workers cannot cheat and produce a wrong answer, a single malicious worker can still cause the protocol to "abort," effectively performing a denial-of-service attack. The authors address this partially with an "eventual consensus" mechanism, but it doesn't guarantee a result if workers refuse to cooperate.
  • Reactive MPC Dependency: The efficiency gains rely on the underlying MPC protocol having "free" linear operations. If the underlying protocol doesn't support this, the overhead of the MAC verification would increase.

Summary updated

Abstract

We study the problem of how to efficiently outsource a sensitive computation on secret inputs to a number of untrusted workers, under the assumption that at least one worker is honest. In our setting there is a number of clients C_1,…,Cn with inputs x1,…,xn. The clients want to delegate a secure computation of f(x1,…,xn) to a set of untrusted workers W1,…,Wm. We want do so in such a way that as long at there is at least one honest worker (and everyone else might be actively corrupted) the following holds 1) the privacy of the inputs is preserved 2) the output of the computation is correct (in particular workers cannot change the inputs of honest clients). We propose a solution where the clients' work is minimal and the interaction pattern simple (one message to upload inputs, one to receive results), while at the same time reducing the overhead for the workers to a minimum. Our solution is generic and can be instantiated with any underlying reactive MPC protocol where linear operations are ``for free''. In contrast previous solutions were less generic and could only be instantiated for specific numbers of clients/workers.
BibTeX
@inproceedings{jakobsen2014framework,
  author = {Thomas P. Jakobsen and Jesper Buus Nielsen and Claudio Orlandi},
  title = {{A Framework for Outsourcing of Secure Computation}},
  booktitle = {CCSW},
  year = {2014},
  doi = {10.1145/2664168.2664170},
}
Figure