CODoH: Privacy-Preserving Caching for Oblivious DNS over HTTPS
Pankaj Niroula (Paper author · William & Mary), Lily Gloudemans (Paper author · William & Mary), Aashutosh Poudel (Paper author · William & Mary), Collin MacDonald (Paper author · William & Mary), Stephen Herwig (Paper author · William & Mary)
Privacy Enhancing Technologies Symposium (PETS) 2026 · Day 2 · Alpaca
Overview
This article delves into CODoH: Privacy-Preserving Caching for Oblivious DNS over HTTPS, a groundbreaking work presented at PETS that addresses a critical challenge in modern privacy-preserving DNS architectures. Oblivious DNS (ODNS), exemplified by services like Apple's iCloud Private Relay, enhances user privacy by decoupling a client's IP address from their DNS queries. While this two-hop architecture significantly improves unlinkability, it traditionally comes at a substantial performance cost due to the inherent difficulty of implementing caching without reintroducing privacy leaks. This talk presents CODoH as a robust solution, demonstrating how intelligent design can restore the performance benefits of caching while maintaining, and even strengthening, the privacy guarantees of ODNS.

Key moments
- 1:00 Oblivious DNS (ODoH) and caching challenges
- 2:15 Shared cache as a side channel: proxy adversary
- 3:30 Three key requirements for privacy-preserving cache
- 5:50 Solving bit key leakage with cover responses
- 7:00 Mitigating timing leakage using batch commits
- 8:15 Overall CODoH design and implementation overview
- 10:00 CODoH performance evaluation results and takeaways
CODoH: Privacy-Preserving Caching for Oblivious DNS over HTTPS
Speakers: Pankaj Niroula, Paper author, William & Mary; Lily Gloudemans, Paper author, William & Mary; Aashutosh Poudel, Paper author, William & Mary; Collin MacDonald, Paper author, William & Mary; Stephen Herwig, Paper author, William & Mary
Conference: PETS
YouTube: https://www.youtube.com/watch?v=QDFS79jciew
Overview
This article delves into CODoH: Privacy-Preserving Caching for Oblivious DNS over HTTPS, a groundbreaking work presented at PETS that addresses a critical challenge in modern privacy-preserving DNS architectures. Oblivious DNS (ODNS), exemplified by services like Apple's iCloud Private Relay, enhances user privacy by decoupling a client's IP address from their DNS queries. While this two-hop architecture significantly improves unlinkability, it traditionally comes at a substantial performance cost due to the inherent difficulty of implementing caching without reintroducing privacy leaks. This talk presents CODoH as a robust solution, demonstrating how intelligent design can restore the performance benefits of caching while maintaining, and even strengthening, the privacy guarantees of ODNS.
The research behind CODoH, a collaborative effort by Pankaj Niroula, Lily Gloudemans, Aashutosh Poudel, Collin MacDonald, and Stephen Herwig from William & Mary, tackles the complex interplay between performance optimization and privacy preservation in distributed systems. The talk highlights that a naive approach to caching in ODNS creates severe side channels, allowing a powerful adversary (specifically, the proxy operator) to infer sensitive user information. CODoH systematically identifies and mitigates these leakages through a combination of cryptographic techniques and oblivious protocols, proving that high performance and strong privacy are not mutually exclusive in the context of DNS resolution.
The significance of CODoH cannot be overstated in an era where internet privacy is increasingly under threat. As more services adopt encrypted and oblivious DNS protocols, ensuring their scalability and efficiency without compromising the very privacy they aim to protect becomes paramount. By offering a practical and thoroughly evaluated method for privacy-preserving caching, CODoH paves the way for wider adoption of ODNS, providing users with both enhanced privacy and a responsive browsing experience. This work is a crucial step forward in the evolution of secure and private internet infrastructure, demonstrating how careful architectural design can overcome fundamental trade-offs.
Background
▶ Watch: Oblivious DNS (ODoH) and caching challenges (1:00)
The evolution of DNS has seen a continuous push towards greater security and privacy. Historically, DNS queries were sent in plaintext, allowing any eavesdropper on the network to observe a user's browsing activity. Even with the advent of Encrypted DNS protocols like DNS over HTTPS (DoH) and DNS over TLS (DoT), which encrypt DNS traffic in transit, a fundamental privacy problem persists: the recursive resolver still sees both the client's IP address and the plaintext query. This centralization of information allows a single entity to compile a comprehensive profile of a user's online behavior, making it a tempting target for surveillance and data aggregation.
To address this, Oblivious DNS (ODNS) emerged as a more privacy-centric architecture. ODNS, as implemented in services such as Apple's iCloud Private Relay, splits the traditional resolver function into two distinct, non-colluding entities: a proxy and a target. The client encrypts its DNS request end-to-end to the target resolver. The request is then sent via the proxy. In this setup:
- The client encrypts its query such that only the target can decrypt it.
- The proxy sees the client's IP address but has no visibility into the encrypted query content.
- The target receives the query in plaintext but only sees the proxy's IP address, not the original client's IP.
This design ensures that neither the proxy nor the target possesses both pieces of sensitive information (client IP and DNS query), thereby preventing either entity from linking a specific user to their browsing history. This unlinkability is a core privacy guarantee of ODNS.
However, this enhanced privacy comes with a significant performance drawback. To maintain unlinkability, ODNS protocols typically employ fresh nonces for each request. This means every query is unique, even if it's for the same domain, preventing a proxy from simply caching responses and serving them directly. Consequently, every request must traverse both the proxy and the target, leading to increased latency. The talk highlights that ODNS incurs a median latency of 40 milliseconds, compared to 30 milliseconds for a classic, unencrypted DNS resolution, representing a substantial performance degradation.
The challenge, therefore, is to reintroduce the performance benefits of a shared cache into the ODNS architecture without undermining its fundamental privacy guarantees. A naive shared cache, however, immediately introduces severe side channels. The speaker identifies the proxy operator as the strongest adversary in this context, capable of:
- Timing attacks: An adversary can infer whether a query has been previously made by observing response times. A fast response indicates a cache hit, while a slow one indicates a miss. This leaks information about other users' queries.
- Probing: The proxy can deliberately query domains to populate or test the cache.
- Cache killing/restarting: Manipulating the cache state to observe its effects.
- Isolating victim queries: Targeting specific clients or queries.
- Dropping tricky resource inserts: Selective caching.
- Watching timing and memory access patterns: Observing which entries are accessed within the cache.
To successfully integrate caching, CODoH must guarantee three critical properties:
- The proxy must never respond to the client with an unauthorized response. All responses must be signed and verified by the target to prevent poisoning.
- All cache hits must look like misses. This means that operations, validations, and timings must be equalized, making it impossible for the proxy to distinguish between a cached response and one fetched from the target.
- The proxy should not be able to tell if two requests are the same, even if they map to the same cached entry, preserving unlinkability.
These requirements form the bedrock upon which CODoH is built, aiming to restore performance without sacrificing the essential privacy benefits of Oblivious DNS.
Key Findings
▶ Watch: Three key requirements for privacy-preserving cache (3:30)
The research presented on CODoH makes several pivotal findings that redefine the feasibility of high-performance, privacy-preserving DNS. The core discovery is that while Oblivious DNS (ODNS) significantly enhances user privacy by preventing the linking of client IPs to DNS queries, this privacy comes at a notable cost to performance due to the inherent inability to leverage traditional caching mechanisms. The talk quantifies this performance penalty, noting a median latency of 40 milliseconds for ODNS compared to 30 milliseconds for classic DNS.
A crucial finding is the identification and systematic mitigation of the critical privacy leaks that arise when attempting to introduce a shared cache into an ODNS architecture. The researchers precisely detail three primary leakage vectors that a powerful adversary, such as the proxy operator, could exploit: cache content enumeration (bit key leakage), timing attacks, and access pattern leakage. Each of these vectors, if left unaddressed, could completely undermine the privacy guarantees of ODNS.
CODoH's central contribution is its comprehensive solution that successfully integrates caching into ODNS by neutralizing these side channels. The key findings related to these mitigations include:
- Cover responses effectively obfuscate cache content enumeration, preventing the proxy from discerning a client's specific query amidst a set of dummy responses. The probability of identifying a real query is reduced to 1/(k+1), where k is the number of cover responses.
- Batch commits neutralize timing attacks by aggregating multiple cache updates and releasing them simultaneously, making it impossible to link a specific query to an instantaneous cache update event. This improves privacy to 1/(1+PK), where PK is a privacy-performance parameter.
- Path-ORAM (Oblivious RAM) eliminates access pattern leakage by ensuring that every memory access within the cache enclave appears random and indistinguishable, preventing the proxy from inferring which specific DNS records are being queried.
Perhaps the most compelling finding is CODoH's demonstrated performance superiority. Through rigorous evaluation, the system was shown to be remarkably faster than existing Opaque DNS implementations:
- 2.7 times faster in warm workloads, where cache hits are frequent.
- 2.4 times faster in realistic zipf-distributed workloads, which better reflect typical internet traffic patterns.
- Only 0.9 times slower (i.e., marginally slower) in cold workloads where all requests result in cache misses, demonstrating that the overhead of the privacy-preserving mechanisms is minimal even in the worst-case scenario.
These results conclusively show that CODoH achieves its performance benefits "without leaking out the sensitive information of knowledge" and "without losing the privacy." This work fundamentally alters the landscape for privacy-preserving DNS, providing a practical, high-performance solution that was previously considered an intractable problem due to the inherent conflict between caching and unlinkability.
Technical Deep Dive
▶ Watch: Solving bit key leakage with cover responses (5:50)
The technical ingenuity of CODoH lies in its meticulous design to introduce caching into an Oblivious DNS (ODNS) architecture while preventing the emergence of privacy-compromising side channels. The foundation of CODoH involves placing the shared cache within a Trusted Execution Environment (TEE), specifically an enclave, at the proxy. A TEE offers strong guarantees regarding the confidentiality and integrity of the data and code running within it, meaning the proxy operator cannot directly inspect or tamper with the cache's contents.
However, the talk critically highlights a key limitation of TEEs: they do not inherently hide access patterns. While the content of the cache entries is protected, an attacker (the proxy operator) can still observe which entries are being accessed, when they are disclosed, and which memory regions are being touched. This means that merely putting a cache in an enclave is insufficient for privacy-preserving caching in ODNS. CODoH addresses these specific leakages through a multi-pronged approach:
Mitigating Cache Content Enumeration (Bit Key Leakage)
The Attack: The speaker describes a "subtle difference attack" where the proxy can enumerate the cache's contents. An adversary takes a snapshot of the cache's entry list, blocks traffic, allows a single client query to pass through, and then takes another snapshot. The difference between the two snapshots reveals the query made by the client. This allows the proxy to learn exactly what a specific client has queried.
CODoH's Solution: Cover Responses. To counter this, CODoH employs cover responses. For every legitimate client request, the target (the second hop in ODNS) is instructed to respond not only with the real DNS answer but also with k additional cover responses for randomly chosen, non-existent, or unrelated domain names. These cover responses are cryptographically indistinguishable from real responses to the proxy.
- When the proxy takes its second snapshot, it observes k+1 new entries in the cache (the real response plus k cover responses).
- The probability of identifying the client's actual query is thus reduced to 1/(k+1). This significantly increases the anonymity set for each query, making it much harder for the proxy to link a specific client to a specific domain. The cover responses effectively introduce noise that obscures the true signal.
Mitigating Timing Leakage
The Attack: Even with cover responses, an instantaneous event of k+1 new entries appearing in the cache could still signal to the proxy that a query has been made and that a specific batch of responses arrived. If the proxy could correlate the arrival of these k+1 entries with a client's request, it could still infer activity, even if the specific query remains ambiguous within the anonymity set.
CODoH's Solution: Batch Commits. To prevent this timing side channel, CODoH utilizes batch commits. Instead of immediately writing new responses (real + cover) to the cache upon arrival, these responses are held in a pending tree within the enclave. They are only committed to the main cache in large batches, when a "large anonymity set" of pending queries has accumulated.
- This mechanism mixes many distinct queries together, making it impossible for the proxy to link an instantaneous cache update event to any single client's request.
- The speaker notes that the probability of identifying a victim's domain becomes at most 1/(1+PK), where PK is a privacy-performance parameter that balances the size of the batch (anonymity) with the latency introduced by waiting for the batch to fill. This ensures that the timings of cache updates are decoupled from individual client requests.
Mitigating Access Pattern Leakage
The Attack: Even if the cache's contents are protected and updates are batched, a TEE does not hide which specific memory locations or cache entries are being accessed. If the proxy observes that querying a particular domain consistently "lights up" the same set of memory pages or indices within the enclave, it could infer that the same underlying query is being processed, thereby linking activities.
CODoH's Solution: Path-ORAM (Oblivious RAM). To address this, CODoH integrates Path-ORAM (Oblivious RAM). ORAM is a cryptographic primitive designed to obscure memory access patterns. In Path-ORAM, every access to the cache (whether a read or a write, a hit or a miss) involves a series of operations that are indistinguishable from each other.
- When a cache entry is accessed, Path-ORAM ensures that not only the requested data is retrieved but also a series of dummy operations are performed, touching other random memory locations.
- This makes every access pattern appear statistically identical to an observer outside the enclave (the proxy), preventing the proxy from discerning which specific DNS record was truly accessed. All operations, regardless of whether they are actual data accesses or dummy operations, appear as random memory operations.
Overall Design and Implementation
The overall design of CODoH integrates these mitigations into the ODNS flow. When a client makes a query:
- The query is sent to both the proxy (which hosts the CODoH enclave) and the target.
- If the query results in a cache hit within the proxy's TEE-protected cache, the proxy can respond directly and quickly.
- If it's a cache miss, the query proceeds to the target, as in baseline ODNS. The target then responds, and this response (along with cover responses) is eventually committed to the proxy's cache via batch commits.
Crucially, the system ensures that "all the hits must look like a miss itself," meaning the external timing and observable operations for a cache hit are indistinguishable from those of a cache miss that goes all the way to the target. This equality is maintained through Path-ORAM and batch commits. The system is deployed as an Opaque DNS plugin, building upon existing ODNS infrastructure. The speaker notes that in the "unkeyed" scenario (referring to the indistinguishable operations), regardless of hit or miss, "everything's same in the unkeyed itself," with "very few operations being run over there."
The evaluation conducted an "apple to apple comparison" using identical infrastructure across three different regions. The results conclusively demonstrate the efficacy of CODoH: 2.7 times faster than Opaque DNS in warm workloads, 2.4 times faster in realistic zipf workloads, and only 0.9 times slower (a marginal overhead) in cold workloads. This rigorous technical design and validation confirm CODoH's ability to deliver both privacy and performance.
Demo / Proof of Concept
▶ Watch: Overall CODoH design and implementation overview (8:15)
While the talk did not feature a live, interactive demonstration during the presentation itself, the researchers clearly indicated that CODoH is a fully implemented and evaluated system. The speaker mentioned that the solution was deployed as an Opaque DNS plugin, suggesting a functional prototype built upon existing Oblivious DNS frameworks.
The detailed performance evaluation, comparing CODoH against existing Opaque DNS configurations across "identical infrastructure across three different other regions," serves as compelling evidence of a working proof of concept. The presentation of specific performance metrics (e.7 times faster, 2.4 times faster, 0.9 times slower) for various workload types (warm, zipf, cold) further underscores that the system has been rigorously tested and validated in a practical setting.
The speaker also alluded to having a "happy previous session in the poster," implying that additional details, perhaps including static visual demonstrations or further technical specifications of the implementation, were available during a related poster session at the conference. This suggests that interested attendees had opportunities to engage with the technical artifacts of CODoH beyond the main presentation.
Defensive Implications
▶ Watch: CODoH performance evaluation results and takeaways (10:00)
The CODoH research provides critical insights and actionable intelligence for various stakeholders involved in deploying, securing, and advocating for privacy-preserving internet protocols. Its defensive implications are profound, offering a roadmap for enhancing both the performance and resilience of Oblivious DNS architectures.
For ODNS Service Providers and Operators (e.g., Apple, Cloudflare): CODoH offers a robust and thoroughly evaluated solution to a major bottleneck in ODNS adoption: performance. By demonstrating how to safely integrate caching, CODoH enables providers to offer a significantly faster user experience without compromising the core privacy guarantees that differentiate ODNS. This means ODNS can become a more viable and attractive option for mainstream internet usage, potentially accelerating its deployment and user base. Implementing CODoH-like mechanisms can reduce operational costs by decreasing upstream traffic to target resolvers and improving overall network efficiency.
For Network Defenders and Security Architects: The work highlights the subtle yet powerful side channels that can emerge even in cryptographically secured systems. The systematic identification and mitigation of cache content enumeration, timing attacks, and access pattern leakage provide a valuable blueprint for designing and auditing other privacy-sensitive distributed systems. Defenders must be aware that simply encrypting data or using Trusted Execution Environments (TEEs) is often insufficient; additional oblivious techniques are required to hide metadata and access patterns. The emphasis on signed and verified responses is also a crucial defensive reminder, preventing cache poisoning attacks regardless of the caching mechanism.
For Developers of Privacy-Preserving Protocols: CODoH serves as an excellent case study for how to approach performance optimization in privacy-sensitive contexts. It underscores the necessity of a holistic threat model that considers powerful adversaries capable of observing not just data content, but also operational metadata like timings and access patterns. The specific techniques—cover responses, batch commits, and Path-ORAM—are powerful tools that can be adapted to other protocols where unlinkability and resistance to side-channel attacks are paramount. This research encourages a shift from simply protecting data to protecting the information flow itself.
For TEE Implementers and Users: The talk explicitly points out the limitations of TEEs in hiding access patterns. This is a critical defensive insight: TEEs provide strong guarantees for confidentiality and integrity of code and data within the enclave, but they do not inherently make memory access patterns oblivious. Therefore, any application within a TEE that handles sensitive data or processes requests based on a shared state must integrate additional mechanisms, such as ORAM, to prevent leakage through observed memory accesses. This understanding is vital for correctly assessing the security posture of TEE-based solutions.
In essence, CODoH empowers defenders to build more efficient and privacy-preserving internet infrastructure. It moves beyond theoretical privacy guarantees to offer a practical, high-performance solution that addresses real-world challenges, making privacy-by-design a more attainable goal for critical internet services.
Key Takeaways
- Oblivious DNS (ODNS) enhances privacy by decoupling client IP from DNS queries but suffers significant performance overhead due to the inability to cache responses while maintaining unlinkability.
- Naive caching in ODNS reintroduces critical privacy leaks, enabling a powerful adversary (like the proxy operator) to infer client queries through side channels such as cache content enumeration, timing attacks, and access pattern observation.
- CODoH effectively mitigates these side channels using a multi-pronged approach: cover responses for content obfuscation, batch commits for timing equalization, and Path-ORAM (Oblivious RAM) for obscuring memory access patterns within a Trusted Execution Environment (TEE).
- CODoH delivers substantial performance improvements for ODNS, making it 2.7 times faster in warm workloads and 2.4 times faster in realistic zipf workloads, while incurring only a marginal 0.9 times slower overhead in cold (all-miss) scenarios.
- This work demonstrates that high performance and strong privacy are not mutually exclusive in ODNS, providing a practical and scalable solution for privacy-preserving DNS that can accelerate its adoption.
- Implementing caching in privacy-sensitive protocols requires a deep understanding of TEE limitations and the strategic application of oblivious techniques to prevent insidious access pattern and timing leakages.
About the Speaker(s)
The work presented in this talk, "CODoH: Privacy-Preserving Caching for Oblivious DNS over HTTPS," is a collaborative effort by Pankaj Niroula, Lily Gloudemans, Aashutosh Poudel, Collin MacDonald, and Stephen Herwig, all affiliated with William & Mary. Their research focuses on advancing the performance and privacy of internet protocols, particularly in the realm of DNS. The team's expertise lies in designing robust solutions that tackle complex trade-offs between system efficiency and user privacy in distributed network environments.
Reviews
Dr. Zero (Offensive Security Researcher) — STRONG ACCEPT
This is how you actually do privacy engineering. Instead of treating TEEs like a magic black box that magically solves all side-channels, the William & Mary team actually did the math on access pattern leakage and built a cryptographically sound caching layer for Oblivious DNS. It's a pragmatic, high-impact fix for the latency tax that currently holds back widespread ODNS adoption.
Heather Calloway (CISO) — WEAK
For most enterprise security teams, this talk is a pass—you are not building custom Oblivious DNS infrastructure. However, if you are a CISO at a major service provider or telecom, this is important protocol engineering that proves the latency penalties of privacy-preserving network architectures can be engineered away.
→ Top-rated talks at Privacy Enhancing Technologies Symposium (PETS) 2026
All talks from Privacy Enhancing Technologies Symposium (PETS) 2026