Client-aided Robust Bit-composition Protocol with Deterministic Cheater Identification in Standard Model

Hikaru Tsuchida, Takashi Nishide

Abstract

Secure Multiparty Computation (MPC) often requires efficient conversion between binary and arithmetic shares, a process known as bit-composition. While existing protocols offer various trade-offs between speed and security, many rely on idealized cryptographic assumptions or probabilistic cheater detection. This paper introduces a novel client-aided bit-composition protocol that achieves deterministic cheater identification in the Standard Model. By utilizing auxiliary helper clients, the protocol ensures private robustness and minimizes online communication to a single round. Comparative analysis demonstrates that the proposed method matches or exceeds the efficiency of state-of-the-art protocols while providing stronger security guarantees.

Introduction

In the field of Secure Multiparty Computation (MPC), different mathematical operations are optimized for different data representations: binary shares for logical operations (like XOR) and arithmetic shares for numerical calculations (addition and multiplication). Bit-composition serves as the essential bridge between these representations.

A significant challenge in this domain is "robustness," or Guaranteed Output Delivery (GOD), which ensures that a system can complete a calculation correctly even if some participants are malicious. Many current robust protocols suffer from three primary flaws: reliance on the Random Oracle Model (an idealized cryptographic assumption), use of probabilistic identification (which may fail to catch a cheater due to statistical luck), or high communication latency requiring multiple rounds.

Methodology

The researchers propose a "client-aided" framework where auxiliary helper clients assist the primary computing parties. This architecture is divided into two distinct phases:

  • Offline Phase: Helper clients generate random "masks" and shares before the actual private data is processed. This pre-computation ensures that the heavy lifting does not impede the live calculation.
  • Online Phase: During the actual computation, the protocol uses these pre-generated shares to perform bit-composition efficiently.

A key innovation is the use of Deterministic Identification. Unlike probabilistic methods, this protocol employs majority voting and hash-based consistency checks to pinpoint malicious parties with 100% certainty. Furthermore, the protocol is proven secure in the Standard Model, making it more theoretically sound for real-world implementation compared to those relying on the Random Oracle Model.

Performance and Comparison

The proposed protocols (Protocols 4, 5, and 7) were evaluated against several state-of-the-art MPC schemes, including FLASH, SWIFT, and Fantastic Four.

Comparison of the proposed protocols with existing state-of-the-art MPC schemes across various security and performance metrics.

As shown in the comparison table above, the proposed work achieves significant improvements:

  • Speed: In the online phase, the protocol requires only a single round of communication. For comparison, the well-known FLASH protocol requires three rounds.
  • Efficiency: Protocol 5 matches the low online communication cost (8k bits) of the most efficient existing methods while providing stronger security guarantees, such as deterministic identification in the standard model.
  • Security: The protocol achieves "private robustness," meaning that even when a cheater is identified and removed, no private information about the honest parties' inputs is leaked.

Application: Iris Recognition

The protocol's utility was demonstrated through a modified version designed for Hamming distance calculations. This has direct applications in privacy-preserving biometric authentication. In an iris recognition service, this protocol allows a user to be authenticated against a database without the server ever seeing the user's actual biometric template, ensuring both system robustness and user privacy.

Conclusion

This work presents a robust and efficient solution for bit-composition in MPC. By leveraging helper clients and deterministic identification within the Standard Model, the authors provide a protocol that is both theoretically sound and practically viable. Future research may focus on reducing the number of required clients or extending the protocol to handle a higher threshold of malicious corruptions without losing the Standard Model proof.

Summary updated

BibTeX
@article{tsuchida2021client,
  author = {Hikaru Tsuchida and Takashi Nishide},
  title = {{Client-aided Robust Bit-composition Protocol with Deterministic Cheater Identification in Standard Model}},
  journal = {J. Inf. Process.},
  year = {2021},
  doi = {10.2197/ipsjjip.29.515},
}
Figure