There has been a growing interest in Internet user privacy, demonstrated by the popularity of privacy-preserving products such as Telegram and Brave, and the widespread adoption of HTTPS. The Domain Name System (DNS) is a key component of Internet-based communication and its privacy has been neglected for years. Recently, DNS over HTTPS (DoH) has improved the situation by fixing the issue of in-path middleboxes. Further progress has been made with proxy-based solutions such as Oblivious DoH (ODoH) and DoH over Tor (DoHoT), which separate a user’s identity from their DNS queries. However, these solutions rely on trusted DNS resolvers and non-collusion with the proxy network. This paper proposes a new extension to DNS, called PDNS, that uses Private Information Retrieval to allow DNS resolvers to operate on encrypted DNS queries, thereby eliminating any privacy leaks. We have implemented a prototype of PDNS and compared its performance against all state-of-the-art solutions via trace-driven experiments. The results show that PDNS achieves high performance and strong privacy guarantees, mainly at the cost of its scalability, which specialized hardware for PIR can address in the near future.
