Secure Multi-Party Computation with a Helper

Johannes Schneider

Abstract

A client wishes to outsource computation on confidential data to a network of parties. He does not trust a single party but believes that multiple parties do not collude. To solve this problem, we use the idea of treating one of the parties as a helper. A helper assists computation only. Often using more parties ensures confidentiality despite more corrupted parties. This does not hold for adding a helper. But a helper can in some cases lower the amount of communication asymptotically to the theoretical minimum of one bit per AND gate, improving significantly on schemes without a helper. It can also allow for very efficient computations of certain functions, as we show for the exponential function with public base.

Introduction

Secure Multi-Party Computation (MPC) is a cornerstone of modern cryptography, enabling multiple entities to compute a joint function over their private inputs without revealing the inputs themselves. Despite its theoretical elegance, practical adoption of MPC has been hindered by significant communication overhead. Traditional protocols often require extensive data exchange between servers, creating a bottleneck for large-scale data processing.

This research addresses the challenge of outsourcing private computations to untrusted cloud environments. Consider a client who utilizes services from multiple providers, such as Google, Amazon, and Microsoft, as illustrated in Figure 1. While the client may not fully trust any single provider, they operate under the assumption that these providers will not collude to compromise data privacy.

The scenario of a client outsourcing computation to multiple cloud providers.

The Helper-Based Architecture

The primary innovation of this work is the introduction of an asymmetric protocol involving a specialized "Helper" role. Unlike standard MPC frameworks where all parties perform identical tasks, this model partitions responsibilities among three distinct roles:

  1. Encrypted Value Holder (EVH): This party stores the encrypted data but does not possess the decryption keys.
  2. Key Holder (KH): This party manages the encryption keys but never has access to the ciphertexts.
  3. Helper: This party facilitates the mathematical operations. It receives blinded values and keys that do not correspond to the same data, allowing it to perform intermediate computations without gaining any knowledge of the underlying secrets.

Efficient AND Gate Protocol

The core of the protocol lies in its handling of boolean AND gates. By decomposing an AND operation ($a \land b$) into four distinct terms and distributing them across the EVH, KH, and Helper, the system can compute the result with minimal interaction.

The detailed protocol for computing an AND gate using a Helper, Key Holder, and Encrypted Value Holder.

As shown in Figure 5, the process involves the client initially sharing encrypted inputs and keys. The parties then exchange blinded intermediate values (like $t_0, t_1, t_2, t_3$) to reconstruct the encrypted result of the AND operation. This specific arrangement allows the protocol to complete in just two rounds of communication.

Key Insights and Performance

The "Helper" paradigm offers several significant advantages over traditional symmetric MPC:

  • Reaching the Theoretical Floor: By amortizing the cost of sharing variables across multiple gates, the communication overhead can be reduced to just one bit per AND gate. This represents a 3x improvement over state-of-the-art three-party protocols, which typically require at least three bits.
  • Round Complexity: Most fundamental operations, including XOR and AND, are optimized to complete in only two rounds, minimizing latency.
  • Storage Efficiency: The split between EVH and KH allows for storage requirements comparable to two-party protocols, as no single party needs to store a full share of the entire dataset.
  • Algebraic Optimization: Beyond boolean circuits, the framework enables highly efficient computation of complex numerical functions. For instance, exponential functions ($a^x$) are computed directly using mathematical identities rather than being decomposed into thousands of logic gates.

Security Considerations and Limitations

The security of this framework is predicated on a "non-collusion" assumption. Specifically, the system is compromised if the Helper colludes with either the Key Holder or the Encrypted Value Holder. The current model is designed for "semi-honest" participants—those who follow the protocol but may attempt to learn information from the data they see. To formalize these guarantees, the authors provide a security mapping (Theorem 1) that relates their "distrust attacker" model back to standard MPC security definitions.

Furthermore, while the protocol supports gates with multiple inputs (large fan-in) in constant rounds, the message size grows exponentially with the number of inputs ($2^w$), making it less practical for very wide gates.

Conclusion

By introducing a specialized Helper role, this research demonstrates that it is possible to significantly reduce the communication bottlenecks inherent in Secure Multi-Party Computation. Achieving the theoretical minimum of one bit per AND gate paves the way for more scalable and efficient privacy-preserving data analysis in multi-cloud environments. Future work will focus on extending these techniques to a broader range of functions and enhancing robustness against malicious actors.

Summary updated

Abstract

A client wishes to outsource computation on confidential data to a network of parties. He does not trust a single party but believes that multiple parties do not collude. To solve this problem, we use the idea of treating one of the parties as a helper. A helper assists computation only. Often using more parties ensures confidentiality despite more corrupted parties. This does not hold for adding a helper. But a helper can in some cases lower the amount of communication asymptotically to the theoretical minimum of one bit per AND gate, improving significantly on schemes without a helper. It can also allow for very efficient computations of certain functions, as we show for the exponential function with public base.
BibTeX
@misc{schneider2015secure,
  author = {Johannes Schneider},
  title = {{Secure Multi-Party Computation with a Helper}},
  year = {2015},
  eprint = {1508.07690},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1508.07690},
}
Figure