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.
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.
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