Described systems and methods allow carrying out privacy-preserving DNS exchanges. In some embodiments, a client machine engages in a private information retrieval (PIR) exchange with a nameserver. In response to receiving an encrypted query from the client, the query formulated according to a domain name, the nameserver may extract a record (e.g., an IP address) from a domain name database without decrypting the respective query. Some embodiments achieve such information retrieval by the use of homomorphic encryption.