  Privacy leaks are an unfortunate and an integral part of the current Internet
domain name resolution. Each DNS query generated by a user reveals -- to one or
more DNS servers -- the origin and target of that query. Over time, a user's
browsing behavior might be exposed to entities with little or no trust. Current
DNS privacy leaks stem from fundamental DNS features and are not easily fixable
by simple patches. Moreover, privacy issues have been overlooked by DNS
security efforts (i.e. DNSSEC) and are thus likely to propagate into future
versions of DNS.
  In order to mitigate privacy issues in current DNS, this paper proposes a
Privacy-Preserving Domain Name System (PPDNS), which maintains privacy during
domain name resolution. PPDNS is based on distributed hash tables (DHTs), an
alternative naming infrastructure, and computational private information
retrieval (cPIR), an advanced cryptographic construct. PPDNS takes advantage of
the DHT's index structure to improve name resolution query privacy, while
leveraging cPIR to reduce communication overhead for bandwidth-sensitive
clients. Our analysis shows that PPDNS is a viable approach for obtaining a
higher degree of privacy for name resolution queries. PPDNS also serves as a
demonstration of blending advanced systems techniques with their cryptographic
counterparts.
