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

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

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

Abstract

Secure two-party computation (2PC) in the RAM model has attracted huge attention in recent years. Most existing results only support semi-honest security, with the exception of Keller and Yanai (Eurocrypt 2018) with very high cost. In this paper, we propose an efficient RAM-based 2PC protocol with active security and one-bit leakage. 1) We propose an actively secure protocol for distributed point function (DPF), with one-bit leakage, that is essentially as efficient as the state-of-the-art semi-honest protocol. Compared with previous work, our protocol takes about $50 \times$ less communication for a domain with $2^{20}$ entries, and no longer requires actively secure generic 2PC. 2) We extend the dual-execution protocol to allow reactive computation, and then build a RAM-based 2PC protocol with active security on top of our new building blocks. The protocol follows the paradigm of Doerner and shelat (CCS 2017). We are able to prove that the protocol has end-to-end one-bit leakage. 3) Our implementation shows that our protocol is almost as efficient as the state-of-the-art semi-honest RAM-based 2PC protocol, and is at least two orders of magnitude faster than prior actively secure RAM-based 2PC without leakage, providing a realistic trade-off in practice.
BibTeX
@article{zhang2024efficient,
  author = {Wenhao Zhang and Xiaojie Guo and Kang Yang and Ruiyu Zhu and Yu Yu and Xiao Wang},
  title = {{Efficient Actively Secure DPF and RAM-based 2PC with One-Bit Leakage}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2024},
}

Loading related content...

Figure