Scalable Mixed-Mode MPC

Scalable Mixed-Mode MPC

Speakers: Radhika; Kang Yang; Jonathan Katz; Xiao Wang

Conference: IEEE S&P

YouTube: https://www.youtube.com/watch?v=XinhCD-M8HY

Overview

Multiparty Computation (MPC) is a cryptographic primitive that enables several parties to jointly compute a function on their private inputs without revealing anything beyond the function's output. While traditionally MPC protocols assume either an arithmetic or a Boolean circuit representation for the function, many real-world applications, such as biometric matching, inherently require a combination of both. This necessitates efficient conversion protocols between arithmetic and Boolean shares, a process that has historically been a significant bottleneck in mixed-mode MPC, consuming up to 99% of computation time and communication bandwidth in prior state-of-the-art solutions.

This talk, presented by Radhika, along with collaborators Kang Yang, Jonathan Katz, and Xiao Wang, addresses the critical challenge of scalability and efficiency in mixed-mode MPC, particularly concerning these inter-share conversions. The research introduces novel protocols that dramatically improve the performance of these conversions, making large-scale MPC deployments feasible even in challenging scenarios involving a dishonest majority and a massive number of parties, up to 128 in their benchmarks.

The significance of this work lies in its ability to overcome the quadratic communication complexity that plagued prior solutions, which relied on pairwise communication patterns. By introducing a new multi-party private table lookup protocol with linear communication complexity, the researchers have paved the way for practical and truly scalable mixed-mode MPC. This breakthrough has profound implications for privacy-preserving technologies, enabling more complex computations on sensitive data with unprecedented efficiency and participant numbers.

Background

▶ Watch: Introduction to mixed-mode MPC and conversion challenges (0:00)

Multiparty Computation (MPC) is a cornerstone of privacy-enhancing technologies, allowing a group of participants to collectively compute a function on their private inputs without revealing the inputs themselves. The underlying mathematical representation of the function typically falls into one of two categories: arithmetic circuits or Boolean circuits. Arithmetic circuits are optimized for operations like addition and multiplication, where values are often shared additively among parties (e.g., x = x1 + x2 + ... + xn). In this mode, addition is computationally "free." Conversely, Boolean circuits excel at bitwise operations such as XOR and AND, with values shared using Boolean shares or addition modulo two. Here, XOR operations are free.

Many practical applications, however, naturally require a blend of both arithmetic and Boolean operations. A prime example highlighted in the talk is biometric matching. The initial phase, computing the Euclidean distance between sample points and a dataset, involves numerous additions and multiplications, making an arithmetic circuit representation ideal. Subsequently, determining the minimum distance requires comparisons and multiplexers, which are inherently bitwise operations and thus best handled by a Boolean circuit. This hybrid requirement necessitates mixed-mode MPC, where efficient conversion between arithmetic shares and Boolean shares becomes paramount.

Prior work in mixed-mode MPC, while acknowledging the benefits of combining circuit types, has struggled with the efficiency of these conversion protocols. The speaker noted that with prior state-of-the-art solutions, an astonishing 99% of the total time and communication overhead was spent solely on these conversions. This inefficiency stemmed from several limitations in existing protocols:

• Limited Scalability: Most solutions catered to a very small number of parties (e.g., two or three) or required an honest majority setting, where more than half of the parties are assumed to be honest.
• Quadratic Communication Complexity: Protocols supporting an arbitrary number of parties and corruptions often suffered from communication complexity that was quadratic in the number of parties (O(N^2)). This was primarily due to their reliance on pairwise communication, where each party had to communicate individually with every other N-1 party. This quadratic scaling made them impractical for even moderately large groups of participants.

The challenge, therefore, was to devise conversion methods that could break free from this quadratic communication barrier, achieve scalability to a large number of parties, and maintain strong security guarantees, specifically against a dishonest majority setting (where any number of parties, up to N-1, can be malicious). The core question driving this research was: "Can we do better than pairwise communication and still achieve security for the dishonest majority setting?"

Key Findings

▶ Watch: Our solution: Scalable conversion protocols and GMW circuit (4:00)

The presented work affirmatively answers the critical question of achieving better-than-pairwise communication for scalable mixed-mode MPC in a dishonest majority setting, while guaranteeing security against semi-honest corruptions. The key findings and contributions of this research are multi-faceted:

1. Novel Multi-Party Private Table Lookup Protocol (MP-PTL): A foundational contribution is the design of a new MP-PTL protocol. Unlike prior lookup table protocols that were limited to two parties and relied on oblivious transfer (OT) or distributed point functions (DPF), this new protocol ensures that each party communicates with only one other party in a ring-like structure, rather than with every other party. This innovation is crucial for breaking the quadratic communication barrier.
2. Massive Scalability: Leveraging the MP-PTL as a core component, the developed conversion protocols achieve unprecedented scalability. The researchers were able to run benchmarks for up to 128 parties, demonstrating practical performance across a large number of participants.
3. Linear Communication Complexity: The communication complexity of the new conversion protocols scales linearly with the number of parties (O(N)), a significant improvement over the quadratic complexity (O(N^2)) of prior dishonest majority solutions.
4. Linear Execution Time: The execution time of the conversion protocols also scales linearly with the number of parties, further contributing to their practicality for large-scale deployments.
5. Efficient Multi-Party Garbled Circuits Construction: The work also introduces a multi-party Garbled Circuits construction that achieves linear communication complexity in a dishonest majority setting. This is a notable advancement, as the only prior work with similar asymptotic complexity was confined to an honest majority setting.
6. Significant Performance Speedups: Concrete benchmarks demonstrate substantial performance gains compared to existing state-of-the-art solutions:

• Speed: Up to 20 times faster than Motion and up to 2,000 times faster than MP-Speeds for arithmetic-to-Boolean conversions, starting from four parties. For Boolean-to-arithmetic conversions, performance improvements become noticeable from 16 parties in a LAN setting and from four parties in a WAN setting.
• Communication: Massively outperforms prior works, requiring up to 1,000 times less communication than Motion and up to 8,000 times less communication than MP-Speeds, with significant improvements evident starting from just four parties.

These findings collectively represent a substantial leap forward in the practicality and deployment potential of mixed-mode MPC, making complex, privacy-preserving computations viable for a much broader range of real-world applications and participant scales.

Technical Deep Dive

▶ Watch: Overview of the multi-party private table lookup protocol (5:06)

The core innovation enabling the scalability of mixed-mode MPC lies in the design of a novel Multi-Party Private Table Lookup (MP-PTL) protocol and its application to share conversion.

Multi-Party Private Table Lookup Protocol

The functionality of the MP-PTL protocol is straightforward: given a table T and the shares of an index X, parties want to obtain the shares of T(X). The protocol operates in two distinct phases:

1. Table Rotation and Sharing: The fundamental idea is to "rotate" the table T using a random value R such that all parties obtain shares of a rotated table T' and shares of the rotation value R.
2. Cheap Lookup: Once the rotated table and R are shared, parties can reveal X XOR R. Since R is uniformly random, X XOR R reveals no information about the original index X. This combined value then serves as the index for a very cheap lookup in the rotated table T'. The lookup phase itself requires communicating only a few bits.

The challenge historically lay in the first phase, obtaining the shares of the rotated table. Prior 2-party lookup protocols relied on pairwise oblivious transfer (OT), which is not scalable for multiple parties. To overcome this, the new MP-PTL protocol uses a ring communication structure:

• Assume a table T of size M.
• Party 1 (P1): Encrypts the entries of T using a suitable encryption scheme. It then samples a random rotation value R1 and shuffles the table entries such that the entry originally at index i is now stored at i XOR R1. P1 then sends this shuffled, encrypted table to Party 2.
• Party 2 (P2): Receives the encrypted table. P2 samples its own randomness R2, shuffles the entries further (e.g., i XOR R1 becomes (i XOR R1) XOR R2), and crucially, randomizes the entries of the table before sending it to Party 3. This randomization step is vital to prevent collusion between P1 and P3 from reducing the randomness contributed by P2.
• Subsequent Parties (P3 to Pn): Each party Pi performs similar shuffling and randomization steps, using its own random value Ri, and passes the table to Pi+1.
• Last Party (Pn): The last party holds an encrypted table that is effectively the encryption of the original table T rotated by the combined randomness of all parties (R_total = R1 XOR R2 XOR ... XOR Rn).
• Share Conversion: Finally, a cheap encryption to additive shares protocol is used to obtain the additive shares of this randomly rotated table from the encrypted form.

The communication for the majority of this protocol proceeds in a ring, avoiding pairwise interactions. Although there are N rounds for N parties, the ring structure allows for easy pipelining of operations, meaning N operations can be completed in N+1 rounds, significantly improving throughput.

Boolean to Arithmetic Share Conversion (B2A)

The MP-PTL protocol is then applied to achieve efficient Boolean to Arithmetic (B2A) share conversion. The goal is to convert ZOR shares of an L-bit number X into additive shares of X.

• Bit-wise Conversion: If we consider each bit of X individually, converting the share of a single bit Y from Boolean to arithmetic is a simple lookup in a size-2 table. This table would map 0 -> 0 and 1 -> 1. The MP-PTL protocol can directly use the Boolean share of the bit Y as an index to obtain the additive share of Y from this table.
• The Packing Challenge: A naive application of this for an L-bit number would require L separate size-2 tables. Each entry in these tables would be a ciphertext, which, as the speaker noted, can be very large (e.g., greater than 100 kilobytes). For a 32-bit number, this would mean 32 2 100KB = 6400KB of data, which is impractical.
• Solution: Packing with LWE-based Homomorphic Schemes: The solution lies in using packing features available in LWE-based homomorphic encryption (H) schemes. These schemes allow multiple elements (e.g., N elements) to be packed into a single ciphertext. While traditional random permutation is not possible with packed ciphertexts, H schemes do allow cyclical rotation of the packed entries.
• Permutation via Cyclic Rotation: The talk illustrated how to achieve the necessary permutation for two size-2 tables packed together, a concept extendable to larger tables and more packed elements.
• P1 starts with packed tables, e.g., [0, 1, 0, 1]. This is a public table.
• P1 uses its randomness R1 to shuffle the table in an unencrypted form and then encrypts it, resulting in a single ciphertext representing [A, B, C, D] (where A, B, C, D are the permuted and packed entries). This ciphertext is sent to P2.
• P2 receives the encrypted table T1. P2 samples its randomness R2 (say, X and Y for controlling two tables). To permute the packed entries, P2 locally performs operations using rotations and multiplications. For example, to permute [A, B, C, D] based on X:
• It computes the original ciphertext C_orig = [A, B, C, D].
• It computes C_rot_plus_1 = [B, C, D, A] (cyclic rotation by +1).
• It computes C_rot_minus_1 = [D, A, B, C] (cyclic rotation by -1).
• Then, using its private bit X (part of R2), it computes a linear combination: (1-X) C_orig + X C_rot_plus_1 (simplified example).
• The example shown in the talk for two size-2 tables demonstrated how specific multiplications (e.g., by 0 or 1) with rotated ciphertexts can selectively bring desired elements into the correct positions based on the random bit X. If X=1, it might select [B, A, ...], and if X=0, it selects [A, B, ...].
• All these operations (rotations, ciphertext-plaintext multiplications) are done locally by P2 and do not require additional communication.
• Overall B2A Communication: This packing technique drastically reduces communication. The overall communication complexity becomes 2 L Ciphertext_size / N. The term Ciphertext_size / N becomes a very small constant (e.g., 2 or 4 in their implementation), making the communication linear in the number of bits L and inversely proportional to the number of parties N.

The talk alluded to similar principles being applied to the Arithmetic to Boolean (A2B) share conversion protocol and the multi-party Garbled Circuits construction, but detailed explanations were directed to the full paper. The core idea of avoiding pairwise communication and leveraging ring-based structures with packed homomorphic encryption remains central to these other contributions.

Demo / Proof of Concept

▶ Watch: Mechanism for obtaining shares of the rotated table (6:03)

The talk presented compelling results from their benchmarks, demonstrating the practical efficacy and scalability of their novel protocols. The experiments were conducted for up to 128 parties, showcasing performance in scenarios far exceeding the capabilities of prior solutions.

A key visual presented was a graph illustrating that the Boolean to Arithmetic (B2A) protocol scales linearly with the number of parties. This direct linear dependence is a powerful validation of their design, particularly the success of avoiding pairwise communication and implementing a ring-based communication structure.

For a more concrete comparison, the researchers benchmarked their protocols against established state-of-the-art solutions, specifically Motion and MP-Speeds.

• Execution Time Comparison:
• For the B2A protocol, their solution's performance starts to surpass prior works from 16 parties in a LAN setting. Notably, in a WAN setting, their protocol outperforms prior works starting from just four parties.
• For the Arithmetic to Boolean (A2B) conversion protocols, their solution showed even more significant advantages, being significantly better than both prior works starting from four parties. Concretely, they achieved up to a 20 times speedup when compared to Motion and an impressive 2,000 times speedup when compared to MP-Speeds.

• Communication Comparison:
• The communication efficiency was even more dramatic. A logarithmic graph was used to emphasize the massive improvements.
• Their protocols required significantly less communication, outperforming prior works starting from four parties.
• Quantitatively, they required up to 1,000 times less communication when compared to Motion and up to a staggering 8,000 times less communication when compared to MP-Speeds.

These results unequivocally demonstrate that the proposed scalable mixed-mode MPC protocols are not just theoretically sound but also offer immense practical advantages in terms of both execution time and communication bandwidth, especially as the number of participating parties increases. The concrete speedups and communication reductions underscore the breakthrough nature of this research in making large-scale privacy-preserving computations a reality. The speaker also mentioned that their code implementation would be open-sourced soon, further enabling research and adoption.

Defensive Implications

▶ Watch: Designing Boolean to arithmetic share conversion (8:12)

While this talk focuses on advancements in cryptographic protocol design rather than direct vulnerabilities or attack vectors, its implications for defensive security are substantial and indirect. The primary defensive implication lies in the expanded practicality and deployability of privacy-preserving computation (MPC) for sensitive data.

1. Enabling Secure Data Processing: By making mixed-mode MPC conversions dramatically more efficient and scalable, this work directly facilitates the secure processing of sensitive information that requires both arithmetic and Boolean operations. This means organizations can now realistically consider using MPC for applications like privacy-preserving biometric matching, secure machine learning on distributed datasets, or confidential genomic analysis without incurring prohibitive computational or communication overheads, even with a large number of participating entities. This capability is a crucial defensive tool against data breaches and unauthorized access to raw sensitive inputs.
2. Mitigating Data Exposure Risks: The ability to perform computations on encrypted or shared data ensures that individual private inputs are never revealed to any single party, including the computing parties themselves. This inherently reduces the attack surface for sensitive data, making it a robust defense against insider threats, data leaks during processing, and targeted attacks on central data repositories.
3. Broadening MPC Adoption: The scalability to 128 parties and the significant performance improvements (up to 2000x speedup, 8000x less communication) mean that MPC is no longer limited to niche applications with few participants. This broadens the scope of problems that can be tackled securely, encouraging wider adoption of MPC as a fundamental defensive measure for collaborative data analysis in regulated industries or multi-party consortia.
4. Security in Dishonest Majority Settings: The protocols are designed to be secure even in a dishonest majority setting, where a significant number of parties (up to N-1) might be malicious. This robust security model offers strong guarantees against collusion and malicious behavior, providing a higher level of trust and resilience than protocols requiring an honest majority, which can be a weaker defensive posture in real-world scenarios.

In essence, this research provides security practitioners and architects with more powerful and practical tools to build systems that are "secure by design" when dealing with collaborative computations on private data. It removes a major barrier to entry for MPC, thereby strengthening the overall defensive posture of systems handling sensitive information.

Key Takeaways

• Mixed-mode MPC conversions are a critical bottleneck: Prior state-of-the-art solutions spent up to 99% of resources on converting between arithmetic and Boolean shares, hindering practical deployment.
• Novel Multi-Party Private Table Lookup (MP-PTL) is key: The research introduces a new MP-PTL protocol that shifts communication from quadratic pairwise interactions to an efficient ring structure, enabling linear scalability.
• LWE-based homomorphic encryption packing is crucial for B2A efficiency: Techniques like packing multiple elements into single ciphertexts and using cyclic rotations for permutations drastically reduce communication overhead for Boolean to Arithmetic conversions.
• Achieves linear scalability for dishonest majority: The new protocols scale linearly with the number of parties in both execution time and communication, even in challenging dishonest majority settings, supporting up to 128 parties in benchmarks.
• Dramatically outperforms prior works: The protocols demonstrate significant speedups (up to 2000x) and massive reductions in communication (up to 8000x) compared to Motion and MP-Speeds.
• Enables practical large-scale privacy-preserving computations: This work makes complex applications like privacy-preserving biometric matching and secure machine learning feasible for a large number of participants, fostering wider adoption of MPC.

About the Speaker(s)

The talk was presented by Radhika. The work is a joint effort with Kang Yang, Jonathan Katz, and Xiao Wang, who is Radhika's advisor. The transcript primarily features Radhika as the presenter and does not provide specific titles or affiliations for all named individuals beyond their collaborative roles in this research. The collective expertise of the team is evident in the depth and impact of the presented work on scalable mixed-mode Multiparty Computation.