{"id":"c43a668a-5487-4b18-ad94-7554a2d8db31","arxiv_id":"2509.08704","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"A one-run privacy audit claims tight lower bounds for general DP algorithms, but the core dominance proof is invalid.","lead":"This paper proposes a one-run privacy audit method that claims to produce tight privacy lower bounds for (ε,δ)-differentially private algorithms, using f-DP and order statistics. The central theoretical guarantee rests on a transmission-dominance theorem whose proof contains an invalid step.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1's proof fails: score-based release can make the original guess's conditional error below the f-DP optimum p*, so replacing it with an independent p*-error guess does not dominate the original framework; the p-value guarantee is unsupported.","rationale":"The paper's central claim is that Theorem 1 reduces any one-run audit to independent f-DP channels, making the order-statistics p-value of Theorem 3/Prop. 1 a valid upper bound. The reader's rejection rests on the invalidity of this reduction. I checked the proof in Appendix B.2 and the flaw is real and specific. In the first domination step, the proof replaces the original guess at coordinate i by an independent optimal channel guess but keeps the original score for filtering. For the replacement to be no worse, the original guess's error on the released subpopulation must be at least p*. The f-DP condition only lower-bounds the unconditional error of any test of b_i; it cannot lower-bound the error after conditioning on the score being among the top r. The paper's own framework is built on the opposite intuition—scores select the most trustworthy guesses—and Figure 11 shows accuracies far above 1-p* for released guesses. Thus the step fails. A second, independent failure is that the proof treats the remaining error sum as if it were independent of E_i; all guesses are functions of the same M output and the release indicators are score-based, so the Bernoulli dominance used in the proof does not extend to the sum. The concrete n=2 Gaussian test isolates the first failure. This is not an objection to the experiments: for the specific product mechanisms and attacks used, the final bound may well be valid, and the empirical improvements over previous work are plausible. But the claimed general theoretical guarantee—valid p-values for all M,H,D—is unsupported. Therefore I concur with the reader's REJECT verdict: the central theorem's proof has a load-bearing gap.","tokens_in":22187,"tokens_out":26893,"duration_ms":306666,"concrete_test":"Numerically test the first domination step in the paper's own product Gaussian mechanism. Let n=2, r=1, M(b)=(b_1+N(0,1), b_2+N(0,1)), D guess a_i=1 iff y_i>0.5 and score s_i=|y_i-0.5|, releasing the coordinate with the largest score. Compute q_orig = Pr[released guess is wrong] via exact integration or 10^7 Monte Carlo samples. Compare to p* = Φ(-0.5) ≈ 0.3085, the error of the independent f-DP channel guess used in Eq. (31). If q_orig < p* (i.e., Pr[event_0] > 1-p* ≈ 0.6915), then the original framework is NOT dominated by the intermediate framework in Appendix B.2, and the proof of Theorem 1 is invalid. This isolates the failing assumption without needing to test the full theorem.","verdict_should_be":"REJECT","load_bearing_attack":"Load-bearing concern: Theorem 1's proof (Appendix B.2, Eq. (31)) is invalid. The first domination step replaces each released guess a_i with an independent optimal f-DP channel guess, while keeping the original score for filtering, and claims the replacement can only improve the error count. This requires that, conditional on the guess being released, the original a_i has error probability at least p* = min_α(α+f(α))/2. f-DP only provides that bound unconditionally: for each fixed B_{>i}, any test of b_i has error ≥ p*. It provides no bound on the error restricted to outputs whose score is in the top r. The filter in Definition 6 is deliberately designed to select the most accurate guesses; the paper's own Figure 11 shows released-guess accuracy can exceed 0.9 while p* ≈ 0.31 for the audited Gaussian mechanism. Hence the released original guess can have error well below p*, so replacing it with an independent p*-error guess increases the expected error count and can decrease Pr[event_u]; the stochastic domination inequality in Eq. (31) is false. Additionally, the proof treats the remaining error sum as if E_i were independent of it, but all guesses are deterministic functions of the same output y of M, and the release indicators depend on y through scores. Marginal Bernoulli dominance does not extend to sums of dependent Bernoulli variables. Because Theorem 3 and Proposition 1 inherit their validity from Theorem 1, the p-value is not established as a valid upper bound for arbitrary M,H,D. The experiments may be valid for the specific attacks, but the central theoretical claim is unsupported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a one-run privacy audit framework in which n secret bits are embedded, the audited mechanism M is run once, a decoder produces guesses and scores, and only the r highest-score guesses are released. Modeling the target mechanism by f-DP, the authors claim (Theorem 1) that every such framework is stochastically dominated by n independent f-DP channels with the optimal decoder and score-based filtering. This reduction is used to compute a tail bound (Theorems 3 and Proposition 1) and a p-value for rejecting the null f-DP guarantee. Experiments on Gaussian, Laplace, DP-SGD, sub-sampled Gaussian, and randomized-response mechanisms report tight lower bounds that improve on prior work.","tokens_in":22585,"tokens_out":9109,"duration_ms":113649,"significance":"If Theorem 1 were correct, the paper would be a significant advance: it would give the first tight one-run audit for general (ε,δ)-DP mechanisms, and the order-statistics treatment of score-based release is a genuinely new idea. The paper also provides an anonymous implementation and extensive experiments, which are valuable. However, the central reduction is not proved and appears false: score-based release can make the conditional error probability of a released guess smaller than the f-DP optimal error, which breaks the stochastic domination. The order-statistics tail bound also implicitly assumes independence of selected error indicators without a supporting argument. Since the validity of the audit p-value rests on these two points, the paper's main claim is not established.","major_comments":[{"comment":"","section":"Appendix B.2, Eq. (31)"},{"comment":"","section":"Theorems 3 and Proposition 1 (Appendices B.4–B.5)"}],"minor_comments":[{"comment":"","section":"Section 5.3, Eq. (20)"},{"comment":"","section":"Proof sketch of Theorem 1"},{"comment":"","section":"Definition 11 / Theorem 2"},{"comment":"","section":"Section 6.4, Figure 12"}],"recommendation":"reject","confidential_remarks":"The flaw in Theorem 1 is not a presentation issue; it is a false stochastic-domination claim. The proof replaces accurate released guesses by independent p*-error guesses while keeping informative scores, which can only worsen the audit's error count. A revision would require a fundamentally different theoretical foundation for score-based audit, not a local patch. The independence gap in Proposition 1 reinforces this assessment. I recommend rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the paper is worth reading for its clean formulation of one-run auditing with score-based filtering and its order-statistics treatment of the release rule. The experiments are extensive and consistently beat prior work. But the load-bearing theoretical claim, Theorem 1, is not established. The proof in Appendix B.2 replaces each released guess with an independent guess from an optimal f-DP channel while keeping the original score, and asserts this can only improve the error count. That step requires the original guess, conditional on being released, to have error probability at least the unconditional optimum p*. The paper gives no such bound, and the filter is designed to select guesses that do better. Their own Figure 11 shows released-guess accuracy above 0.9 when p* is about 0.31 for the Gaussian mechanism. So the conditional error can be below p*, and replacing the guess with an independent p*-error guess can increase the expected error count, breaking the dominance inequality in Eq. (31). The accompanying claim that the remaining errors are independent of the replaced one is also suspect, because all guesses are functions of the same output and the release indicators depend on it.\n\nThe order-statistics computation of the tail probability is fine as a calculation for the independent-channels model, and the experiments may be valid for the specific attacks used. But since Theorem 3 and Proposition 1 inherit their validity from Theorem 1, the claimed p-value is not established as a valid upper bound for arbitrary M, H, D. The paper's central contribution, a tight audit with a theoretically justified confidence statement, depends on that missing piece.\n\nI'd send this to peer review anyway: the question is important, the framework is well laid out, and the flaw is specific enough that a careful referee could either find a fix or force the authors to weaken the claims. But as it stands, the main claim should not be taken at face value.","headline":"Nice framework and experiments, but the proof of the central dominance theorem has a genuine gap: replacing released guesses with independent channel guesses does not preserve the conditional error bound.","tokens_in":23034,"tokens_out":3054,"would_cite":false,"duration_ms":33374,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that any one-run privacy audit of an f-DP mechanism can be reduced to independent f-DP channels, making the resulting privacy lower bound valid and tight even for (ε,δ)-differential privacy.","keywords":["privacy audit","one-run audit","differential privacy","f-DP","order statistics","hypothesis testing","membership inference","privacy lower bound"],"falsifier":"Implement an f-DP mechanism with a deliberately informative decoder, e.g., a Gaussian mechanism where the decoder scores each guess by the posterior P(B_i=1|y) rather than by absolute privacy loss. Fix a known f-DP upper bound, run the audit many times, and compare the empirical frequency of observing at most u errors among the r released guesses with the paper's p-value; an empirical frequency systematically above the claimed bound would refute Theorem 1.","tokens_in":22130,"feed_emoji":"🔒","tokens_out":6657,"duration_ms":71295,"temperature":0.7,"pith_summary":"The paper sets out to prove that a single execution of a differentially private algorithm can yield a tight privacy audit: a valid privacy lower bound with non-trivial confidence, even when the algorithm only satisfies relaxed (ε,δ)-differential privacy. Previous one-run audit methods were provably tight only for pure (ε,0)-DP; for δ>0 they left a gap or failed entirely. The paper locates the difficulty in the way one-run audits release only their most confident guesses, and shows this filtering is best analyzed as an order-statistics problem. Its main theorem reduces any one-run audit of an f-DP mechanism to n independent f-DP channels with an optimal decoder, which converts observed guess errors into a computable p-value. If the theorem holds, expensive algorithms such as DP-SGD can be audited once and still produce lower bounds that meet the known upper bounds.","feed_headline":"One run now yields tight privacy lower bounds for (ε,δ)-DP","feed_subtitle":"Order-statistics filtering bounds released-guess errors, closing a gap earlier one-run audits left open.","key_machinery":"The central objects are the f-DP channel and the base distribution pair (P,Q) whose trade-off function is exactly f. The f-DP channel sends one input bit through P or Q; its optimal decoder is the likelihood-ratio/maximum-a-posteriori rule, which attains the minimal single-bit error probability. The proof works by transmission dominance: step by step, each released guess of the original audit is replaced by an independent f-DP-channel guess while preserving the original score, then the score-filtering step is replaced by ordering the channel's own scores. The filtering action — releasing only the r guesses with largest scores — is analyzed through order statistics of the score samples, yield","core_discovery":"If a mechanism is f-DP, then for any number n of secret bits, any dataset encoder, any score-producing decoder, and any number r of released guesses, the distribution of errors among the r highest-scoring released guesses is stochastically no better than the distribution obtained by sending each bit independently through the f-DP channel and decoding with the optimal likelihood-ratio rule. The scoring-and-filtering procedure in the original audit can be replaced by the channel's own scores without decreasing the probability of observing at most u errors, so the p-value of Theorem 3 and Proposition 1 is a valid upper bound. This closes the gap between audited lower bound and known upper bound","pith_inferences":["A boundary worth probing is whether the dominance reduction is conservative for decoders whose scores directly encode correctness, such as calibrated confidence outputs. The proof replaces a released guess with a fresh f-DP-channel guess holding the score fixed; if scores themselves reveal which guesses are right, the conditional error probability could fall below the marginal optimum and make the","The same order-statistics tail bound could be reused for auditing mechanisms that publish top-k outputs or use private selection, since the released-subset abstraction maps naturally onto selection problems.","The parameter-free treatment of scores gives a clean benchmark for membership-inference attack development: any attack's accuracy translates directly into a lower bound, so attackers only need to maximize expected accuracy rather than tune audit-specific statistics."],"forward_implications":["For Gaussian, Laplace, randomized-response, and DP-SGD mechanisms audited in the paper, the reported lower bound meets the privacy upper bound once n is large enough, including the (ε,δ>0) cases where prior one-run audits were loose.","The framework works as an add-on: given any collection of guesses from a single run, the order-statistics p-value converts them into a valid lower bound without requiring the guesses to be independent.","Sub-sampled Gaussian mechanisms, which even multiple-run audits find hard, can be audited tightly in one run with small δ.","For a fixed number of canary bits n, the audited ε grows monotonically with the number r of released guesses, suggesting that the earlier reported trade-off between releasing more guesses and confidence is not inherent.","The bound is efficiently computable: each v_k is a one-dimensional integral and the p-value comes from a convex optimization over a single parameter λ."],"supporting_citations":[{"why":"Supplies the f-DP trade-off framework, the base-distribution-pair construction, and the Gaussian and Laplace trade-off functions used throughout the reduction and experiments.","marker":"[8]"},{"why":"Describes the one-run audit framework and the high-score-only release heuristic that this paper refines; also the baseline whose δ>0 gap motivates the work.","marker":"[27]"},{"why":"Formulates privacy audit as bit transmission and shows tight results need independent guesses; serves as the comparison point that is invalid under dependent filtering.","marker":"[32]"},{"why":"Extends f-DP auditing in one run but fails to close the Gaussian-mechanism gap; the main baseline for the general dependent case.","marker":"[17]"},{"why":"Establishes the standard membership-inference-to-lower-bound pipeline with Clopper-Pearson confidence that one-run audits aim to replace.","marker":"[22]"},{"why":"Provides the density formula for k-th order statistics used to compute the tail bound in Theorem 3.","marker":"[25]"},{"why":"Gives the randomized response mechanism used in the large-δ experiment where previous one-run audits fail.","marker":"[30]"},{"why":"Provides DP-SGD, the real differentially private algorithm audited in the experiments.","marker":"[1]"},{"why":"Relates privacy loss distributions to f-DP and gives the conversion from f-DP to (ε,δ)-DP used in Algorithm 2.","marker":"[34]"}],"fun_headline_variants":["Tight privacy audit in a single run","One-run audit hits tight (ε,δ) lower bounds","Privacy audit in one run now provably tight","One run, tight (ε,δ) privacy audit","Tight one-run audit for (ε,δ)-DP"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The load-bearing step is that replacing a released guess by an independent f-DP-channel guess with the same score cannot improve the distribution of errors—equivalently, that the conditional error probability of a released original guess is never below the marginal optimum; if the score reveals which guesses are correct, this can fail and the p-value becomes too small.","fun_headline_variants_meta":{"raw":{"variants":["Tight privacy audit in a single run","One-run audit hits tight (ε,δ) lower bounds","Privacy audit in one run now provably tight","One run, tight (ε,δ) privacy audit","Tight one-run audit for (ε,δ)-DP"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000759,"raw_usage":{"total_tokens":3160,"prompt_tokens":650,"completion_tokens":2510,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":394,"completion_tokens_details":{"reasoning_tokens":2446}},"tokens_in":394,"tokens_out":2510,"duration_ms":21796,"temperature":1.0,"reasoning_tokens":2446,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T20:19:18.768562+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Implement an f-DP mechanism with a deliberately informative decoder, e.g., a Gaussian mechanism where the decoder scores each guess by the posterior P(B_i=1|y) rather than by absolute privacy loss. Fix a known f-DP upper bound, run the audit many times, and compare the empirical frequency of observing at most u errors among the r released guesses with the paper's p-value; an empirical frequency systematically above the claimed bound would refute Theorem 1.","supporting_citations":[],"review_version":1}