{"id":"b135a702-e22a-4992-8fed-43c353e30834","arxiv_id":"2507.20806","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"PDNS integrates single-server PIR into DNS so a resolver responds without seeing the requested domain, with a prototype and measurements, but it shifts some query exposure to authoritative name servers and handles only a few queries per second.","lead":"PDNS is a DNS design that lets a recursive resolver answer queries encrypted with private information retrieval so the resolver never learns which domain is being asked for. The paper includes a working prototype, a BIND9 change for cache misses, and measurements showing PDNS is faster than DNS over Tor but far less scalable than standard DoH.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Collusion resistance rests on an unverified, and in §9 partially conceded, premise that final ANSes already learn users' queries from subsequent traffic; one colluding ANS or multi-service operator can break the 'no trust assumptions' claim.","rationale":"The reader's weakest assumption is exactly the load-bearing premise I identify: the claim that exposing the full query and user IP to the final ANS during cache misses adds no privacy loss because ANSes already learn this from subsequent traffic. The paper's own §9 undermines this premise by conceding that third-party ANSes (e.g., Route 53) do not already have such access, and by deferring a PIR-based fix to future work. Moreover, the threat model names the ReR as the covert adversary; the argument that 'ANSes are not critical' addresses whether the ANS learns something new, not whether the ReR learns something new via a colluding ANS. A single realistic collusion between one large ANS and the ReR — or a single multi-service company operating both — breaks the 'no trust assumptions' and 'survive non-collusion violation' claims. This is not an abstract theoretical worry: Cloudflare, Google, and Amazon operate both public resolvers and large authoritative DNS services, so the fraction of affected queries is plausibly substantial. The proposed concrete test directly measures the empirical premise with trace data; if the premise fails, the conditional verdict is justified. Other concerns (e.g., benchmarking fairness, scalability, missing artifacts) are real but secondary; the privacy-parity claim is the central one. The reader's CONDITIONAL verdict already captures the need to temper the privacy claims, so I recommend no change to that verdict. Credit is due for the prototype, the cache-population mechanism, and the security analysis; the concern is specifically with the overstatement of the privacy guarantee.","tokens_in":35470,"tokens_out":8949,"duration_ms":103903,"concrete_test":"Using a public DNS/connection trace (or the paper's Mysterium trace if released), for each direct cache-miss query to a final ANS, check whether the same client IP later opens a TCP/HTTP(S) connection to the resolved IP or the queried domain within the TTL, and classify the ANS as first-party (same operator as the site) or third-party. Report the fraction of cache-miss queries where no such connection exists or where the ANS is third-party; if that fraction is non-negligible (e.g., >5%), the 'no additional information' premise fails and the collusion resistance claim must be weakened. Additionally, compute the fraction of domains whose final ANS is operated by the same company as a major public ReR; if non-zero, a single multi-service company can link identity to query without any cross-party collusion.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central privacy claim (abstract, §3.1, §7.1) is that PDNS provides the same protections as DoHoT without trust assumptions, because exposing query+IP to the final ANS on cache miss 'adds no additional information' since 'ANSes are likely already gaining information about users from users' subsequent traffic' (§3.1, citing [73]). This premise is load-bearing in two ways. First, the threat model treats the ReR as the covert adversary that 'might track and inspect DNS queries'; a final ANS that colludes with (or is the same company as) the ReR can simply hand over the query+user-IP pair from the cache-miss path, giving the ReR exactly the link PDNS is designed to hide. The fact that the ANS already knows the query does not make the query known to the ReR. Second, the paper itself concedes in §9 ('Third-Party Final ANSes') that for third-party ANS services such as Route 53, PDNS 'would leak some information to a third party which does not already have access to this information via direct traffic,' and defers a fix to future work. Thus the 'no additional information' premise is admitted to be false for a large class of real deployments, and the paper's restriction to 'realistic collusion... not among millions of ANSes' does not help because a single large ANS (or one Google/Cloudflare operating both ReR and ANS, discussed in §9) suffices. Without this premise, PDNS's 'Survive Non-Collusion Violation: Yes' (Table 1) and the abstract's parity with DoHoT are conditional on the unstated assumption that no final ANS ever cooperates with the ReR. The §9 claim that PDNS 'stands out' for multi-service companies is internally inconsistent, since such a company's ANS and ReR trivially share the user's identity and query.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"PDNS is a DNS privacy extension that integrates single-server PIR (Spiral) into the recursive resolver (ReR). A user hashes the queried domain to a cache slot, encrypts the slot index, and the ReR evaluates the PIR answer over an encoded cache without learning the domain; to populate the cache after a miss, the user performs the iterative lookup directly and the final authoritative name server (ANS) forwards the record to the ReR via the paper's EDNS-PR extension, with randomized delay to hinder timing correlation. The paper claims that PDNS removes the proxy non-collusion assumption that limits ODoH, achieves median query latencies of 208 ms (64 MB cache) versus 272 ms for ODoH, and is about 2x faster than DoH over Tor, with privacy guarantees 'similar' to DoHoT, at the cost of scalability (4-8 QPS per ReR). The contributions include a working prototype (Rust Spiral client/ReR, ~200-line BIND9 patch), trace-driven evaluation over 1,415 residential VPN nodes and 122K domains, a cache-miss proof mechanism to defend reflection attacks, and a deployment cost model.","tokens_in":35822,"tokens_out":25490,"duration_ms":267995,"significance":"If taken at face value, the ReR-blind query path is a meaningful advance: it removes the trusted proxy from the query path entirely, and the PIR construction rests on the published LWE-based security of Spiral rather than on fitted parameters; the cache shape, PIR choice, and throughput numbers are measured engineering decisions, and the paper reports the 4-8 QPS bottleneck and its cost model transparently. The paper also deserves credit for shipping an open-source prototype and for honestly disclosing its limitations (anycast, scalability, third-party final ANSes). The significance is nevertheless conditional: the headline parity with DoHoT and the 'Survive Non-Collusion Violation: Yes' entry in Table 1 hold only if exposing (user IP, full domain) to final ANSes on cache misses is privacy-neutral, a premise that Section 3.1 hedges with 'likely' and Section 9 partially retracts for Route 53-class deployments. As a system that distributes DNS exposure across many ANSes rather than concentrating it at one resolver, PDNS is a credible and useful contribution; as a no-trust-assumptions protocol it is not yet demonstrated.","major_comments":[{"comment":"The load-bearing premise of the paper's central claim is stated in Section 3.1: a cache-miss query that reveals the full domain and the user IP to the final ANS 'does not leak any extra private information about a user than what the subsequent traffic directed to the domain' reveals, because 'ANSes are likely already gaining information about users from users' subsequent traffic [73].' This premise converts the design's inherent exposure of (IP, domain) to final ANSes into the abstract's 'similar privacy guarantees' to DoHoT and into the 'Survive Non-Collusion Violation: Yes' entry for single-server PIR in Table 1, and it is not established. First, the paper provides no evidence that the final ANS that serves a user's cache-miss query also observes that user's subsequent HTTP(S) traffic, and the claim is contradicted by the paper's own Section 9, which admits that for third-party ANS services such as Route 53, PDNS 'would leak some information to a third party which does not already have access to this information via direct traffic,' with the fix deferred to future work. Second, even if the ANS already knew the query, that does not make it known to the ReR: a single colluding ANS can transmit the (domain, user IP) pair to the ReR over the cache-population path (or simply omit the randomized delay), giving the ReR exactly the link the PIR query was designed to hide. The Section 3.1 restriction to 'realistic collusion... not among millions of ANSes' does not bound this threat, because one colluding ANS, or one multi-service operator such as Google or Cloudflare (discussed in Section 9), suffices. DoHoT, with which the paper claims parity, hides the user IP from the resolver entirely; PDNS does not. The abstract, Table 1, and Section 7.1 therefore overstate the guarantee: either the claims must be scoped to non-collusion between the ReR and the final ANS (which makes PDNS a different trade-off than advertised), or the PIR-at-the-ANS mechanism of Section 9 must be moved into the design rather than left as future work.","section":"§3.1, §7.1, Table 1, abstract; §9 'Third-Party Final ANSes'"},{"comment":"The timing-attack defense is load-bearing for the cache-miss path, because the ReR learns the domain when the ANS populates the cache, and the randomized delay is the only mechanism preventing the ReR from correlating that event with the user IP and query time it already observes. The Appendix G analysis supports a weaker conclusion than the Section 7.2 claim that PDNS 'effectively thwarts' timing attacks. For the uniform delay U(0, 2Δ) proposed in Section 4.2, Equation (2) yields entropy exactly at the threshold Te ≈ 0.69 nats, i.e., two equiprobable candidate queries, so the ReR can attribute a given population event to the correct user with 50% probability per miss. Over the paper's measured ~10% miss rate, with the ReR knowing the source IP and exact time of every PIR query, a 50%-accurate per-event signal is a substantial accumulation of user-to-query links rather than a thwarted attack. The model also assumes equally spaced queries made by different users (Figure 9), which is violated by the bursty traffic documented in Appendix F; under bursts, Δ shrinks and the candidate set for U(0, 2Δ) shrinks with it. The authors should report the per-event correlation success probability rather than a threshold-satisfying entropy, justify choosing the geometric distribution from Figure 10 for the actual design, and analyze the bursty regime.","section":"§4.2, §7.2, Appendix G"}],"minor_comments":[{"comment":"The sentence 'PDNS is slightly faster than DoH and ReR-Less DoH assuming a small cache, and no connection reuse' cannot be right as written, since PDNS is 208 ms and DoH is 69 ms; 'ODoH' was presumably the intended comparison, as ODoH is 272 ms without reuse.","section":"§7.1"},{"comment":"The '2x faster than DoH over Tor' claim should state which cache configuration it refers to: the introduction says the factor holds 'even on a large cache (512MB)', while Section 7.1 gives 208 ms (small cache) and 450 ms (large cache) and never reports the DoHoT median used for comparison; the two sections should be reconciled and the DoHoT baseline number reported.","section":"Abstract, intro, §7.1"},{"comment":"The exponent notation is lost in '216 slots' (Figure 2 caption) and '215 slots with a size of 16KB' (Section 6.2); these should read 2^16 and 2^15, and the same check should be applied to '210', '220', and similar values elsewhere in Section 6.2.","section":"Figure 2 caption, §6.2"},{"comment":"Reference [8], labeled 'Google Cloud Pricing Calculator', points to the same AWS calculator URL as reference [1]; the Google Cloud link appears to be a copy-paste error and should be corrected.","section":"References [1], [8]"},{"comment":"The threshold Te ≈ 0.69 is evaluated with natural logarithms, but the base is never stated; because the numerical value of the entropy depends on the base, the analysis should state the base or report entropy in bits.","section":"Appendix G"},{"comment":"The 'preserving regional access pattern' analysis treats large absolute domain-popularity rank differences between PDNS and ground truth as a privacy benefit; rank perturbation is an observation about how the PIR slot-return distribution reshapes cache-visible statistics, not a demonstrated privacy guarantee, and the framing should be softened or argued more carefully.","section":"§7.2, Figure 4(c)"},{"comment":"The DoHoT durations are collected from a single laboratory location, while PDNS numbers are obtained by injecting 1,415-node Mysterium latencies; the paper discloses this asymmetry, but the headline 2x comparison would be considerably more robust if both protocols were measured over the same client population.","section":"Appendix E.1, §7.1"}],"recommendation":"major_revision","confidential_remarks":"The engineering contribution is real, and the PIR-at-the-ReR concept is publishable if the claims are scoped honestly. My central concern is that the abstract and Table 1 promise 'no trust assumptions' and 'similar privacy guarantees' to DoHoT, while the design inherently exposes (user IP, full domain) to the final ANS on every miss and Section 9 concedes this leak for third-party ANSes like Route 53. I would recommend the authors either reposition PDNS as distributing exposure across ANSes (with an explicit comparison of the ReR-ANS collusion surface against ODoH's proxy-ReR surface), or implement the PIR-at-ANS mechanism for the miss path instead of deferring it. The timing-attack section also needs per-event success probabilities rather than threshold entropies. The paper fits cs.NI well despite the security-adjacent content."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is worth reading. It is the first working prototype I know of that combines single-server PIR with a mechanism for populating a recursive resolver's cache without leaking the query. The EDNS-PR extension, the client-driven iterative lookup, and the cache-miss proofs are concrete, sensible design choices. The performance study is careful, trace-driven, and honestly reports the big limitation: a PDNS resolver handles only a handful of queries per second, which the authors admit makes it a niche product today unless specialized PIR hardware arrives.\n\nThe central privacy claim is the soft spot. The abstract says PDNS gives 'similar privacy guarantees' to DoHoT with 'no trust assumptions.' That is not true for cache misses. On a miss, the final authoritative name server sees the user's IP and the full domain. The paper argues this adds no information because those ANSes already learn the same thing from subsequent HTTP(S) traffic. That is an empirical claim, and no evidence supports it. Worse, Section 9 concedes that with third-party ANSes like Route 53, PDNS leaks information to a party that does not already have it. One large ANS that colludes with, or is owned by, the resolver can therefore hand the resolver exactly the query-identity link PDNS is designed to hide. Table 1's 'Survive Non-Collusion Violation: Yes' is conditional on the unstated assumption that no final ANS cooperates with the resolver. That is a weaker guarantee than DoHoT, which hides the user's IP from the resolver entirely. The claim should be tempered from a categorical 'yes' to 'resistant against resolver-proxy collusion, at the cost of trusting a large set of ANSes not to collude.'\n\nThe cryptographic core, by contrast, is on solid ground. The security rests on Spiral and standard LWE assumptions; there is no circular fitting. The free parameters are engineering choices and projections, clearly labeled. The F1 5ms assumption is optimistic but flagged as futuristic.\n\nMinor points: no code or data is released, which hurts reproducibility for a systems paper; and the timing-attack analysis, while a nice idea, assumes independent responses from all ANSes and equal query intervals, which simplifies real traffic considerably.\n\nThe paper deserves a serious referee. A good review will push the authors to rewrite the abstract, qualify the ANS premise, and either release artifacts or provide a stronger justification. I would not cite the privacy-parity claim as stated, but I would cite the system design and the cache-population approach.","headline":"A genuine PIR-based DNS prototype that solves cache population, but the privacy parity with DoHoT is overstated and the collapse of the ANS premise makes 'collusion resistant' conditional, not absolute.","tokens_in":36433,"tokens_out":1872,"would_cite":true,"duration_ms":25280,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"PDNS lets DNS resolvers answer queries without learning the domain.","keywords":["DNS privacy","Private Information Retrieval","collusion resistance","Oblivious DoH","recursive resolver","homomorphic encryption","EDNS","DNS caching"],"falsifier":"Inspect real PDNS cache-miss traces and check whether, for each miss, the authoritative server for the domain would independently observe HTTP(S) traffic from the same user IP to that domain within the record's TTL; if a large fraction of misses are never followed by such traffic, PDNS's parity-with-Tor privacy argument collapses.","tokens_in":35276,"feed_emoji":"🔒","tokens_out":8511,"duration_ms":87410,"temperature":0.7,"pith_summary":"The paper tries to establish that DNS privacy can be made collusion-resistant without removing recursive resolvers, by having resolvers answer queries blindly through single-server Private Information Retrieval. The proposed PDNS lets a recursive resolver compute PIR answers over its cache so it never learns which domain was queried, removing the non-collusion assumption that ODoH needs between proxy and resolver. To keep caches populated, a client that hits a cache miss performs the iterative lookup itself, and the final authoritative name server privately refills the resolver's cache via a new EDNS extension. The price is that a user's IP and domain are visible to the final authoritative server on cache misses, which the paper argues is acceptable because those servers already see the user's subsequent traffic and because caching limits misses to a small fraction of queries. If the argument holds, PDNS gives users today a practical, financially viable alternative to Tor-based DNS that is about twice as fast.","feed_headline":"DNS queries stay hidden from the resolver itself","feed_subtitle":"PDNS adds private information retrieval, drops the non-collusion bet, and beats Tor-based DNS on speed.","key_machinery":"The load-bearing mechanism is single-server stateless PIR, specifically the Spiral scheme, which lets a user fetch one slot of a pre-encoded database without revealing the index. PDNS wraps Spiral in a DNS workflow: a public hash maps each domain to one of $2^{15}$ slots of 16 KB in a 512 MB cache, the resolver encodes the whole cache once, and each query is answered homomorphically. On a cache miss, a new EDNS(0) option called EDNS-PR carries the resolver's IP address to the final authoritative name server, which then refills the resolver's cache with a randomly delayed response to blunt timing correlation. DNS records are reshaped for the scheme by replacing the domain name with a 16-byte hash and the TTL with an expiration timestamp, so expired entries can be resolved in a single direct hop to the authoritative server.","core_discovery":"PDNS claims that a recursive resolver can resolve DNS queries while staying blind to the queried domain, using single-server stateless PIR (Spiral) over a fixed-size hash-table cache. On a cache hit, the user hashes the domain to an index, encrypts it, and the resolver homomorphically returns the whole matching slot, so the resolver learns neither the index nor the slot content. On a cache miss, the client performs the iterative lookup itself and the final authoritative name server sends the fresh record back to the resolver through an EDNS-PR extension, populating the cache without exposing the client's IP to the resolver. The paper argues this shifts privacy exposure from one central resolver (or resolver-proxy pair) to many authoritative servers, that this exposure is acceptable, and that caching keeps it small. In trace-driven experiments PDNS achieves median query times of 208 ms with a 64 MB cache, faster than ODoH's 272 ms and about twice as fast as DNS over Tor, at the cost of a resolver throughput of only 4-8 queries per second on an 8-core server.","pith_inferences":["If the claim that final authoritative servers already see users' subsequent traffic fails for a large fraction of real users, PDNS's privacy guarantee would reduce to 'resolver learns nothing, final ANS learns query and IP on misses,' which is still stronger than DoH but not equivalent to Tor.","The cache-refill mechanism generalizes to other hierarchical systems with shared caches, such as certificate transparency logs or blockchain light clients, wherever a cache must be populated without revealing who asked for what.","A direct test of the paper's scalability projection would be to run Spiral's Answer primitive on an FHE accelerator and measure whether query resolution actually falls to the assumed few milliseconds on multi-GB caches."],"forward_implications":["PDNS removes the need to trust a proxy not to collude with a resolver, the assumption that limits ODoH.","PDNS is about twice as fast as DoH over Tor with comparable privacy guarantees, and with a small cache it is faster than ODoH (208 ms versus 272 ms median).","Only cache misses expose queries to authoritative servers; in the paper's traces fewer than 10% of queries miss, and 90% of misses come from expired records that can be resolved directly at the final authoritative server.","With foreseen PIR hardware accelerators, answer time drops to a few milliseconds, making PDNS competitive with plain DoH while retaining collusion resistance."],"supporting_citations":[{"why":"Supplies the Spiral single-server stateless PIR scheme that PDNS selects for its query/answer primitives.","marker":"[91]"},{"why":"Supplies SealPIR, the stateless PIR baseline that PDNS benchmarks and rejects for smaller slots.","marker":"[31]"},{"why":"Supplies the ODoH design and its non-collusion limitation, plus the baseline performance PDNS compares against.","marker":"[116]"},{"why":"Supplies the argument that authoritative name servers already observe user information from subsequent traffic, the basis for accepting ANS exposure.","marker":"[73]"},{"why":"Supplies the DNS client behavior dataset used for cache sizing, query-rate, and subscription-cost analysis.","marker":"[114]"},{"why":"Supplies the F1 FHE accelerator projection that PDNS uses to estimate near-future sub-5ms PIR answers.","marker":"[109]"}],"fun_headline_variants":["PDNS: DNS queries stay private without trusting proxy or resolver","Blind resolver DNS: PDNS uses PIR, beats Tor speed","No collusion needed: PDNS hides DNS queries via PIR","PDNS: Private DNS that outruns Tor and trusts nobody","PIR-powered DNS: Resolver blind, queries hidden, fast"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The paper assumes that when a user's query misses the resolver's cache, the final authoritative name server learning the user's IP and queried domain is not a new privacy loss because that server already sees the user's subsequent traffic to the domain.","fun_headline_variants_meta":{"raw":{"variants":["PDNS: DNS queries stay private without trusting proxy or resolver","Blind resolver DNS: PDNS uses PIR, beats Tor speed","No collusion needed: PDNS hides DNS queries via PIR","PDNS: Private DNS that outruns Tor and trusts nobody","PIR-powered DNS: Resolver blind, queries hidden, fast"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000913,"raw_usage":{"total_tokens":3961,"prompt_tokens":1025,"completion_tokens":2936,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":641,"completion_tokens_details":{"reasoning_tokens":2845}},"tokens_in":641,"tokens_out":2936,"duration_ms":23290,"temperature":1.0,"reasoning_tokens":2845,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T13:14:12.913724+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Inspect real PDNS cache-miss traces and check whether, for each miss, the authoritative server for the domain would independently observe HTTP(S) traffic from the same user IP to that domain within the record's TTL; if a large fraction of misses are never followed by such traffic, PDNS's parity-with-Tor privacy argument collapses.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the Spiral single-server stateless PIR scheme that PDNS selects for its query/answer primitives."},{"cited_title":"Singanamalla, S","cited_arxiv_id":null,"evidence_quote":"Supplies the ODoH design and its non-collusion limitation, plus the baseline performance PDNS compares against."},{"cited_title":"Schomp, M","cited_arxiv_id":null,"evidence_quote":"Supplies the DNS client behavior dataset used for cache sizing, query-rate, and subscription-cost analysis."},{"cited_title":"Samardzic, A","cited_arxiv_id":null,"evidence_quote":"Supplies the F1 FHE accelerator projection that PDNS uses to estimate near-future sub-5ms PIR answers."}],"review_version":1}