Mutualized oblivious DNS ($μ$ODNS): Hiding a tree in the wild forest

ith a full-service resolver, i.e., identities of users cannot be hidden to the resolver. This paper introduces a new concept of a multiple-relay-based DNS for user anonymity in DNS queries, called the mutualized oblivious DNS ($μ$ODNS), by extending the concept of existing relay-based schemes. The $μ$ODNS introduces a small and reasonable assumption that each user has at least one trusted/dedicated relay in a network and mutually shares the dedicated one with others. The user just sets the dedicated one as his next-hop, first relay, conveying his queries to the resolver, and randomly chooses its $0$ or more subsequent relays shared by other entities. Under this small assumption, the user's identity is concealed to a target resolver in the $μ$ODNS even if a certain (unknown) subset of relays collude with the resolver. That is, in $μ$ODNS, users can preserve their privacy and anonymity just by paying a small cost of sharing its resource. Moreover, we present a PoC implementation of $μ$ODNS that is publicly available on the Internet. We also show that by measurement of round-trip-time for queries, and our PoC implementation of $μ$ODNS achieves the performance comparable to existing relay-based schemes.