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 the target of that query. Over time, users' communication (e.g., browsing) patterns might become exposed to entities with little or no trust. Current DNS privacy leaks stem from fundamental features of DNS and are not easily fixable by simple patches. Moreover, privacy issues have been overlooked by DNS security efforts (such as DNSSEC) and are thus likely to propagate into future versions of DNS. In order to mitigate privacy issues in DNS, this paper proposes a Privacy-Preserving DNS (PPDNS), that offers 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 index structure to provide 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 reasonably high level of privacy for name resolution queries. PPDNS also serves as a demonstration of blending advanced systems techniques with their cryptographic counterparts.