  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.
