Information-Theoretically Secure Three-Party Computation with One Corrupted Party

Ye Wang, Prakash Ishwar, Shantanu Rane

Information-Theoretically Secure Three-Party Computation with One Corrupted Party

Abstract

The problem in which one of three pairwise interacting parties is required to securely compute a function of the inputs held by the other two, when one party may arbitrarily deviate from the computation protocol (active behavioral model), is studied. An information-theoretic characterization of unconditionally secure computation protocols under the active behavioral model is provided. A protocol for Hamming distance computation is provided and shown to be unconditionally secure under both active and passive behavioral models using the information-theoretic characterization. The difference between the notions of security under the active and passive behavioral models is illustrated through the BGW protocol for computing quadratic and Hamming distances; this protocol is secure under the passive model, but is shown to be not secure under the active model.

Introduction

Secure Multiparty Computation (SMC) enables a group of parties to compute a function of their private inputs without revealing any information beyond the final result. Traditionally, security is analyzed against two types of adversaries: Passive (Semi-honest), where parties follow the protocol but attempt to extract extra information, and Active (Malicious), where a party may arbitrarily deviate from the protocol to compromise data or results.

A well-known result in cryptography is that unconditionally secure protocols generally require $t < n/3$, where $t$ is the number of corrupted parties and $n$ is the total number of parties. In a three-party setting ($n=3$), this suggests that even a single active adversary ($t=1$) cannot be tolerated for general functions. This paper challenges that absolute barrier by identifying specific functions, such as Hamming distance, that can be computed securely in this configuration and providing a formal information-theoretic framework for such security.

Methods: The Real vs. Ideal Paradigm

The authors define security using the Real versus Ideal model simulation paradigm. In the Ideal Model, a "trusted genie" receives inputs from Alice and Bob, computes the function, and provides the result to Charlie. In the Real Model, the parties execute a protocol to achieve the same result. A protocol is deemed secure if any attack possible in the real world can be mapped to an equivalent attack in the ideal world.

Comparison of the Real Model (a) and the Ideal Model (b) for secure three-party computation.

The paper's primary contribution is the translation of these simulation requirements into concrete information-theoretic conditions. By using mutual information and probability identities, researchers can mathematically prove security without constructing complex simulators.

To demonstrate this, the authors propose the HamDist protocol:

  1. Masking: Alice generates random masks and a random permutation.
  2. Sharing: She shares these masks with Bob.
  3. Transmission: Alice and Bob send masked, permuted versions of their data to Charlie.
  4. Computation: Charlie computes the Hamming distance from these masked inputs without gaining knowledge of the raw data.

Key Insights and Results

Breaking the $n/3$ Barrier

While general-purpose active security for arbitrary functions requires more than three parties, this work proves that specific functions like Hamming distance are achievable with just three parties. This highlights that the $n/3$ requirement is not an absolute limitation for all computational tasks.

The Active vs. Passive Paradox

A counterintuitive finding is that a protocol secure against an active attacker is not necessarily secure against a passive one. This stems from the "Ideal Model" for active attackers being more permissive; it assumes the attacker could have altered their input regardless. The paper emphasizes this subtle distinction, which is often overlooked in security analysis.

The Failure of the BGW Protocol

The authors demonstrate that the classic BGW protocol (based on Shamir's Secret Sharing) fails in the three-party active model. While BGW is a standard for passive security, an active attacker in a three-party setup can manipulate values to force the final interpolation to produce a result outside the valid range of the function—an outcome impossible in the "Ideal" genie model.

Formal Characterization

The paper provides Theorem 1, the first formal information-theoretic characterization of security for three-party computation with one active adversary. They successfully prove that the proposed HamDist protocol satisfies both active and passive security definitions.

Limitations and Future Work

The current research focuses specifically on Hamming and quadratic distances and does not yet provide a general characterization for all functions computable in the three-party active model. Additionally, the model assumes no collusion between parties. A significant open question remains: whether any protocol can securely compute the quadratic distance under the active behavioral model in a three-party setting.

Summary updated

Abstract

The problem in which one of three pairwise interacting parties is required to securely compute a function of the inputs held by the other two, when one party may arbitrarily deviate from the computation protocol (active behavioral model), is studied. An information-theoretic characterization of unconditionally secure computation protocols under the active behavioral model is provided. A protocol for Hamming distance computation is provided and shown to be unconditionally secure under both active and passive behavioral models using the information-theoretic characterization. The difference between the notions of security under the active and passive behavioral models is illustrated through the BGW protocol for computing quadratic and Hamming distances; this protocol is secure under the passive model, but is shown to be not secure under the active model.
BibTeX
@misc{wang2012information,
  author = {Ye Wang and Prakash Ishwar and Shantanu Rane},
  title = {{Information-Theoretically Secure Three-Party Computation with One Corrupted Party}},
  year = {2012},
  eprint = {1206.2669},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1206.2669},
}
Figure