A secret sharing scheme for anonymous DNS queries

Since its adoption in the early 90's, several privacy concerns have emerged about the Domain Name System (DNS). By collecting the DNS queries performed by each user, it is possible to characterize habits, interests and other sensitive data of the users. Usually, users resolve their {\em url} requests by querying the DSN server belonging to their Internet Service Provider (ISP) and therefore they assume they can trust it. However, different DNS servers can be used, by revealing sensitive data to a partially untrusted entity that can collect and sell this data for several purposes (target advertising, user profiling, etc.). In this paper we address the possibility to integrate tools in the current DNS architecture to enhance users privacy when they decide to use a DNS server different from the one made available by their ISP, while allowing the DNS servers to collect statistics about queries in order to optimize their operations. The mean feature of the proposed architecture is to guarantee {\em Sender Anonymity} from the DNS point of view, without obfuscating the actual queries. This is possible by applying a {\em Secret Sharing} scheme on {\em urls} to be resolved in an overlay network consisting of clients using the same DNS, and by disseminating the shares of each query to multiple nodes, randomly selected from this network, which in turn act as proxies to reach the DNS.