In structured peer-to-peer networks, like Chord, users find data by asking a number of intermediate nodes in the network. Each node provides the identity of the closet known node to the address of the data, until eventually the node responsible for the data is reached. This structure means that the intermediate nodes learn the address of the sought after data. Revealing this information to other nodes makes Chord unsuitable for applications that require query privacy so in this paper we present a scheme Iris to provide query privacy while maintaining compatibility with the existing Chord protocol. This means that anyone using it will be able to execute a privacy preserving query but it does not require other nodes in the network to use it (or even know about it). In order to better capture the privacy achieved by the iterative nature of the search we propose a new privacy notion, inspired by $k$-anonymity. This new notion called $(α,δ)$-privacy, allows us to formulate privacy guarantees against adversaries that collude and take advantage of the total amount of information leaked in all iterations of the search. We present 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 $(α,δ)$-private while introducing a modest performance overhead. Importantly the overhead is tunable and proportional to the required level of privacy, so no privacy means no overhead.