Don't Eject the Impostor: Fast Three-Party Computation With a Known Cheater

Don't Eject the Impostor: Fast Three-Party Computation With a Known Cheater

Speakers: Andreas Brüggemann, Oliver Schick, Thomas Schneider, Ajith Suresh, Hossein Yalame

Conference: IEEE S&P

YouTube: https://www.youtube.com/watch?v=8bJqImUjbtk

Overview

The "Don't Eject the Impostor: Fast Three-Party Computation With a Known Cheater" talk, presented by Andreas Brüggemann and co-authored with Oliver Schick, Thomas Schneider, Ajith Suresh, and Hossein Yalame from TU Darmstadt and TII, addresses a critical gap in the landscape of secure multi-party computation (MPC). The presentation highlights the common real-world scenario where trust between participating parties is inherently asymmetric. Instead of assuming all parties are either perfectly honest (semi-honest) or fully malicious, the research focuses on a practical setting where one specific party is known to be potentially malicious, while the others are assumed to be semi-honest.

This work introduces two novel three-party computation (3PC) protocols, Auxilior and Zocum, designed to offer robust security against a known malicious party without incurring the prohibitive computational and communication costs associated with general malicious 3PC. The motivation stems from applications like secure inference as a service, where a less trustworthy online store interacts with trusted entities like a fintech company and a bank. The protocols leverage an honest majority assumption, allowing for significantly more efficient operations by carefully tailoring verification mechanisms to the specific trust model. By bridging the performance gap between semi-honest and fully malicious MPC, this research provides a practical and efficient solution for secure collaborative computations in diverse, real-world environments.

Background

▶ Watch: Introduction and motivating example for secure inference. (0:00)

The concept of secure multi-party computation (MPC) allows multiple parties to jointly compute a function over their private inputs without revealing those inputs to each other. Traditional MPC models often fall into two main categories: semi-honest (or honest-but-curious) security, where parties follow the protocol but may try to learn extra information from messages received, and malicious security, which protects against any arbitrary deviation from the protocol. While semi-honest protocols are highly efficient, they offer insufficient protection when a party actively tries to cheat. Conversely, fully malicious protocols provide strong guarantees but come with a substantial performance overhead, often deemed too expensive for practical deployment.

The speakers argue that neither of these extreme models perfectly fits many real-world scenarios where trust is asymmetric. For instance, in a secure inference setup involving an online store, a fintech company, and a bank, it's plausible to assume the large institutions (fintech, bank) are semi-honest, while the smaller, potentially numerous online stores might be malicious. Applying a fully malicious 3PC protocol in this case would be overkill and inefficient, as it would protect against malicious behavior from all parties, including the trusted ones. Conversely, a semi-honest protocol would fail if the online store cheats.

While asymmetric trust settings have been explored in two-party computation (2PC), these often involve an inherently dishonest majority and can be very inefficient. The authors highlight that their work specifically addresses asymmetric three-party computation (3PC) under an honest majority assumption, meaning that no two parties collude. This specific setting is crucial because the honest majority allows for more efficient cryptographic techniques, particularly for multiplications, compared to dishonest majority settings. The new protocols build upon existing efficient 3PC protocols like Estra (for semi-honest settings) and Swift (for malicious settings), which already feature a "helper" server and two "evaluator" servers, and provide function-dependent pre-processing and machine learning-friendly building blocks like matrix multiplication and fixed-point arithmetic.

Key Findings

▶ Watch: Asymmetric 3PC setting and core contributions of the work. (4:00)

The core contribution of this research is the introduction of two new 3PC protocols, Auxilior and Zocum, specifically designed for asymmetric trust models where an honest majority exists, and exactly one party is known to be potentially malicious. These protocols offer a significant advancement by providing tailored security guarantees without the typical performance penalties of general malicious MPC.

The key findings and contributions include:

• Two Novel 3PC Protocols:
• Auxilior: Tailored for the scenario where the helper server is malicious.
• Zocum: Designed for the scenario where one of the evaluator servers is malicious.
• Streamlined Online Phase: Both protocols achieve a highly efficient online phase where the bulk of the computation (heavy lifting) is performed by the two trusted evaluator servers, with the remaining server (potentially malicious or just a helper) playing a more limited role. This is particularly valuable for applications requiring fast predictions, such as secure inference.
• Multiple Efficient Pre-processing Options: The protocols support various methods for generating verified multiplication triples and other necessary cryptographic primitives during the computationally intensive pre-processing phase, adapting to the asymmetric trust:
• Triple Sacrificing (Ring Version): Includes a novel Matrix Triple Sacrificing protocol, which is highly efficient for machine learning tasks. This method has low computational overhead but linear communication overhead in the number of multiplication gates.
• Cut-and-Choose: For computations in the binary domain, offering similar overhead characteristics.
• Distributed Zero-Knowledge Proofs (D-ZKPs): Provides a different trade-off, with higher computational overhead for verification but sublinear communication overhead, applicable to both arithmetic and binary domains.
• Machine Learning Friendly Design: The protocols are explicitly designed to be multi-purpose and efficient for machine learning operations, particularly matrix multiplications, by avoiding cubic overheads typically associated with scalar-based verification.
• Performance Bridging the Gap: The research empirically demonstrates that these tailored protocols effectively bridge the performance gap between symmetrical semi-honest and fully malicious models. For example, Auxilior reduces communication overhead from 4x (sacrificing) to 2% (D-ZKPs) compared to semi-honest Estra, while Zocum improves communication by 8.5x (sacrificing) or 1.4x (D-ZKPs) compared to fully malicious Swift. Critically, these protocols avoid the massive overheads (e.g., 600x-2400x for Auxilior, 17x-60x for Zocum) that would result from simply removing the untrusted party and falling back to 2PC, underscoring the importance of maintaining an honest majority.
• Open-Source Implementation: The authors provide an open-source implementation, facilitating adoption and further research. Benchmarks on a 7-layer convolutional neural network (CNN) for MNIST and CIFAR-10 datasets validate their theoretical claims regarding efficiency.

Technical Deep Dive

▶ Watch: Overview of Auxiliatrix and Zorum protocols based on existing MPC. (5:50)

The core innovation of Auxilior and Zocum lies in their intelligent adaptation of existing 3PC protocols (Estra for semi-honest, Swift for malicious) to the asymmetric trust model. Both protocols operate with three parties: a helper server and two evaluator servers. The assumption of an honest majority (no two parties collude) is fundamental, as it allows for more efficient methods of generating and verifying multiplication triples – a cornerstone of MPC for non-linear operations.

Verification Techniques

All expensive verification in Auxilior and Zocum is pushed into the pre-processing phase, ensuring a streamlined and fast online phase. The protocols support several verification options:

1. Triple Sacrificing (Ring Version):

• Standard Process: The idea is to optimistically generate multiplication triples (a, b, c) and then verify that c = a * b. This is done by sacrificing a second, correlated triple (a', b', c'). A random number is sampled, and linear combinations of a and a' (and later b and b') are computed. By recovering these linear combinations and performing a final check (e.g., verifying a sum equals zero over an extended ring), the correctness of the original triple can be proven with high probability.
• Asymmetric Optimization: A key observation is that the computationally intensive verification steps (sampling random values, computing linear combinations, final verification) can be outsourced entirely to the two semi-honest evaluator servers. Since these two servers are trusted not to collude or cheat, they can perform these checks efficiently without involving the potentially malicious party in critical verification steps. This also makes the initial multiplication triple generation cheaper as less data needs to be securely handled.
• Matrix Triple Sacrificing: A novel contribution is the generalization of scalar triple sacrificing to matrix multiplication. Instead of individual scalar values, entire matrices are used. The proof structure remains valid, providing a highly efficient method for generating verified matrix multiplication triples, which is crucial for machine learning applications. This avoids the cubic overhead of naive scalar multiplication when performing matrix operations.

1. Cut-and-Choose: This technique is supported for computations in the binary domain, offering similar low computational overhead and linear communication overhead to triple sacrificing.

1. Distributed Zero-Knowledge Proofs (D-ZKPs): This option offers a different trade-off. While it incurs a higher computational overhead for verification, it achieves sublinear communication overhead. This is beneficial in bandwidth-constrained environments and is applicable to both arithmetic (ring) and binary domains.

Protocol Auxilior: Malicious Helper

Auxilior is based on the semi-honest Estra protocol and addresses the scenario where the helper server is the malicious party. This setup is relevant, for example, if an online store provides limited computing power for pre-processing but wants the online phase to be entirely outsourced to trusted entities (fintech, bank).

• Adaptation from Estra: In Estra's pre-processing phase, certain values (e.g., Lambda_X, Lambda_Y) are additively secret-shared between the two evaluator servers, with the helper holding all shares. To compute a multiplication triple, the helper and one evaluator could traditionally sample one share of the result, and the helper would compute the other share in cleartext and send it.
• Verification Plug-in: Since the helper is now malicious, this trust assumption is broken. The solution is straightforward: a verification step is "plugged in" after the helper sends its share. The two semi-honest evaluator servers perform this verification using one of the techniques mentioned above (e.g., triple sacrificing). The malicious helper might need to provide additional triples or proofs, but the core fix is to add a check between the trusted parties.
• Performance: While Estra is semi-honest, Auxilior introduces an overhead for security. For machine learning, the communication overhead is approximately 4 times higher than semi-honest Estra when using sacrificing. However, if D-ZKPs are employed, the communication overhead can be brought down to only about 2% compared to sacrificing. The speakers emphasize that not ejecting the malicious helper is critical; simply removing it and falling back to 2PC between the two evaluators (losing the honest majority) would result in a massive overhead of over 600 times for sacrificing or 2,400 times for D-ZKPs, demonstrating the efficiency gains of maintaining the 3PC structure.

Protocol Zocum: Malicious Evaluator

Zocum is built upon the malicious Swift protocol and targets the case where one of the evaluator servers is malicious. This scenario might represent a "basic plan" where the online store (malicious evaluator) performs more heavy lifting, while the bank acts as a helper with low online effort.

• Adaptation from Swift: Swift is designed for any party being malicious, leading to symmetric verification mechanisms. Zocum optimizes this by leveraging the fact that only one specific evaluator is malicious.
• Online Phase Optimization: The key optimization in Zocum happens in the online phase. In Swift, when parties want to recover a replicated secret-shared value M, each party sends missing shares to others. For verification, each party also sends a hash of the message it sent to a third party. In Zocum, since only one evaluator is malicious, several of these symmetric hash messages can be removed. More significantly, the semi-honest evaluator (the non-malicious one) is trusted to correctly combine its shares. This means other servers don't need to know some shares, which in turn simplifies and makes the pre-processing (based on replicated secret sharing plus verification) cheaper.
• Truncation Efficiency: The reduction in the number of shares that need to be handled also makes truncation operations significantly cheaper in Zocum compared to Swift. Truncation is essential for fixed-point arithmetic in machine learning.
• Performance: Zocum achieves substantial improvements over general malicious Swift. Communication in machine learning tasks improves by about 8.5 times when using sacrificing, or 1.4 times when using D-ZKPs. Again, the importance of the helper is highlighted: removing the helper and using state-of-the-art 2PC (like Sync, which is fine-tuned for secure inference) would still result in overheads of 17 times (sacrificing) or 60 times (D-ZKPs) compared to Zocum, showcasing the benefits of the 3PC honest majority setting.

Performance Spectrum

The protocols demonstrate a clear performance spectrum:

• Estra (Semi-Honest): Baseline, lowest cost.
• Auxilior (Malicious Helper): Higher cost than Estra, but significantly lower than full malicious.
• Zocum (Malicious Evaluator): Higher cost than Auxilior, but significantly lower than full malicious.
• Swift (Fully Malicious): Highest cost, provides strongest security.

This spectrum is observed across both pre-processing (e.g., 1 ring element for Estra, up to 9 for Swift with sacrificing) and online phase costs. For matrix multiplications, the factors split elegantly, avoiding cubic overhead.

Demo / Proof of Concept

▶ Watch: Cheating detection and prevention through pre-processing options. (6:00)

The practical viability and performance benefits of Auxilior and Zocum were demonstrated through an open-source implementation and extensive benchmarking. The authors implemented all their protocols, along with the foundational Estra and Swift protocols (using sacrifice proofs), making the code publicly available.

The benchmarks focused on secure inference using a seven-layer convolutional neural network (CNN), trained on the MNIST and CIFAR-10 image recognition datasets. This choice of application and network architecture provides a realistic evaluation context for machine learning tasks.

Key observations from the benchmarks included:

• Communication Trends: The benchmarks clearly showed the expected trend in communication costs: Estra < Auxilior < Zocum < Swift. This validates the hypothesis that tailored asymmetric protocols offer a significant efficiency improvement over generic malicious 3PC.
• D-ZKP Trade-off: For distributed zero-knowledge proofs, the communication cost was consistently much lower across all protocols (e.g., 1 ring element for pre-processing in Auxilior, compared to 4 for sacrificing). This confirms the trade-off of higher computation for lower communication.
• Bottlenecks: The primary bottleneck identified in the setup (pre-processing) phase was the nonlinear layers of the CNN. The only exception was Swift when using sacrificing, where linear layers surprisingly became a significant bottleneck due to expensive truncation operations. This highlights how Zocum's optimizations, which make truncation much cheaper, offer a substantial advantage for such computations.
• Runtime Performance: In the LAN setting, the online execution times for all protocols on the CIFAR-10 dataset were remarkably under 2 seconds. This demonstrates that despite the added security, the online prediction phase remains extremely fast. The setup (pre-processing) times, as expected, varied significantly, ranging from just over 1 second for Estra to 12 seconds for Auxilior, 22 seconds for Zocum, and over 33 seconds for Swift. This practical demonstration underscores the real-world applicability of Auxilior and Zocum in scenarios demanding fast inference.

Defensive Implications

▶ Watch: Detailed explanation of novel triple sacrificing verification protocol. (7:10)

The "Don't Eject the Impostor" research offers crucial defensive implications for organizations deploying secure multi-party computation, particularly in complex, multi-party ecosystems where trust levels are heterogeneous.

1. Tailored Security for Cost-Efficiency: Defenders no longer need to choose between inadequate semi-honest security and prohibitively expensive fully malicious security. By accurately assessing the trust level of each participant – identifying a single, potentially malicious party among otherwise semi-honest ones – organizations can deploy Auxilior or Zocum. This allows for achieving the precise level of security needed (protection against one known cheater) at a significantly reduced cost in terms of computation and communication, compared to generic malicious protocols. This is particularly relevant for Secure Inference as a Service (SIaaS), where a service provider might interact with numerous clients, some of whom could be untrustworthy.

1. Maintaining Honest Majority is Key: A critical takeaway for system architects is the importance of maintaining a three-party setup with an honest majority, even when one party is deemed malicious. The research clearly shows that "ejecting" the malicious party and falling back to a two-party computation (which would lose the honest majority) leads to massive performance degradation (hundreds to thousands of times slower). This implies that adding a third, trusted party (even a lightweight "helper") specifically to maintain the honest majority can be a highly effective defensive strategy to achieve both security and efficiency.

1. Optimized Pre-processing for Faster Online Operations: The protocols' design, which offloads all expensive verification to the pre-processing phase and supports efficient methods like Matrix Triple Sacrificing and Distributed Zero-Knowledge Proofs, enables extremely fast online phases. For real-time applications like fraud detection or personalized recommendations via secure inference, this means defenders can get secure predictions within seconds, which is often a non-negotiable requirement for operational deployment.

1. Flexible Verification Trade-offs: The availability of multiple pre-processing verification options (e.g., sacrificing for low compute/linear communication vs. D-ZKPs for high compute/sublinear communication) allows defenders to choose the optimal approach based on their specific resource constraints (CPU vs. network bandwidth). This flexibility empowers organizations to fine-tune their MPC deployments for maximum efficiency within their existing infrastructure.

In essence, this work provides a practical blueprint for building more secure and efficient collaborative systems by acknowledging and strategically addressing the nuances of asymmetric trust, moving beyond the simplistic dichotomy of fully honest or fully malicious assumptions.

Key Takeaways

• Asymmetric Trust is Prevalent: Real-world multi-party computations often involve asymmetric trust, where one party is less trustworthy than others, making traditional semi-honest or fully malicious models suboptimal.
• Tailored 3PC Protocols Bridge the Gap: Auxilior and Zocum are novel 3PC protocols designed for an honest majority setting with one known malicious party, offering a practical balance between security and efficiency.
• Maintaining the Honest Majority is Crucial for Efficiency: Simply removing a malicious party to revert to 2PC leads to massive performance penalties (600x to 2400x overhead), underscoring the benefits of a 3PC setup even with a known cheater.
• Efficient Pre-processing Enables Fast Online Phases: All expensive verification is moved to the pre-processing phase, utilizing techniques like optimized triple sacrificing (including novel matrix triple sacrificing) and distributed zero-knowledge proofs, to ensure a streamlined and fast online computation phase (under 2 seconds for CNN inference).
• Significant Performance Gains: Compared to generic malicious 3PC, Auxilior and Zocum achieve substantial communication reductions (e.g., 8.5x or 1.4x for Zocum, or 2% overhead with D-ZKPs for Auxilior).
• ML-Friendly and Multi-Purpose: The protocols are designed to be efficient for machine learning tasks, particularly matrix multiplications, and are applicable to various other multi-party computation scenarios.

About the Speaker(s)

The talk "Don't Eject the Impostor: Fast Three-Party Computation With a Known Cheater" was presented by Andreas Brüggemann, and is a joint work with Oliver Schick, Thomas Schneider, Ajith Suresh, and Hossein Yalame. The researchers are affiliated with TU Darmstadt and TII, indicating their expertise in secure multi-party computation and cryptographic protocols. Their collaborative work focuses on advancing practical and efficient solutions for real-world security challenges in distributed computing environments.