  In structured peer-to-peer networks like Chord, the users manage to retrieve
the information they seek by asking other nodes from the network for the
information they search. Revealing to other nodes the search target makes
structured peer-to-peer networks unsuitable for applications that demand query
privacy, i.e., hiding the query's target from the intermediate nodes that take
part in the routing. This paper studies the query privacy of structured P2P
networks, particularly the Chord protocol.
  We initially observe that already proposed privacy notions, such as
$k$-anonymity, do not allow us to reason about the privacy guarantees of a
query in Chord in the presence of a strong adversary. Thus, we introduce a new
privacy notion that we call $(\alpha,\delta)$-privacy that allows us to
evaluate the privacy guarantees even when considering the worst-case scenario
regarding an attacker's background knowledge.
  We then design Iris, an algorithm that allows a requester to conceal the
target of a query in Chord from the intermediate nodes that take part in the
routing. Iris achieves that by having the requester query for other than the
target addresses so as reaching each one of them allows the requester to get
closer to the target address.
  We perform a security analysis of the proposed algorithm, based on the
privacy notion we introduce. We also develop a prototype of the algorithm in
Matlab and evaluate its performance. Our analysis proves Iris to be
$(\alpha,\delta)$-private while introducing a modest performance overhead.
