Methods, systems, and computer program products for resolving domain name system records based on client authentication. Basing domain name resolution on client authentication provides remote clients with the convenience of domain names, without sacrificing the security of keeping potentially sensitive domain names private. An authoritative name server receives requests for domain name resolution from clients. For requests without client authentication, the authoritative name server responds that the domain name cannot be found. This response identifies the authoritative name server to the client so that the client can submit subsequent requests with client authentication. For requests with client authentication, the authoritative name server responds with the corresponding domain name addresses. Client may communicate domain name resolution requests directly to the authoritative name server or indirection, through one or more intermediate domain name servers. Client authentication may occur over a secure connection with the authoritative name server.