TL;DR
This paper introduces a novel actively secure RAM-based two-party computation (2PC) protocol that achieves performance comparable to state-of-the-art semi-honest protocols, while leaking only a single bit of information. This breakthrough significantly lowers the barrier for deploying secure computation in practical RAM-based applications by offering a much-needed balance between security and efficiency.
What Problem Does This Paper Address?
Secure two-party computation (2PC) allows two parties to jointly compute a function on their private inputs without revealing those inputs to each other. While significant progress has been made for computations represented as circuits, many real-world programs operate in the Random-Access Machine (RAM) model, requiring private memory access. Existing RAM-based 2PC protocols primarily offer semi-honest security, meaning parties follow the protocol but might try to learn extra information. Actively secure protocols, which protect against malicious parties that can deviate from the protocol, are notoriously inefficient. The state-of-the-art actively secure RAM-based 2PC protocol [KY18] suffers from slowdowns of at least two orders of magnitude, making it impractical for most applications. This paper aims to bridge this gap by developing an actively secure RAM-based 2PC protocol that is both efficient and practical.
Methods
The authors propose a novel approach that combines several key techniques:
- Efficient Actively Secure Distributed Point Function (DPF): They introduce a new DPF protocol that is actively secure and significantly more efficient than prior malicious DPF protocols. This protocol avoids generic malicious 2PC and achieves a 50x communication improvement, matching the efficiency of semi-honest DPF protocols.
- Reactive 2PC with One-Bit Leakage: They extend existing dual-execution protocols for active security to support reactive computations (protocols that maintain state over multiple steps). This is achieved by leveraging BDOZ authenticated shares and carefully controlling abort events to ensure only one bit of leakage.
- RAM-based 2PC Construction: They build their RAM-based 2PC protocol on top of their new DPF and reactive 2PC building blocks, following the blueprint of the semi-honest Floram protocol. This involves constructing actively secure Read-Only Memory (ROM) and Write-Only Memory (WOM) components.
- Optimized Refresh and Stash Mechanisms: To maintain efficiency, they employ optimized refresh procedures and a stash-based lookup mechanism for WOM updates.
- Batching of Checks: Crucially, they batch all consistency checks to the end of the protocol execution, allowing for a single-bit leakage guarantee.
Datasets
Not discussed in the paper. The paper focuses on theoretical constructions and experimental evaluation of their protocol.
Key Insights and Ideas
- One-Bit Leakage as a Practical Trade-off: The paper demonstrates that a single bit of leakage is a highly practical trade-off for achieving active security in RAM-based 2PC, making it orders of magnitude faster than fully secure protocols.
- DPF as a Core Building Block: The efficiency gains are heavily reliant on their novel actively secure DPF protocol, highlighting its importance for secure RAM computation.
- Dual Execution for Reactive Protocols: Adapting the dual-execution paradigm to reactive settings, where state is maintained, is a key enabler for their actively secure RAM-based 2PC.
- Batching Checks for Efficiency: Deferring and batching all security checks to the end is a critical optimization that allows for a single-bit leakage guarantee without sacrificing performance.
Key Results
- Performance Comparable to Semi-Honest Protocols: Their actively secure protocol achieves performance essentially the same as state-of-the-art semi-honest RAM-based 2PC protocols (Floram and Duoram).
- Significant Speedup Over Prior Malicious Protocols: The protocol is orders of magnitude faster (e.g., ~100x) than prior actively secure RAM-based 2PC protocols like KY18.
- Efficient DPF: Their actively secure DPF protocol offers a 50x communication improvement over previous malicious DPF protocols and matches the efficiency of semi-honest ones.
- Practicality Demonstrated: Experimental results show competitive performance across various benchmarks, including binary search, stable matching, and scrypt, in both LAN and WAN settings.
Limitations and Future Work
- One-Bit Leakage: The protocol inherently leaks one bit of information to the adversary. While this is presented as a practical trade-off, it might not be suitable for applications requiring absolute zero leakage.
- Future Work: The authors suggest applying their optimizations to weaker models of DPF protocols (e.g., with two servers) and exploring their use for improving the efficiency of silent correlation generation. They also mention the possibility of applying their protocol to improve the concrete efficiency of silent correlation generation.
Summary updated