Secure Computation Framework for Multiple Data Providers Against Malicious Adversaries

Zhili Chen, Xin ChenarXiv 2020 · OpenReview

TL;DR

This paper introduces a novel secure computation framework designed for multiple data providers, specifically addressing the challenge of malicious adversaries. By cleverly combining garbled circuits and a cut-and-choose approach, it enables secure joint computation of data while ensuring privacy and integrity, even when some participants are untrustworthy. The framework is demonstrated to be effective and practical for scenarios like secure cloud resource auctions.

What Problem Does This Paper Address?

In today's data-driven world, many organizations want to pool their data for joint analysis or computation, but doing so securely is a significant challenge. Secure multi-party computation (SMC) offers solutions, but existing schemes often fall short when dealing with "malicious adversaries" – participants who actively try to cheat or disrupt the computation. This is particularly problematic in scenarios like cloud resource auctions, where multiple providers might offer bids, and a malicious party could try to gain an unfair advantage or leak sensitive information. Previous secure auction protocols typically only protected against "semi-honest" adversaries (who follow the protocol but try to learn extra information), leaving them vulnerable to more sophisticated attacks. This paper aims to bridge this gap by providing a framework that is secure even in the presence of malicious participants, including the computation parties themselves or a subset of the data providers.

Methods

The core of this framework relies on two key cryptographic techniques:

  • Garbled Circuits: This is a standard technique in SMC where a function is "garbled" into a circuit. Two parties can then compute this function on their private inputs without revealing those inputs to each other. The novelty here is running two independent garbled circuits of the same computation.
  • Cut-and-Choose: This is a general technique for achieving security against malicious adversaries. In this framework, it's ingeniously adapted for input consistency checking.

Here's how they are combined:

  1. Input Consistency Check (Cut-and-Choose): Each data provider generates two sets of input encodings and labels, one for each of the two garbled circuits. They commit to these inputs. The computation parties then randomly select some of these commitments to "check" (opening them to verify correctness) and use the rest for "evaluation." This process ensures that a data provider cannot submit different inputs to the two circuits without being detected. A "cheating proof" mechanism identifies malicious providers.
  2. Maliciously Secure Computation (Two Garbled Circuits): The two independent garbled circuits are run. Crucially, the roles of the two computation parties (P1 and P2) are swapped for each circuit. P1 acts as the garbler for one circuit and the evaluator for the other, and vice-versa for P2. This symmetry, combined with the fact that neither party learns the other's inputs or the final output during computation, provides security against a malicious computation party.
  3. Output Verification: After the computations, the output labels and encodings from both circuits are committed. Each data provider then receives the relevant commitments and decodes the results from both circuits. By comparing these two versions of their output, they can verify its correctness. If the outputs don't match, it indicates a problem, and the data provider can present a proof of this discrepancy.

Datasets

Not discussed in the paper. The paper focuses on a theoretical framework and its application to a simulated cloud resource auction, rather than training on specific datasets.

Key Insights and Ideas

  • The Power of Two Garbled Circuits: Running two identical garbled circuits with swapped roles for the computation parties is a surprisingly effective way to achieve malicious security without relying on more complex protocols or oblivious transfers.
  • Cut-and-Choose for Input Integrity: Adapting the cut-and-choose paradigm for input consistency checking is a clever way to detect and prove malicious behavior from data providers. This is a critical step for ensuring the overall integrity of the computation.
  • Separation of Concerns for Security: The framework meticulously separates input handling, computation, and output verification. This modular design allows each phase to contribute to the overall security without compromising the others. For instance, computation parties don't learn inputs or outputs, and data providers verify outputs independently.
  • Practicality for Auctions: The framework's ability to handle multiple data providers and its security against malicious adversaries make it particularly well-suited for real-world applications like cloud resource auctions, where fairness and privacy are paramount.

Key Results

  • Theoretical Security: The paper provides a theoretical proof that the framework is secure against malicious computation parties (P1 or P2) and malicious data providers.
  • Practical Implementation: The framework was implemented and tested using a secure cloud resource auction scenario.
  • Performance: Experimental evaluations showed that the performance of the proposed framework is "acceptable in practice." Specifically:
  • Running time and communication overhead are largely unaffected by the number of instances per VM type (k).
  • Performance scales linearly with the number of VM types (m).
  • Performance scales super-linearly with the number of bidders (n).
  • For hundreds of bidders, running times were in the tens of minutes, and communication overhead in the thousands of MB, which is deemed acceptable for small-scale applications.

Limitations and Future Work

  • Scalability with Bidders: While the framework is secure, the super-linear scaling with the number of bidders (n) suggests that performance might become a bottleneck for very large-scale auctions or computations with a massive number of participants.
  • Efficiency of Garbled Circuits: The paper mentions that the framework is compatible with standard garbled circuit optimizations (like Free-XOR), but further research into more efficient garbled circuit constructions could improve overall performance.
  • Generalizability: While presented as a general framework, its direct application to other complex SMC problems might require further adaptation and analysis.
  • Future Work: The authors suggest that their framework can be extended to support more complex scenarios and that further optimizations for performance are always welcome. The compatibility with techniques like reusable encrypted values (mentioned in [25]) is also a promising avenue for future work.

Summary updated

Abstract

Due to the great development of secure multi-party computation, many practical secure computation schemes have been proposed. As an example, different secure auction mechanisms have been widely studied, which can protect bid privacy while satisfying various economic properties. However, as far as we know, none of them solve the secure computation problems for multiple data providers (e.g., secure cloud resource auctions) in the malicious security model. In this paper, we use the techniques of cut-and-choose and garbled circuits to propose a general secure computation framework for multiple data providers against malicious adversaries. Specifically, our framework checks input consistency with the cut-and-choose paradigm, conducts maliciously secure computations by running two independent garbled circuits, and verifies the correctness of output by comparing two versions of outputs. Theoretical analysis shows that our framework is secure against a malicious computation party, or a subset of malicious data providers. Taking secure cloud resource auctions as an example, we implement our framework. Extensive experimental evaluations show that the performance of the proposed framework is acceptable in practice.
BibTeX
@misc{chen2020secure,
  author = {Zhili Chen and Xin Chen},
  title = {{Secure Computation Framework for Multiple Data Providers Against Malicious Adversaries}},
  year = {2020},
  eprint = {2007.14915},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2007.14915},
}
Figure