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.
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