||An open problem in structured overlay networks is related to the anonymity to
be provided to recipients, namely, those nodes who respond to request messages.
Such a feature is of main concerns when designing censorship-resistant
In this paper it is shown that, in a chordal ring overlay, by enforcing a
degree of imprecision in each peer's routing table we obtain better recipient
anonymity while keeping the length of routing paths within logarithmic length.
A suitable metrics for recipient anonymity is established, based on the amount
of resources an adversary needs in order to break anonymity of recipients in
the overlay. In terms of this metrics, it is shown that imprecise routing
tables make it impossible for a ``small'' coalition of malicious peers to
correlate overlay addresses to hosts for censorship or auditing purposes.
As an aside, this approach is also shown to provide a ``better'' sender
anonymity: good anonymity levels become more likely at the expenses of
very low and very high ones.