Efficient Three-party Computation: An Information-theoretic Approach from Cut-and-Choose

Zhili ChenarXiv 2019 · OpenReview

TL;DR

This paper introduces the first information-theoretic secure three-party computation (3PC) protocol that uses the cut-and-choose technique to achieve security against one malicious party. The proposed protocol offers a significant reduction in communication rounds compared to existing malicious 3PC protocols while maintaining computational costs comparable to semi-honest 3PC protocols.

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 anything beyond the output. While significant progress has been made in achieving efficient MPC, particularly for two-party computation (2PC) against malicious adversaries using techniques like cut-and-choose, extending these to information-theoretic security for three-party computation (3PC) has been an open challenge. Existing 3PC protocols often focus on the semi-honest setting, where parties follow the protocol but might try to learn more than allowed. Adapting cut-and-choose, a powerful technique for handling malicious adversaries in the computational setting, to the information-theoretic 3PC setting, especially with only one corrupted party (an "honest majority" scenario), was unclear. This paper aims to bridge this gap by developing an information-theoretic 3PC protocol that leverages cut-and-choose to tolerate a single malicious participant.

Methods

The core of the proposed solution is a novel adaptation of the cut-and-choose paradigm for information-theoretic 3PC. The protocol operates in four phases:

  1. Input Preparation: Each of the three parties (P1, P2, P3) prepares two versions of their input: their true input and a randomly generated input of the same length. They then create s copies of their input, where each copy contains either the true or the random input, permuted according to a private random permutation vector. This is crucial for later verification. They also generate a share of a "cut-and-choose indicator" and commit to their true input and this share.
  2. Circuit Computation: The parties run s parallel instances of a semi-honest 3PC protocol. A specially designed "input selection circuit" uses the cut-and-choose indicator (which is cooperatively determined but unknown to individual parties) to select either the true or random inputs for each of the s runs. Runs selected for "computation verification" use random inputs, while runs for "output computation" use the true inputs. This ensures that a malicious party cannot easily tamper with inputs without being detected.
  3. Transcript Commitment: After computing all s circuit instances, each party commits to the transcripts (all wire states) of every run. This commitment phase uses a novel three-party commitment scheme based on Shamir's secret sharing, which is shown to be perfectly binding and perfectly hiding.
  4. Output Generation: The cut-and-choose indicator is revealed. For runs designated for computation verification (where the indicator bit is 1), parties reveal their input shares. This allows for consistency checks: if a party's revealed input doesn't match their random input, they are detected. For these verification runs, parties also reveal their internal state and output shares, allowing for a full check of the circuit's correctness. For runs designated for output computation (where the indicator bit is 0), only the output shares are revealed, and the final output is reconstructed. If any inconsistencies are found at any stage, the protocol aborts.

The key novelty lies in adapting cut-and-choose, typically used for compiling computationally secure protocols, to the information-theoretic setting for 3PC. This involves carefully managing input preparation, using a cooperative but private cut-and-choose indicator, and employing a robust three-party commitment scheme.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Cut-and-Choose for Information-Theoretic 3PC: The paper demonstrates that the cut-and-choose technique, previously confined to computational security, can be effectively adapted to achieve information-theoretic security in 3PC. This opens new avenues for designing secure MPC protocols.
  • Balancing Privacy and Correctness: The protocol cleverly uses two types of inputs (true and random) and a cut-and-choose indicator to ensure both privacy (by hiding true inputs during verification) and correctness (by verifying computations with random inputs and then computing the final output with true inputs).
  • Cooperative but Private Indicator: The cut-and-choose indicator is generated cooperatively by all three parties, preventing any single party from knowing which runs are for verification and which are for output. This is crucial for preventing a malicious party from manipulating the process.
  • Efficient Malicious Security: The protocol achieves malicious security at a computational cost only slightly higher than semi-honest 3PC protocols and significantly reduces communication rounds compared to other information-theoretic malicious 3PC protocols.
  • Novel Three-Party Commitment Scheme: The paper introduces and analyzes a three-party commitment scheme based on Shamir's secret sharing, which is essential for the protocol's security and efficiency.

Key Results

  • Information-Theoretic Secure 3PC: The paper presents the first information-theoretic 3PC protocol that tolerates one malicious party using the cut-and-choose paradigm.
  • Cheating Probability: The protocol achieves a cheating probability of $2^{-s}$, where s is the statistical parameter (number of circuit runs). This means that by increasing s, the probability of a malicious party successfully cheating undetected can be made arbitrarily small.
  • Efficiency: The computational cost is only a small constant factor worse than state-of-the-art semi-honest 3PC protocols. The communication rounds are significantly reduced compared to other information-theoretic malicious 3PC protocols, being proportional to the circuit depth plus a constant.

Limitations and Future Work

  • Single Malicious Party: The current protocol is designed to tolerate only one malicious party. Extending it to tolerate multiple malicious parties would require further research.
  • Computational Security vs. Information-Theoretic Security: The paper notes that for practical applications where computational security is sufficient, the protocol can be made more efficient by using pseudo-random generators for commitments and transcripts, trading information-theoretic security for better performance.
  • Generalization: While the protocol is presented for Boolean circuits, future work could explore its applicability to other types of functions or more general MPC settings.
  • Covert Security: The paper mentions that the protocol can be converted into one against covert adversaries by choosing an appropriate value for s, offering a practical trade-off between security guarantees and efficiency.

Summary updated

Abstract

As far as we know, the literature on secure computation from cut-and-choose has focused on achieving computational security against malicious adversaries. It is unclear whether the idea of cut-and-choose can be adapted to secure computation with information-theoretic security. In this work we explore the possibility of using cut-and-choose in information theoretic setting for secure three-party computation (3PC). Previous work on 3PC has mainly focus on the semi-honest case, and is motivated by the observation that real-word deployments of multi-party computation (MPC) seem to involve few parties. We propose a new protocol for information-theoretically secure 3PC tolerating one malicious party with cheating probability $2^{-s}$ using $s$ runs of circuit computation in the cut-and-choose paradigm. The computational cost of our protocol is essentially only a small constant worse than that of state-of-the-art 3PC protocols against a semi-honest corruption, while its communication round is greatly reduced compared to other maliciously secure 3PC protocols in information-theoretic setting.
BibTeX
@misc{chen2019efficient,
  author = {Zhili Chen},
  title = {{Efficient Three-party Computation: An Information-theoretic Approach from Cut-and-Choose}},
  year = {2019},
  eprint = {1908.03718},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1908.03718},
}

Loading related content...

Figure