If you are concerned about your privacy, choosing an appropriate DNS server is a difficult decision. The only certain answer, however, is that you should not stick to the default configuration, which in most cases uses DNS servers provided and maintained by your ISP. Using these servers would enable backtracking your DNS requests to your ISP, so with a warrant or additional tracking information it is perfectly possible to identify your real IP. In this article, we will look at a few alternatives, along with their pros and cons.
If your VPN provider runs its own dedicated DNS servers, they might be the best option. However, the differences in quality between VPN providers can be huge. For example, many DNS solutions by VPN providers can be real performance killers. Also, using their own servers means you trust the way they will handle your privacy and you assume they will not store data that could be used to identify you. Finally, you should make sure that your VPN provider is not just redirecting your DNS queries to public services, such as Google Public DNS (which means that your DNS queries should have your VPN provider's IP, not your real IP). This option is very common and easy to implement but is far from an ideal solution.
There are a few public DNS offerings out there that focus on performance, security or censorship circumvention.
The most popular public DNS services are offered by Google, OpenDNS (part of Cisco since 2015) and Level3. According to their privacy statement, Google Public DNS sounds very promising:
Important: We built Google Public DNS to make the web faster and to retain as little information about usage as we could, while still being able to detect and fix problems. Google Public DNS does not permanently store personally identifiable information.
Google's statement is clear about what it means that they do "not permanently store personally identifiable information". Data about DNS queries will be stored for 24h to 48h hours, which seems a reasonable period. This logging is essential to discover and fix bugs as well as to fine-tune the service.
The next big group of public DNS servers is for users who want to avoid domain-name based censoring systems. Some example servers are included in the list of alternative DNS servers on wikileaks.org. Although many of these systems are not particularly conceived for privacy, they can include privacy protection as a feature, e.g. dns.watch.
This group of public DNS servers are usually provided by IT security companies. Examples include Norton ConnectSafe, Comodo Secure DNS and Verisign. These services aim at improving security by filtering malicious websites or botnet controllers, so they might be redundant if your web browser filters malicious websites (but not botnet controllers) by default, such as Google Safe Browsing or Microsoft SmartScreen. It is up to you whether you are willing to support the business models of these US companies in exchange for protecting your privacy. Some companies address privacy issues explicitly in their offerings, such as Verisign:
Assurance that your public DNS data will not be sold to third parties.
This might be less than you hoped for, but at least sounds better than AT&T.
There are also paid solutions that offer "logless" DNS servers, such as GoldenFrog. However, this does not mean no logs at all. Even if these companies themselves do not log any information (which is highly unlikely anyway), their rack or uplink providers might still store enough information to identify you.
DNSCrypt and DNSSEC are often touted as effective means to improve your DNS privacy. However, they do not make your DNS requests anonymous. Instead, DNSCrypt encrypts DNS traffic in order to prevent eavesdropping or man-in-the-middle attacks. DNSSEC is comparable to a security certificate for hosts, which enables your DNS client to verify responses using a chain of trust. In other words, these services together can prevent a man in the middle from spoofing or listening to your DNS traffic but will do nothing to anonymize your activity. As a result, the receiving authoritative nameservers will still process your plain request, usually generating some sort of entries in a log file. In any case, a DNS server with support for DNSSEC and/or DNSCrypt can be interpreted as a sign that the provider is concerned about their users' privacy. Before using these DNS extensions, make sure you understand their drawbacks, such as the reduced failover capability of DNSCrypt.
A list of DNS server providers supporting DNSCrypt is available here.
Deciding on a DNS server is nothing compared to the pain of configuring and testing your DNS configuration. As soon as you uncheck the "Obtain DNS server address automatically" option, you are knee-deep in a nerd's universe where every mistake will kill your network, performance or security. And it gets even more complicated as a lot of software tries to be extra clever at managing your DNS. For example, Windows 10 attempts to improve performance by sending DNS requests in parallel to all available resources at once while various torrent clients employ a built-in mechanism that falls back to Google's DNS servers whenever users mess up their DNS configuration.
A list of public DNS servers that dissects their privacy statements and the networks they are on: https://thesimplecomputer.info/a-list-of-dns-service-providers