Efficient Actively Secure DPF and RAM-based 2PC with One-Bit Leakage

Efficient Actively Secure DPF and RAM-based 2PC with One-Bit Leakage

Speakers: Wenhao Zhang, Xiaojie Guo, Kang Yang, Ruiyu Zhu, Yu Yu, Xiao Wang

Conference: IEEE S&P

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

Overview

This talk introduces a groundbreaking protocol for actively secure Distributed Point Function (DPF) and RAM-based Two-Party Computation (2PC), designed to achieve high efficiency with minimal information leakage. The research tackles a critical challenge in applied cryptography: enabling two parties to jointly compute a function on their private inputs without revealing any information beyond the function's output, even when faced with a malicious adversary. Specifically, the work focuses on scenarios requiring numerous random memory accesses, which have traditionally posed significant efficiency hurdles for generic 2PC protocols.

The presented solution significantly advances the state-of-the-art by providing a maliciously secure RAM-based 2PC protocol that is orders of magnitude more efficient than previous secure constructions, while remaining competitive with even semi-honest protocols. By meticulously designing actively secure DPFs, reactive 2PC components, and authenticated sharing mechanisms, the researchers have created a robust framework that ensures data privacy and integrity in complex real-world applications such as private database queries, graph algorithms, and stable matching. This work represents a major step forward in making practical and secure multi-party computation accessible for a broader range of complex computational tasks.

Background

▶ Watch: Introduction to Secure Multi-Party Computation challenges (0:00)

Secure Multi-Party Computation (SMC), and its two-party variant 2PC, is a foundational concept in cryptography that allows multiple parties to jointly compute a function over their private inputs while keeping those inputs confidential. The canonical example involves two parties, P0 holding input X and P1 holding input Y, who wish to compute F(X,Y) without revealing X to P1 or Y to P0. Traditional 2PC protocols, such as Garbled Circuits and GMW (Goldreich-Micali-Wigderson), typically model the function F as a Boolean or arithmetic circuit and evaluate it gate by gate. While powerful, this approach suffers from significant overhead when the function involves frequent and unpredictable memory accesses.

Many real-world applications, however, inherently rely on dynamic data structures and random memory accesses. Algorithms like stable matching, private database queries, and graph algorithms often involve numerous read or write operations on private data locations. Directly converting such programs into compact circuits leads to immense overhead, rendering generic 2PC impractical. This limitation has spurred the development of specialized RAM-based 2PC models, which explicitly support both circuit evaluation and private random access to private data.

Historically, Oblivious RAM (ORAM) has been the classical method to address RAM-based 2PC. An ORAM protocol allows a client to outsource storage of an array to a server and then read from or write to that array without revealing the data itself or the memory access patterns to the server. In a two-server ORAM setup, two parties (P0 and P1) can jointly emulate the client, effectively converting it into a RAM-based 2PC protocol. While ORAM-based solutions offer strong security guarantees, they often come with substantial performance costs. For instance, the QI18 protocol, an ORAM-based approach, is one of the few known maliciously secure RAM-based 2PC protocols, but it exhibits a "huge overhead" compared to semi-honest alternatives, making it impractical for many use cases.

More recently, a new paradigm known as DPF-plus-2PC has emerged. This approach leverages a Distributed Point Function (DPF) to convert a private index into a corresponding position in memory, followed by custom protocols to complete the RAM-based 2PC operation. DPFs are cryptographic primitives that allow two parties to collaboratively evaluate a point function (a function that is zero everywhere except at a single, secret point) without revealing the point itself. Protocols like D17, which follows the DPF-plus-2PC paradigm, have demonstrated considerable efficiency under a semi-honest security model. In this model, adversaries are assumed to follow the protocol correctly but may try to learn extra information from the messages they receive. However, converting these semi-honest DPF-plus-2PC schemes to achieve malicious security—where adversaries can arbitrarily deviate from the protocol to compromise privacy or correctness—has remained an open challenge, particularly regarding efficiency. The core problem this research addresses is bridging this gap: achieving the efficiency of DPF-plus-2PC with the robust guarantees of malicious security, without incurring the prohibitive costs seen in prior maliciously secure ORAM-based solutions.

Key Findings

▶ Watch: Problem with prior art and our solution's efficiency (4:00)

The central contribution of this research is the design and implementation of a super-efficient, actively secure RAM-based 2PC protocol that overcomes the long-standing barriers to achieving malicious security in this domain. The protocol is built upon novel actively secure cryptographic primitives and achieves a performance profile that is not only competitive with state-of-the-art semi-honest RAM-based 2PC protocols but also vastly superior to existing maliciously secure solutions.

The key findings and contributions include:

1. Efficient Actively Secure DPF: The researchers developed a maliciously secure DPF protocol that offers significant improvements in communication efficiency compared to prior actively secure DPFs with comparable leakage properties. This DPF is also designed to be compatible with other building blocks required for RAM-based 2PC, a crucial aspect where previous work often fell short.
2. Actively Secure and Reactive 2PC: A new maliciously secure and reactive 2PC protocol was designed, extending techniques like dual execution. This protocol demonstrates an overhead that is "exactly twice" the cost of semi-honest Garbled Circuits, making it highly efficient for a maliciously secure primitive. Its "reactive feature" is particularly valuable, enabling seamless combination with other protocols and supporting applications requiring multiple interactions or stateful computations.
3. Overall RAM-based 2PC Construction with One-Bit Leakage: By integrating these new actively secure DPF and reactive 2PC components with extended authenticated sharing mechanisms and a novel batch consistency check using random linear combination, the team constructed a complete RAM-based 2PC protocol. This construction ensures that despite individual components potentially having "up to one-bit leakage," the total leakage throughout the entire execution of the RAM-based 2PC protocol is precisely one bit. This minimal leakage is a critical achievement for practical security guarantees.
4. Dramatic Performance Improvement: The protocol's efficiency is unprecedented for malicious security. In experimental settings involving 2^24 memory entries, it is "more than a thousand times better than QI18" (a previous maliciously secure ORAM-based protocol). Furthermore, it requires "only about twice the cost" of state-of-the-art semi-honest protocols like D17, demonstrating a significant leap in practical applicability. Benchmarking shows a random access cost of approximately 14 milliseconds for a memory size of 10^6 entries, highlighting its practical efficiency for real-world scenarios.

These findings collectively demonstrate that efficient and robustly secure RAM-based 2PC is not only theoretically possible but also practically achievable, paving the way for broader adoption of privacy-preserving technologies in complex applications.

Technical Deep Dive

▶ Watch: Our design: Maliciously secure DPF and reactive 2PC (5:30)

The proposed protocol fundamentally builds upon the DPF-plus-2PC paradigm, specifically drawing inspiration from the D17 design, but meticulously re-engineering each component to achieve malicious security while maintaining exceptional efficiency. The D17 scheme, a semi-honest DPF-plus-2PC protocol, typically uses a first-stage secure DPF, followed by a semi-honest and reactive 2PC protocol, and finally custom protocols for local operations that bridge these two key building blocks into a RAM-based 2PC. The challenge for the current work was to upgrade every one of these components to maliciously secure equivalents without incurring prohibitive overhead.

The core of their design involves three main technical innovations:

1. Maliciously Secure Distributed Point Function (DPF) with Up to One-Bit Leakage:

A DPF is a cryptographic primitive that allows a point function (a function f_α, β(x) that outputs β if x = α and 0 otherwise) to be split into two keys, k0 and k1. One party (P0) gets k0 and the other (P1) gets k1. Neither party learns α or β from their key alone. When P0 computes f_α, β(x) using k0 and P1 computes f_α, β(x) using k1, their outputs y0 and y1 sum to f_α, β(x). In the context of RAM-based 2PC, the DPF is used to securely identify the memory address (α) being accessed.

The authors' contribution here is a novel construction for a maliciously secure DPF. Prior maliciously secure DPFs often suffered from high communication costs. Their design achieves "great improvement on the communication" compared to these prior works while maintaining the "same leakage" profile (up to one bit). Crucially, this DPF is designed to be fully compatible with the other building blocks of the RAM-based 2PC scheme. This compatibility is vital because previous secure DPFs were often not efficiently integrable into the DPF-plus-2PC framework. Furthermore, the speakers highlight that this DPF construction can serve as a useful building block for other advanced cryptographic protocols, such as 2-out-of-N Oblivious Linear Evaluation (OLE) extensions.

1. Maliciously Secure and Reactive 2PC Protocol with Up to One-Bit Leakage:

The second critical component is a robust 2PC protocol capable of handling general computations in a reactive setting. "Reactive" means the protocol can maintain state and respond to a sequence of inputs over time, which is essential for complex memory access patterns. The researchers extended techniques from dual execution to achieve malicious security for their reactive 2PC. Dual execution is a method to upgrade semi-honest protocols to malicious security by having each party effectively run two instances of the protocol, verifying consistency between them.

The resulting maliciously secure and reactive 2PC protocol exhibits an overhead that is "exactly twice the cost overhead to the semi-honest garbled circuits." This is a significant achievement because it means the cost for malicious security is very close to the theoretical minimum for this approach. The "reactive feature" is particularly powerful, enabling the 2PC protocol to be combined seamlessly with other cryptographic primitives and allowing it to be applied in a wider array of applications that require dynamic interactions and state management, beyond simple one-off computations.

1. Extended Local Operations with Authenticated Sharing and Batch Consistency Checks:

The DPF and general 2PC building blocks need to be integrated through custom local operations that manage the actual memory accesses and data manipulation. In the D17 design, these local operations are performed on semi-honest shares. For malicious security, the authors needed to extend these local operations to support authenticated sharing. Authenticated sharing ensures that not only is the secret shared among parties, but also that any manipulation of these shares can be verified to be correct, preventing a malicious party from corrupting the computation by providing invalid shares.

A critical aspect of achieving overall security and managing leakage is the mechanism for consistency checks. Each component (DPF, reactive 2PC, local operations) might individually contribute "up to one bit leakage" during its execution. To ensure that the total leakage for the entire RAM-based 2PC protocol remains minimal, the authors employ a technique using random linear combination to batch all consistency checks together. Instead of checking each operation individually, which could accumulate leakage or communication, they combine multiple checks into a single verification. This batching mechanism is crucial because it ensures that "there is only one bit [of leakage] during the whole execution of this RAM-based 2PC particle," a remarkable feat for an actively secure protocol.

In summary, the technical deep dive reveals a sophisticated architectural approach where each building block is meticulously designed for malicious security and efficiency, and then cleverly integrated with mechanisms like authenticated sharing and batch consistency checks to guarantee overall security and minimal leakage. This modular yet tightly integrated design is what allows the protocol to achieve its unprecedented performance characteristics.

Demo / Proof of Concept

▶ Watch: Benchmark results and performance comparison with prior work (8:00)

While the talk did not feature a live, interactive demonstration of the protocol, the researchers provided extensive benchmarking results to validate its efficiency and practical applicability. This performance evaluation served as the empirical proof of concept, comparing their novel protocol against both state-of-the-art semi-honest and existing maliciously secure RAM-based 2PC solutions.

The benchmarking compared the "work time per access to the size of memory" across various memory sizes and network settings (both LAN and WAN). The protocols included in the comparison were:

• D17: A prominent semi-honest RAM-based 2PC protocol.
• VHD23: The "state-of-the-art semi-honest RAM-based 2PC protocol in the WAN setting."
• QI18: The only known maliciously secure ORAM-based 2PC protocol, representing the prior art for malicious security.
• Their protocol: The newly proposed actively secure DPF and RAM-based 2PC.

The results were compelling:

• Competitive with Semi-Honest Protocols: The authors' protocol was "competitive with both semi-honest protocols D17 and VHD23" in both LAN and WAN settings. This is a significant achievement, as maliciously secure protocols typically incur substantially higher overheads than their semi-honest counterparts.
• Dramatic Outperformance of Maliciously Secure Prior Art: Their protocol "consistently outperforms QI18 by at least two orders of magnitude" (i.e., over 100 times faster) in both network settings. For a specific experimental setting with 2^24 entries, the speakers claimed their work was "more than a thousand times better than QI18." This stark difference highlights the breakthrough in efficiency for malicious security.
• Practical Efficiency: For a memory size of approximately 10^6 entries (which is 2^20), a random access in their protocol costs "about 14 milliseconds." This figure demonstrates a "good practical efficiency in some real-world 2PC applications," suggesting that the protocol is viable for scenarios demanding responsive private computations.

The researchers also presented a cost breakdown analysis for an access operation in different scenarios, dividing the access into six distinct stages. This analysis revealed key performance bottlenecks:

• In the LAN setting, when the memory size is "somehow large, like more than 2^26 entries," the "local memory access" becomes the main cost driver. This implies that for extremely large datasets, the local processing of data within each party's memory becomes the dominant factor.
• In the WAN setting, "bandwidth and the network imitation" are identified as the bottlenecks. This is expected, as network latency and throughput often limit distributed computations over wide area networks.

These comprehensive benchmarks serve as a strong empirical validation of the protocol's theoretical claims, demonstrating its superior efficiency and practical feasibility in various operational environments.

Defensive Implications

▶ Watch: Summary of contributions and where to find the paper (10:00)

The development of an efficient, actively secure RAM-based 2PC protocol with minimal leakage carries profound defensive implications for organizations and individuals dealing with sensitive data. In an increasingly data-driven world, the ability to perform computations on private data without revealing the inputs themselves is paramount for privacy, regulatory compliance, and competitive advantage.

1. Enabling Robust Privacy-Preserving Applications: This protocol provides a strong cryptographic foundation for building real-world applications that require data collaboration without data exposure. For instance, two hospitals could jointly analyze patient data to identify disease patterns without revealing individual patient records to each other. Financial institutions could detect fraud across their customer bases without sharing sensitive transaction histories. The malicious security guarantee means these computations remain private and correct even if one party attempts to cheat or learn extra information.
2. Mitigating Insider Threats and Collusion: Traditional data sharing often relies on trust models that are vulnerable to insider threats or collusion. By using actively secure 2PC, organizations can significantly reduce the attack surface. Even if an insider on one side attempts to maliciously extract information or tamper with results, the protocol is designed to detect such behavior or prevent information leakage beyond the intended output. The "one-bit leakage" property ensures that the amount of unintended information revealed is negligible.
3. Secure Outsourcing and Cloud Computing: The protocol's efficiency makes it more feasible to outsource complex computations on sensitive data to cloud providers, even if those providers are not fully trusted. By splitting data and computation across multiple cloud instances or between an organization and a cloud provider, and leveraging this RAM-based 2PC, organizations can perform powerful analytics without giving any single entity full access to their raw data.
4. Compliance with Data Protection Regulations: Regulations like GDPR, CCPA, and HIPAA mandate strict controls over personal and sensitive data. This actively secure 2PC protocol offers a powerful tool for achieving compliance by enabling necessary data processing while maintaining stringent privacy guarantees. It allows organizations to demonstrate "privacy-by-design" in their data handling practices.
5. Foundational Security for Advanced Cryptographic Primitives: The novel actively secure DPF and reactive 2PC building blocks are not only crucial for this specific RAM-based 2PC but also serve as more efficient and robust primitives for future cryptographic constructions. As noted by the speakers, the DPF can be used for 2-out-of-N OLE extensions, indicating its potential to bolster the security and efficiency of other privacy-enhancing technologies.
6. Addressing "Random Access" Bottlenecks: By efficiently handling random memory accesses, the protocol makes a whole class of algorithms previously deemed impractical for secure computation now feasible. This includes graph algorithms, complex database queries, and dynamic programming problems, which are prevalent in many defensive security applications (e.g., threat intelligence sharing, anomaly detection, secure machine learning on distributed datasets).

In essence, this work empowers defenders by providing them with a highly efficient and cryptographically sound mechanism to process and analyze sensitive data in a collaborative yet private manner, thereby strengthening overall data security posture against both external and internal threats.

Key Takeaways

• Breaks Efficiency Barriers for Malicious Security: The protocol offers unprecedented efficiency for actively secure RAM-based 2PC, outperforming prior maliciously secure solutions (like QI18) by over 1000 times while remaining competitive with state-of-the-art semi-honest protocols.
• Minimal and Controlled Leakage: Despite the complexity of malicious security, the entire RAM-based 2PC protocol ensures only one bit of leakage throughout its execution, achieved through advanced batch consistency checks using random linear combinations.
• Novel Actively Secure Building Blocks: The research introduces new, highly efficient maliciously secure Distributed Point Function (DPF) and reactive 2PC protocols. The DPF significantly improves communication efficiency, and the reactive 2PC has an overhead of only twice that of semi-honest garbled circuits.
• Practical for Real-World Applications: With a random access cost of approximately 14 milliseconds for 10^6 entries, the protocol demonstrates practical feasibility for complex, random-access-heavy applications such as private database queries, stable matching, and graph algorithms.
• Addresses Random Access Challenge: It effectively solves the long-standing problem of efficiently supporting numerous random memory accesses in secure computation, a limitation that has historically hampered the practical deployment of generic 2PC for many real-world programs.
• Foundation for Future Cryptography: The developed actively secure DPF and reactive 2PC are versatile building blocks that can be applied to other advanced cryptographic constructions, such as 2-out-of-N OLE extensions, fostering further innovation in privacy-enhancing technologies.

About the Speaker(s)

The talk was presented by Wenhao Zhang, who stated during the presentation, "I'm from Los Weston," likely referring to Northwestern University. The work is a collaborative effort, with the full list of authors including Wenhao Zhang, Xiaojie Guo, Kang Yang, Ruiyu Zhu, Yu Yu, and Xiao Wang. Their collective research focuses on advancements in applied cryptography, particularly in the domain of secure multi-party computation and its practical applications. Their work demonstrates a strong commitment to overcoming the practical barriers to deploying secure computation in real-world scenarios, bridging the gap between theoretical cryptographic constructs and efficient, robust implementations.