Paper 2026/2629

VeilDNS: Post-Quantum DNS Privacy from the First UDP Packet

Abstract

DNS was designed around UDP, and most DNS traffic today still follows that design: one query, one response, and no handshake. This makes DNS fast and scalable, but exposes client queries in cleartext. DoT, DoH, and DoQ provide privacy by encrypting DNS messages with TLS. This works once TLS/TCP or QUIC handshakes complete, but cold sessions spend extra round trips and CPU before the first private query can be sent—a cost that grows with post-quantum cryptography. We present VeilDNS, a DNS-native protocol that uses a post-quantum KEM and AEAD to encrypt DNS questions and answers and authenticate the resolver in a single UDP exchange. Given an authenticated resolver KEM key, clients have query privacy from their first UDP packet. VeilDNS supports stateless and stateful modes—the latter reducing recurring computation and bandwidth. An optional mode provides forward secrecy from the second query onward. By preserving the DNS wire format, VeilDNS runs on the standard UDP port 53. Compared with ML-DSA-authenticated Do(T/H/Q) on the well-provisioned network profile, VeilDNS's stateless and stateful modes achieve up to $3.5\times$ higher cold-session throughput, $4.8\times$ lower average latency, $4.7\times$ lower CPU time, $13.7\times$ fewer bytes, and $15.8\times$ fewer packets. On the constrained profile, the throughput gain reaches $12.4\times$. Tamarin establishes query confidentiality, response authentication, and forward secrecy.