Asterisk: Super-fast MPC with a Friend

Asterisk: Super-fast MPC with a Friend

Speakers: Banashri Karmakar, Nishat Koti, Arpita Patra, Sikhar Patranabis, Protik Paul, Divya Ravi

Conference: IEEE S&P

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

Overview

The talk "Asterisk: Super-fast MPC with a Friend" introduces a novel approach to Multi-Party Computation (MPC) that significantly enhances efficiency and security guarantees by incorporating a semi-honest "helper" party. Presented by a team of researchers including Banashri Karmakar, Nishat Koti, Arpita Patra, Sikhar Patranabis, Protik Paul, and Divya Ravi, this work addresses long-standing challenges in balancing the computational cost, communication overhead, and security resilience of MPC protocols. The core innovation lies in a new threat model that bridges the gap between traditional honest-majority and dishonest-majority MPC paradigms, offering the best features of both.

The research presents an impossibility proof for certain adversarial scenarios while demonstrating a highly efficient and scalable protocol for a more practical "either-or" model. This model assumes that either the helper party is semi-honest, or a majority of participating parties are malicious, but not both simultaneously. The protocol, named Asterisk, achieves fairness—a stronger security guarantee than typically available in dishonest-majority settings—without relying on complex cryptographic hardness assumptions. The practical implications are showcased through its application to dark pools, a critical financial mechanism requiring high privacy and integrity.

The significance of Asterisk extends to various privacy-preserving applications where a central, albeit not fully trusted, entity can facilitate computation. By demonstrating substantial performance improvements in both pre-processing and online phases, Asterisk paves the way for more widespread adoption of MPC in real-world scenarios that demand both strong privacy and computational practicality. This work is a crucial step towards making advanced cryptographic techniques accessible and efficient for sensitive data computations.

Background

▶ Watch: Introduction to MPC and its security goals (0:00)

Multi-Party Computation (MPC) allows a set of mutually distrusting parties to jointly compute a function on their private inputs without revealing those inputs to each other. This cryptographic primitive is crucial for scenarios where data privacy is paramount, such as collaborative data analysis, secure auctions, and financial transactions. MPC protocols provide fundamental security guarantees: correctness, ensuring the output is accurate, and privacy, ensuring that a corrupt (adversarial) party learns nothing beyond the final output.

MPC protocols are typically categorized based on two main factors: the security guarantees they offer and the adversary's power. Regarding security guarantees, protocols range from weakest to strongest:

1. Security with abort: An adversary can prevent honest parties from learning the output while still learning it themselves.
2. Fairness: An adversary can still abort the protocol, but if they do, they also cannot learn the output. Either all parties get the output, or no one does.
3. Guaranteed Output Delivery (GOD): All honest parties always receive the output, regardless of the adversary's strategy.

Regarding adversary power, protocols are classified by the number of parties an adversary can corrupt:

1. Honest majority: Security is preserved only if fewer than half of the participating parties are corrupt. These protocols are generally more efficient and can achieve stronger guarantees like fairness and GOD.
2. Dishonest majority: These protocols can withstand corruption of all but one party. However, they are typically less efficient (higher computation and communication costs) and, in this setting, it's generally impossible to achieve fairness or GOD.

The inherent trade-off between resilience (number of corruptible parties) and efficiency/security guarantees presents a significant challenge. Honest majority offers strong guarantees but limited resilience, while dishonest majority offers high resilience but weaker guarantees and higher costs. The existing literature highlights this dichotomy, leading to a gap where applications requiring both high resilience and strong security often face practical limitations.

To bridge this gap, Asterisk introduces an alternate model that incorporates a helper node into the MPC computation. This helper party is initially the centralized service provider in an insecure computation model but is integrated into the MPC protocol. Crucially, privacy must still be maintained even against this helper party, which is modeled as semi-honest. This model is particularly suitable for scenarios where a centralized governing entity maintains system integrity, such as a dark pool where a Security and Exchange Commission (SEC) could act as the helper party. A dark pool is a private forum for trading securities, where order information is kept confidential to prevent market manipulation.

The research considers various relationships between the semi-honest helper party and a malicious adversary corrupting a majority of other parties:

• Simultaneous and Colluding: Prior work has proven that achieving fairness and GOD is impossible in this strongest adversarial model.
• Simultaneous but Non-colluding (Malicious adversary sends non-protocol messages to helper): Asterisk provides an impossibility proof for fairness and GOD even in this slightly weaker model.
• "Either-or" Model: Either the helper party is semi-honest, OR the malicious adversary corrupts a majority of parties (but not both simultaneously). This is the model Asterisk focuses on, proving it is possible to achieve stronger security guarantees like fairness and GOD efficiently. This model allows for higher resilience, better efficiency, and is computationally lightweight, drawing advantages from both honest-majority and dishonest-majority paradigms.

Key Findings

▶ Watch: Introducing the helper node model for efficient MPC (3:00)

The Asterisk project yielded several significant findings across theoretical impossibility, practical protocol design, and empirical performance:

1. Impossibility Proof for Concurrent Adversaries: The work formally demonstrates an impossibility result for achieving fairness and Guaranteed Output Delivery (GOD) in a model where a semi-honest helper party and a malicious adversary (corrupting a majority of parties) exist simultaneously and are non-colluding, but the malicious adversary can still send its complete view (non-protocol messages) to the helper party. This finding clarifies the boundaries of what is achievable in multi-adversary MPC settings.

1. Achieving Fairness in the "Either-Or" Model: In contrast to the impossibility result, Asterisk proves that if the adversaries operate in an "either-or" fashion—meaning either the helper party is semi-honest, or a majority of parties are malicious, but not both simultaneously—then it is possible to achieve fairness for any generic number of parties (n). This is a crucial advancement, as fairness is a stronger security guarantee typically difficult to achieve in dishonest-majority settings. The talk also notes that enhancing this to GOD is "not that difficult," but would nullify the purpose of MPC if it relies on the helper computing the final function in case of abort.

1. Exceptional Efficiency and Scalability: The construction presented in Asterisk is "extremely efficient" and "scalable with the number of parties." It is described as being "as efficient as honest majority" protocols, a remarkable achievement given the higher resilience it offers. Critically, the protocol does not rely on any cryptographic hardness assumptions, contributing to its robustness and long-term security.

1. Significant Performance Improvements:

• Compared to Dishonest Majority Protocols: Asterisk improves the security guarantee from abort to fairness while reducing pre-processing communication cost by at least a factor of N. For 5 parties, it shows communication improvements of 352 times over mCut, 306 times over Overdrive, and close to 7 times over Assisted MPC. In terms of throughput (multiplication triples generated per unit time), it achieves 288 times improvement over mCut, 228 times over Overdrive, and close to 3 times over Assisted MPC.
• Compared to Honest Majority Protocols: Asterisk enhances resiliency from honest majority to "close to dishonest majority" without incurring additional cost. In some cases, its total cost is slightly better, requiring 2N + 3 elements compared to mClan's 3N elements.
• Scalability to 100 Parties: Benchmarks for up to 100 parties demonstrate that Asterisk significantly outperforms state-of-the-art assisted MPC protocols in both runtime and communication during the pre-processing phase, even on a logarithmic scale.
• Online Phase Performance: While showing a slightly higher runtime than implementations in the popular MP-SPDZ framework (attributed to optimization differences in MP-SPDZ), Asterisk consistently outperforms both dishonest majority and honest majority constructions (e.g., Atlas) in terms of communication during the online phase.

1. Suitable Application to Dark Pools: The project successfully applies its framework to the critical problem of dark pool matching, a financial application requiring high privacy for buyer and seller information. The team implemented and benchmarked two popular dark pool algorithms:

• Continuous Double Auction: In a server-outsourced setting with 5 parties, matching 500 buy and 500 sell requests took approximately 16 seconds with less than 1.8 MB of total communication.
• Volume Matching: With 50 buyers and 50 sellers all participating in the MPC protocol, the matching was completed in less than 2 minutes with less than 2.5 MB of total communication. These results demonstrate the practical viability of Asterisk for real-world, sensitive applications.

Technical Deep Dive

▶ Watch: Summary of Asterisk's main results and contributions (5:30)

The Asterisk protocol is built upon fundamental MPC primitives, specifically tailored for efficiency and robustness in the presence of a semi-honest helper party. Any computation can be represented as an arithmetic circuit, comprising addition and multiplication gates. The evaluation proceeds by secret sharing inputs, performing operations on these shared inputs, and then reconstructing the output.

The core of Asterisk's technical construction lies in its specialized secret sharing semantics:

1. Additive Secret Sharing: A secret X is split into n components, x_1, ..., x_n, such that X = Σ x_i. Each component x_i individually appears random. This scheme is chosen for its linearity and its ability to withstand n-1 corrupt parties when combined with authentication.

1. Authenticated Additive Sharing: To ensure integrity against malicious adversaries, additive shares are authenticated using an information-theoretic MAC. A global key Δ is shared among parties. For a secret X, the corresponding tag is T_X = Δ * X. An authenticated share of X consists of additive shares of X, additive shares of the global key Δ, and additive shares of the tag T_X. This allows parties to verify the correctness of shared values.

1. Masked Secret Sharing (MK Secret Sharing): Asterisk utilizes a unique masked secret sharing scheme designed for its pre-processing and online paradigm. A secret X is conceptually split into two components:

• A masked value (M_X = X + Δ_X), which is revealed in the online phase.
• A random mask (Δ_X), whose authenticated sharing is generated during the pre-processing phase.

The invariant maintained throughout the computation is that the masked value is available to all parties, while the random mask's authenticated shares are distributed. An authenticated share of the mask Δ_X comprises additive shares of Δ_X, Δ, and T_{Δ_X} = Δ * Δ_X.

The protocol execution is divided into distinct pre-processing and online phases:

Input Gate Processing:

• Pre-processing: For an input V, a random mask Δ_V is prepared. Its authenticated sharing is distributed to all parties. The helper party then sends the mask Δ_V to the input provider dealer (PD).
• Online Phase: The input provider dealer (PD) computes the masked value M_V = V + Δ_V and sends M_V to all parties. The challenge here is efficiently generating the authenticated sharing of Δ_V.

Addition Gates:

• Since the underlying secret sharing is linear, addition gates are straightforward. Parties can perform additions non-interactively on their shares to obtain the sharing of the sum.

Multiplication Gates:

• Multiplication gates are more complex, requiring interaction and leveraging the pre-processing phase. Let X and Y be masked secret-shared inputs, and Z = X * Y be the desired output.
• Pre-processing: The helper party prepares the mask of Z, denoted Δ_Z, and an intermediate product Δ_{XY} = Δ_X * Δ_Y. Authenticated sharings of Δ_{XY} and Δ_Z are then distributed to the parties.
• Online Phase: Parties aim to compute the masked value M_Z = Z + Δ_Z. They have access to M_X, M_Y, and the authenticated shares of Δ_X, Δ_Y, Δ_{XY}, and Δ_Z. The target equation is M_Z = (M_X - Δ_X)(M_Y - Δ_Y) + Δ_Z. By expanding this, M_Z = M_X M_Y - M_X Δ_Y - M_Y Δ_X + Δ_X Δ_Y + Δ_Z. All terms are available or can be derived from the masked values or authenticated shares, except for Δ_X, Δ_Y, and Δ_X Δ_Y. The protocol cleverly uses the authenticated shares of Δ_X, Δ_Y and Δ_{XY} to derive the necessary components. Specifically, parties compute authenticated shares of M_Z using this relation. One designated party (e.g., P1) reconstructs the masked value M_Z from these shares and sends it to all other parties.

Output Reconstruction:

• At the end of the computation, all parties possess the masked value M_V for the output and authenticated shares of the corresponding mask Δ_V. To obtain the clear output V, they need Δ_V.
• A crucial step is the Mac check. All parties, including the helper, perform a check based on a random linear combination of the secret-shared values. If the check passes (helper obtains 1), the helper releases the mask Δ_V to all parties. If it fails (helper obtains 0), it indicates a malicious act, and all parties abort. This mechanism ensures fairness: either everyone gets the output, or no one does.

Optimized Generation of Authenticated Shares:

• Initially, generating authenticated shares of V (and T_V) would involve the helper computing T_V = Δ * V, then sampling n shares for V and T_V and sending (v_i, t_{v_i}) to each party P_i. This requires 2N elements of communication.
• Asterisk optimizes this using a common key setup. Each party P_i and the helper party share a common key K_i. Using a Pseudo-Random Function (PRF), parties P_1 to P_{N-1} non-interactively sample their shares of V and T_V. Only the helper party needs to compute V_N and T_{V_N} for P_N and send these two elements. This reduces communication for share generation from 2N to just 2 elements, a significant improvement.

Demo / Proof of Concept

▶ Watch: Asymptotic cost comparison with state-of-the-art MPC (6:30)

The talk extensively demonstrated the practical viability and performance of Asterisk through its application to dark pools and comprehensive benchmarks against existing MPC protocols.

Application to Dark Pools:

A dark pool is a private forum for trading securities, where the details of buy and sell orders (quantities, prices) are kept confidential until the transaction is executed. This privacy is crucial to prevent market manipulation and front-running. The current centralized solutions suffer from a single point of failure and lack full privacy guarantees against the central entity. Asterisk addresses this by enabling oblivious matching of buyers and sellers.

The team implemented two popular dark pool algorithms within the Asterisk framework:

1. Continuous Double Auction: This algorithm processes a stream of buy and sell requests, attempting to find the best match as new requests arrive.

• Setting: Server-outsourced model with 5 parties.
• Data: 500 buy orders and 500 sell orders.
• Performance: The matching of these 1000 requests was completed in approximately 16 seconds, with a total communication overhead of less than 1.8 MB.

1. Volume Matching: This algorithm processes buy and sell requests in epochs, with all participating parties contributing to the computation.

• Setting: All parties participate in the MPC protocol.
• Data: 50 buyers and 50 sellers.
• Performance: The matching was completed in less than 2 minutes, requiring less than 2.5 MB of total communication.

These application-specific benchmarks highlight Asterisk's ability to handle real-world, sensitive financial transactions efficiently and privately.

Performance Benchmarks Against State-of-the-Art:

The researchers conducted extensive comparisons with existing honest majority and dishonest majority MPC protocols, focusing on both pre-processing and online phases.

• Pre-processing Phase (Dishonest Majority):
• Asterisk was benchmarked for up to 100 parties against state-of-the-art assisted MPC protocols. The results, presented on a logarithmic scale for both runtime and communication, showed Asterisk to have significantly lower runtime and communication costs.
• For 5 parties, specific improvements were quantified:
• Communication: Asterisk achieved an improvement of 352 times over mCut, 306 times over Overdrive, and close to 7 times over Assisted MPC.
• Throughput (Multiplication Triples): Asterisk demonstrated an improvement of 288 times over mCut, 228 times over Overdrive, and close to 3 times over Assisted MPC. These metrics are crucial as multiplication triples are a primary cost driver in many MPC protocols.

• Online Phase (Honest and Dishonest Majority):
• Asterisk's online phase was compared against protocols implemented in the popular MP-SPDZ framework, including dishonest majority works and honest majority constructions like Atlas.
• Runtime: Asterisk showed a slightly higher runtime in some cases. The speakers attributed this to the highly optimized implementations within the MP-SPDZ framework, suggesting that with similar levels of optimization, Asterisk's runtime could be competitive.
• Communication: Crucially, Asterisk consistently outperformed both dishonest majority and honest majority constructions (e.g., Atlas) in terms of communication during the online phase, reinforcing its communication efficiency.

These comprehensive benchmarks underscore Asterisk's superior performance characteristics, particularly in communication efficiency and scalability, making it a compelling solution for practical MPC deployments.

Defensive Implications

▶ Watch: Quantified communication improvements over dishonest majority protocols (8:00)

The Asterisk protocol introduces a nuanced and highly efficient approach to MPC that has several significant implications for defenders and organizations seeking to implement privacy-preserving computations:

1. Enabling Stronger Security with a Helper: For scenarios where a semi-trusted "helper" entity naturally exists (e.g., regulatory bodies like the SEC, a central service provider with limited trust), Asterisk provides a blueprint for achieving fairness—a stronger security guarantee than typically available in dishonest-majority settings—with high efficiency. This means organizations can leverage the benefits of high resilience (most participants can be malicious) without sacrificing the guarantee that if an adversary aborts the computation, they don't gain an unfair advantage by learning the output.

1. Practical Privacy for Sensitive Data: The successful application to dark pools demonstrates how Asterisk can enable crucial privacy-preserving operations in highly sensitive domains like finance. Defenders in these sectors can now consider deploying MPC solutions that prevent information leakage (e.g., about large buy/sell orders) before transactions are finalized, thereby mitigating risks of market manipulation or data exploitation. This extends to other areas requiring private matching, secure auctions, or collaborative analytics where a central facilitator is involved.

1. Understanding the "Either-Or" Trust Model: Asterisk highlights the importance of carefully defining the threat model. The "either-or" model (helper is semi-honest OR majority of parties are malicious, but not both simultaneously) represents a practical sweet spot for many real-world deployments. Defenders must assess if their specific operational environment fits this trust assumption. If it does, Asterisk offers a robust and efficient solution. If adversaries are likely to be simultaneously colluding or if the malicious adversary can feed information to a semi-honest helper, the presented impossibility results indicate that stronger guarantees like fairness may not be achievable, necessitating different protocol choices or a re-evaluation of the trust model.

1. Efficiency Gains for Wider MPC Adoption: The significant performance improvements in both communication and computation (especially in pre-processing) mean that MPC becomes a more feasible option for a broader range of applications. Defenders who previously found MPC too slow or too resource-intensive for their use cases might now find Asterisk to be a viable alternative. This lowers the barrier to entry for adopting advanced cryptographic privacy tools.

1. Information-Theoretic Security without Hardness Assumptions: The protocol's reliance on information-theoretic MACs and its independence from cryptographic hardness assumptions (like factoring or discrete logarithms) offer a strong long-term security posture. This is a significant advantage as it provides resilience against future advancements in cryptanalysis or the advent of quantum computing, which could potentially compromise schemes based on computational hardness.

In essence, Asterisk provides defenders with a powerful tool to implement privacy-preserving computations under a realistic trust model, delivering strong security guarantees with unprecedented efficiency. It encourages a shift from fully centralized, vulnerable systems to distributed, privacy-enhanced architectures where a trusted "friend" can help, without compromising the core privacy objectives.

Key Takeaways

• Asterisk introduces a novel MPC model with a semi-honest "helper" party, bridging the gap between honest-majority and dishonest-majority MPC protocols to achieve higher resilience and stronger security.
• The research provides a formal impossibility proof for achieving fairness and Guaranteed Output Delivery (GOD) when a semi-honest helper and a malicious majority adversary exist simultaneously, even if non-colluding but with information leakage.
• In the practical "either-or" model (either helper is semi-honest OR majority is malicious), Asterisk achieves fairness with high efficiency and scalability, without relying on cryptographic hardness assumptions.
• Asterisk demonstrates significant performance improvements, including reducing pre-processing communication by a factor of N over dishonest majority protocols and achieving 352x communication and 288x throughput gains over mCut for 5 parties.
• The protocol is successfully applied to dark pools, efficiently performing continuous double auctions and volume matching for hundreds of orders within seconds to minutes, showcasing its real-world applicability for sensitive financial transactions.
• Technically, Asterisk leverages masked secret sharing and an optimized common key setup for authenticated share generation, reducing communication for this critical step from 2N elements to just 2 elements.

About the Speaker(s)

The talk "Asterisk: Super-fast MPC with a Friend" was a joint work presented by Banashri Karmakar, Nishat Koti, Arpita Patra, Sikhar Patranabis, Protik Paul, and Divya Ravi. Based on the provided metadata and transcript, specific titles and affiliations for the speakers are not detailed, but they are all credited as co-authors and presenters of this research.