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.