Adding Query Privacy to Robust DHTs

Michael Backes, Ian Goldberg, Aniket Kate, Tomas Toft

Abstract

Interest in anonymous communication over distributed hash tables (DHTs) has increased in recent years. However, almost all known solutions solely aim at achieving sender or requestor anonymity in DHT queries. In many application scenarios, it is crucial that the queried key remains secret from intermediate peers that (help to) route the queries towards their destinations. In this paper, we satisfy this requirement by presenting an approach for providing privacy for the keys in DHT queries. We use the concept of oblivious transfer (OT) in communication over DHTs to preserve query privacy without compromising spam resistance. Although our OT-based approach can work over any DHT, we concentrate on communication over robust DHTs that can tolerate Byzantine faults and resist spam. We choose the best-known robust DHT construction, and employ an efficient OT protocol well-suited for achieving our goal of obtaining query privacy over robust DHTs. Finally, we compare the performance of our privacy-preserving protocols with their more privacy-invasive counterparts. We observe that there is no increase in the message complexity and only a small overhead in the computational complexity.

Introduction

Distributed Hash Tables (DHTs) serve as a fundamental building block for decentralized systems, facilitating the mapping of keys to values across a peer-to-peer network. While significant progress has been made in ensuring DHTs are robust against malicious nodes and provide requester anonymity, a critical gap remains: query privacy. In standard robust DHT protocols, a requester must reveal the specific key they are searching for to intermediate nodes to receive routing information for the "next hop." This exposure allows intermediate nodes to log user searches, enabling censorship or mass surveillance.

Robust DHTs and Quorums

To address these privacy concerns while maintaining robustness, the authors build upon existing robust communication protocols (RCP-I and RCP-II). These protocols utilize quorums—groups of nodes that act collectively—to provide Byzantine fault tolerance.

Structure of a robust DHT using quorums for fault tolerance.

In this architecture, routing is performed through a sequence of quorums. The challenge is to hide the query from these quorums without allowing a requester to "crawl" the entire network, which would facilitate spam attacks.

Methodology: Query Privacy via Oblivious Transfer

The core of the proposed solution is the integration of Oblivious Transfer (OT), specifically the Naor-Pinkas protocol. OT allows a requester (the "chooser") to obtain a specific piece of information from a quorum (the "sender") without the quorum learning which piece was requested.

Hybrid Encryption and Range Boundaries

To maintain efficiency, the protocol employs a hybrid encryption scheme. Instead of transferring large routing table entries via OT, quorum members encrypt each entry with a unique AES key. The requester then uses an OT execution to fetch only the specific AES key required for the next hop.

A significant innovation is the handling of range queries. DHTs typically route based on intervals. Instead of using computationally expensive "Conditional OT," the authors observe that revealing the boundaries of routing table ranges does not leak sensitive information about the target keys. By sharing these boundaries, the requester can identify the correct index and then use a faster indexed OT to retrieve the necessary routing information.

Protocol flow for privacy-preserving queries using Oblivious Transfer and authorization proofs.

Quorum-Based Validation

To prevent spam, the protocol requires quorums to validate requests. A requester must present an authorization proof to a quorum to demonstrate that their request follows the protocol rules before the quorum members participate in the OT process. This ensures that OT serves a dual purpose: providing privacy for the user while strictly limiting the amount of routing information a requester can harvest.

Key Results

The analysis demonstrates that adding query privacy does not compromise the efficiency of the underlying robust DHT:

  • Message Complexity: The protocols RCPqp-I and RCPqp-II maintain the same message complexity as their non-private counterparts, $O(\log^2 n)$ and $O(\log n)$ respectively.
  • Computational Overhead: The additional computational cost is minimal. The OT operations add only a few milliseconds of latency, which is negligible compared to the multi-second latencies typical in wide-area robust DHT routing.
  • Security: The system remains resilient against adversaries controlling up to 10% of the network, provided no single quorum exceeds a 1/3 threshold of faulty members.

Conclusion and Future Work

This work presents a practical approach to achieving query privacy in robust DHTs without sacrificing performance or spam resistance. While the theoretical foundation is strong, the authors identify areas for future exploration, such as mitigating "range estimation attacks" where an adversary might narrow down a target key's location by observing quorum sequences. Additionally, addressing potential information leaks in the signature chains of RCPqp-II and moving toward large-scale practical deployments remain key objectives for future research.

Summary updated

Abstract

Interest in anonymous communication over distributed hash tables (DHTs) has increased in recent years. However, almost all known solutions solely aim at achieving sender or requestor anonymity in DHT queries. In many application scenarios, it is crucial that the queried key remains secret from intermediate peers that (help to) route the queries towards their destinations. In this paper, we satisfy this requirement by presenting an approach for providing privacy for the keys in DHT queries. We use the concept of oblivious transfer (OT) in communication over DHTs to preserve query privacy without compromising spam resistance. Although our OT-based approach can work over any DHT, we concentrate on communication over robust DHTs that can tolerate Byzantine faults and resist spam. We choose the best-known robust DHT construction, and employ an efficient OT protocol well-suited for achieving our goal of obtaining query privacy over robust DHTs. Finally, we compare the performance of our privacy-preserving protocols with their more privacy-invasive counterparts. We observe that there is no increase in the message complexity and only a small overhead in the computational complexity.
BibTeX
@inproceedings{backes2012adding,
  author = {Michael Backes and Ian Goldberg and Aniket Kate and Tomas Toft},
  title = {{Adding Query Privacy to Robust DHTs}},
  booktitle = {AsiaCCS},
  year = {2012},
  url = {https://openreview.net/forum?id=hPb6jCA2CrB},
}
Figure