Pith. sign in

REVIEW 2 major objections 4 minor 34 references

Tight Privacy Audit in One Run

T0 review · 2 major / 4 minor · reviewed 2026-08-04 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2509.08704 v1 pith:5A4JHR7Z submitted 2025-09-10 cs.CR

Zihang Xiang , Tianhao Wang , Hanshen Xiao , Yuan Tian , Di Wang This is my paper
classification cs.CR
keywords privacyauditone-rundifferentialf-DPorderstatisticshypothesistestingmembershipinferencelowerbound
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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

What would settle it

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.

Watch

Extended reading notes

Core claim

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

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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 λ.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

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.

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 (2)
  1. [Appendix B.2, Eq. (31)]
  2. [Theorems 3 and Proposition 1 (Appendices B.4–B.5)]
minor comments (4)
  1. [Section 5.3, Eq. (20)]
  2. [Proof sketch of Theorem 1]
  3. [Definition 11 / Theorem 2]
  4. [Section 6.4, Figure 12]

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the audit p-value is computed from the f-DP null and checked against independent privacy upper bounds.

full rationale

The derivation chain is self-contained with respect to the null hypothesis. The paper posits that M is f-DP and computes, via Theorem 3 and Proposition 1, an upper bound on the probability that the released r guesses contain at most u errors under that null. The bounds are functions of the trade-off function f and the order statistics of the f-DP channel's scores; no parameter is fitted to the observed guesses, and the claimed privacy lower bound is not used as an input. The central reduction (Theorem 1) asserts a stochastic domination by independent f-DP channels with the optimal decoder. This is a substantive mathematical claim and, even if the proof is flawed, it is not circular: it does not define the target answer into existence, nor does it rely on a self-citation for the load-bearing step. The base distribution pair construction and f-DP trade-off results are cited to external prior work (Dong et al.), and the order-statistics formula is a textbook result. The self-citation to the authors' prior work [32] is only for notation and framework refinement, and is not load-bearing for the claimed tightness. The main risk noted by reviewers is a potential soundness gap in the dominance argument, which belongs to correctness rather than circularity.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No fitted parameters; the method uses user-chosen n, r, δ, and confidence level. The base distribution pair is a construction from Dong et al. and order statistics are standard. The tie-breaking rule is an ad hoc choice but the paper proves validity is independent of it.

assumptions (4)
  • domain assumption f-DP trade-off functions are convex, continuous, non-increasing, and closed under post-processing; every f-DP mechanism can be reduced to the base distribution pair P,Q (Dong et al. 2021).
    Used in Definition 9 and the reduction in Theorem 1; standard in the f-DP literature.
  • standard math Neyman-Pearson lemma: optimal binary tests are likelihood ratio tests.
    Used to identify the optimal decoder in Lemma 2 and to define privacy loss.
  • standard math Order statistic density formula (Theorem 2) for i.i.d. continuous samples.
    Used to compute v_k in Theorem 3.
  • ad hoc to paper Tie-breaking rule in Equation (20) ranks equal-score outputs by y itself.
    Chosen to make order statistics analytically tractable; the paper argues validity holds for any tie-break.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Tight Privacy Audit in One Run." pith.science (2026). https://pith.science/paper/5A4JHR7Z

@misc{pith2026250908704,
  author       = {Pith},
  title        = {Pith review of: Tight Privacy Audit in One Run},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5A4JHR7Z}},
  note         = {Machine review of arXiv:2509.08704}
}
abstract

In this paper, we study the problem of privacy audit in one run and show that our method achieves tight audit results for various differentially private protocols. This includes obtaining tight results for auditing $(\varepsilon,\delta)$-DP algorithms where all previous work fails to achieve in any parameter setups. We first formulate a framework for privacy audit \textit{in one run} with refinement compared with previous work. Then, based on modeling privacy by the $f$-DP formulation, we study the implications of our framework to obtain a theoretically justified lower bound for privacy audit. In the experiment, we compare with previous work and show that our audit method outperforms the rest in auditing various differentially private algorithms. We also provide experiments that give contrasting conclusions to previous work on the parameter settings for privacy audits in one run.

Figures

Figures reproduced from arXiv: 2509.08704 by the authors.

Figure 1
Figure 1. Our audit framework. Dataset Xin is formed based on the input bits {bi : i ∈ [n]}. The targeted privacy algorithm M is only run for a single time. The output of M is fed to a decoder D where a score and a guessed bit pair are formed for each input bit. Finally, only r guessed bits are released based on their associated scores. Definition 6 (General Audit Framework). The general pri￾vacy audit framework is a tuple (n… view at source ↗
Figure 2
Figure 2. The base distribution pairs P, Q for different trade￾off functions f. Post-processing only makes the distinguishing game harder. What cannot be achieved in distinguishing P from Q, also cannot be achieved in distinguishing M(X) from M(X′ ). This high-level idea serves as the principle for determining the confidence in our concluded lower bound. We further introduce the following definition that serves as our basic m… view at source ↗
Figure 3
Figure 3. Audit result comparison on Gaussian mechanism in the “special case”. As guesses are independent, Xiang et al.’s [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figures from the paper (10 more)
Figure 4
Figure 4. Figure 4: Audit result comparison on Laplace mechanism in the “special case”. As guesses are independent, Xiang et al.’s [PITH_FULL_IMAGE:figures/full_fig_p010_4.png]
Figure 5
Figure 5. Figure 5: Audit result comparison on Gaussian mechanism in the “general case”. Since only a subset of guesses are released, [PITH_FULL_IMAGE:figures/full_fig_p010_5.png]
Figure 6
Figure 6. Figure 6: Audit result comparison on DP-SGD. We compare [PITH_FULL_IMAGE:figures/full_fig_p011_6.png]
Figure 7
Figure 7. Figure 7: Audit result comparison on the randomized re [PITH_FULL_IMAGE:figures/full_fig_p011_7.png]
Figure 8
Figure 8. Figure 8: The base distribution pairs P, Q for the sub￾sampled Gaussian mechanism 1/σ-GDP, q = 0.5. bits, independencies are introduced because of the filtering action: whether some bits are released or not depends on the others. If some input bits in the bit vector b suffer fro…
Figure 9
Figure 9. Figure 9: Audit the sub-sampled Gaussian mechanism. We compare our method with Steinke et al.’s [27]. We set the same [PITH_FULL_IMAGE:figures/full_fig_p012_9.png]
Figure 10
Figure 10. Figure 10: P-value comparison between our method and Steinke et al.’s [27] method. We audit the randomized response [PITH_FULL_IMAGE:figures/full_fig_p012_10.png]
Figure 11
Figure 11. Figure 11: Audit result for Gaussian mechanism with fixed [PITH_FULL_IMAGE:figures/full_fig_p012_11.png]
Figure 12
Figure 12. Figure 12: Audit result for Gaussian mechanism satisfying [PITH_FULL_IMAGE:figures/full_fig_p013_12.png]
Figure 13
Figure 13. Figure 13: Pictorial description of the framework (n,M1, H1, D1, r) where the guessed bit a1 is overwritten by the guessed bit a f 1 of the f-DP channel (1,Mf , Hf , D opt f , 1). Note that for the independent f-DP channel, Mf has the same privacy guarantee as M, i.e., f-DP. to …

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

34 extracted references · 7 linked inside Pith

  1. [1]

    Deep learning with differential privacy

    Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. InProceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308–318, 2016

    2016

  2. [2]

    Deciding differential privacy for programs with finite inputs and outputs

    Gilles Barthe, Rohit Chadha, Vishal Jagannath, A Prasad Sistla, and Mahesh Viswanathan. Deciding differential privacy for programs with finite inputs and outputs. InProceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science, pages 141– 154, 2020

    2020

  3. [3]

    Dp-finder: Finding differential privacy violations by sampling and optimization

    Benjamin Bichsel, Timon Gehr, Dana Drachsler-Cohen, Petar Tsankov, and Martin Vechev. Dp-finder: Finding differential privacy violations by sampling and optimization. InProceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pages 508–524, 2018

    2018

  4. [4]

    Dp-sniper: Black-box discovery of differential privacy vi- olations using classifiers

    Benjamin Bichsel, Samuel Steffen, Ilija Bogunovic, and Martin Vechev. Dp-sniper: Black-box discovery of differential privacy vi- olations using classifiers. In2021 IEEE Symposium on Security and Privacy (SP), pages 391–409. IEEE, 2021

    2021

  5. [5]

    Tighter privacy auditing of dp-sgd in the hidden state threat model.arXiv preprint arXiv:2405.14457, 2024

    Tudor Cebere, Aur ´elien Bellet, and Nicolas Papernot. Tighter privacy auditing of dp-sgd in the hidden state threat model.arXiv preprint arXiv:2405.14457, 2024

    arXiv 2024

  6. [6]

    On the privacy prop- erties of variants on the sparse vector technique.arXiv preprint arXiv:1508.07306, 2015

    Yan Chen and Ashwin Machanavajjhala. On the privacy prop- erties of variants on the sparse vector technique.arXiv preprint arXiv:1508.07306, 2015

    arXiv 2015

  7. [7]

    The use of confidence or fiducial limits illustrated in the case of the binomial.Biometrika, 26(4):404–413, 1934

    Charles J Clopper and Egon S Pearson. The use of confidence or fiducial limits illustrated in the case of the binomial.Biometrika, 26(4):404–413, 1934

    1934

  8. [8]

    Gaussian differential privacy.Journal of the Royal Statistical Society, 2021

    Jinshuo Dong, Aaron Roth, and Weijie Su. Gaussian differential privacy.Journal of the Royal Statistical Society, 2021

    2021

Show all 34 references
  1. [9]

    Calibrating noise to sensitivity in private data analysis

    Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. InTheory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pages 265–284. Springer, 2006

    2006

  2. [10]

    On the complexity of differentially private data release: efficient algorithms and hardness results

    Cynthia Dwork, Moni Naor, Omer Reingold, Guy N Rothblum, and Salil Vadhan. On the complexity of differentially private data release: efficient algorithms and hardness results. InProceedings of the forty- first annual ACM symposium on Theory of computing, pages 381–390, 2009

    2009

  3. [11]

    The algorithmic foundations of differential privacy.Foundations and Trends® in Theoretical Computer Science, 9(3–4):211–407, 2014

    Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy.Foundations and Trends® in Theoretical Computer Science, 9(3–4):211–407, 2014

    2014

  4. [12]

    PhD thesis, State University of New York at Buffalo, 2020

    Gian Pietro Farina.Coupled relational symbolic execution. PhD thesis, State University of New York at Buffalo, 2020

    2020

  5. [13]

    Auditing dif- ferentially private machine learning: How private is private sgd?Ad- vances in Neural Information Processing Systems, 33:22205–22216, 2020

    Matthew Jagielski, Jonathan Ullman, and Alina Oprea. Auditing dif- ferentially private machine learning: How private is private sgd?Ad- vances in Neural Information Processing Systems, 33:22205–22216, 2020

    2020

  6. [14]

    https://github.com/google/ jax/pull/3646

    PRNG key reuse in differential privacy. https://github.com/google/ jax/pull/3646

  7. [15]

    A gen- eral framework for auditing differentially private machine learning

    Fred Lu, Joseph Munoz, Maya Fuchs, Tyler LeBlond, Elliott Zaresky- Williams, Edward Raff, Francis Ferraro, and Brian Testa. A gen- eral framework for auditing differentially private machine learning. Advances in Neural Information Processing Systems, 35:4165–4176, 2022

    2022

  8. [16]

    Canife: Crafting canaries for empirical privacy measurement in federated learning.arXiv preprint arXiv:2210.02912, 2022

    Samuel Maddock, Alexandre Sablayrolles, and Pierre Stock. Canife: Crafting canaries for empirical privacy measurement in federated learning.arXiv preprint arXiv:2210.02912, 2022

    2022 arXiv

  9. [17]

    Auditing f-differential privacy in one run.arXiv preprint arXiv:2410.22235, 2024

    Saeed Mahloujifar, Luca Melis, and Kamalika Chaudhuri. Auditing f-differential privacy in one run.arXiv preprint arXiv:2410.22235, 2024

    2024 arXiv

  10. [18]

    Antipodes of label differential privacy: Pate and alibi

    Mani Malek Esmaeili, Ilya Mironov, Karthik Prasad, Igor Shilov, and Florian Tramer. Antipodes of label differential privacy: Pate and alibi. Advances in Neural Information Processing Systems, 34:6934–6945, 2021

    2021

  11. [19]

    On significance of the least significant bits for dif- ferential privacy

    Ilya Mironov. On significance of the least significant bits for dif- ferential privacy. InProceedings of the 2012 ACM conference on Computer and communications security, pages 650–661, 2012

    2012

  12. [20]

    R ´enyi differential privacy of the sampled gaussian mechanism.CoRR, abs/1908.10530, 2019

    Ilya Mironov, Kunal Talwar, and Li Zhang. R ´enyi differential privacy of the sampled gaussian mechanism.CoRR, abs/1908.10530, 2019

    1908 arXiv

  13. [21]

    Tight auditing of differentially private machine learning

    Milad Nasr, Jamie Hayes, Thomas Steinke, Borja Balle, Florian Tram`er, Matthew Jagielski, Nicholas Carlini, and Andreas Terzis. Tight auditing of differentially private machine learning. In Joseph A. Calandrino and Carmela Troncoso, editors,32nd USENIX Security Symposium, USEN...

    2023

  14. [22]

    Adversary instantiation: Lower bounds for differentially private machine learning

    Milad Nasr, Shuang Songi, Abhradeep Thakurta, Nicolas Papernot, and Nicholas Carlin. Adversary instantiation: Lower bounds for differentially private machine learning. In2021 IEEE Symposium on security and privacy (SP), pages 866–882. IEEE, 2021

    2021

  15. [23]

    Jerzy Neyman and Egon Sharpe Pearson. Ix. on the problem of the most efficient tests of statistical hypotheses.Philosophical Transac- tions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character, 231(694-706):289–337, 1933

    1933

  16. [24]

    https://www.flowhunt.io/glossary/cost-of-llm/?utm source=chatgpt.com

    Cost of LLM. https://www.flowhunt.io/glossary/cost-of-llm/?utm source=chatgpt.com

  17. [25]

    Springer, 2007

    Moshe Shaked and J George Shanthikumar.Stochastic orders. Springer, 2007

    2007

  18. [26]

    Membership inference attacks against machine learning models

    Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In 2017 IEEE symposium on security and privacy (SP), pages 3–18. IEEE, 2017

    2017

  19. [27]

    Privacy auditing with one (1) training run.Advances in Neural Information Processing Systems, 36:49268–49280, 2023

    Thomas Steinke, Milad Nasr, and Matthew Jagielski. Privacy auditing with one (1) training run.Advances in Neural Information Processing Systems, 36:49268–49280, 2023

    2023

  20. [28]

    Debugging differen- tial privacy: A case study for privacy auditing.arXiv preprint arXiv:2202.12219, 2022

    Florian Tramer, Andreas Terzis, Thomas Steinke, Shuang Song, Matthew Jagielski, and Nicholas Carlini. Debugging differen- tial privacy: A case study for privacy auditing.arXiv preprint arXiv:2202.12219, 2022

    2022 arXiv

  21. [29]

    Checkdp: An automated and integrated approach for proving differential privacy or finding precise counterexamples

    Yuxin Wang, Zeyu Ding, Daniel Kifer, and Danfeng Zhang. Checkdp: An automated and integrated approach for proving differential privacy or finding precise counterexamples. InProceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pages 919–938, 2020

    2020

  22. [30]

    Randomized response: A survey technique for eliminating evasive answer bias.Journal of the American Statistical Association, 60(309):63–69, 1965

    Stanley L Warner. Randomized response: A survey technique for eliminating evasive answer bias.Journal of the American Statistical Association, 60(309):63–69, 1965

    1965

  23. [31]

    A statistical framework for differential privacy.Journal of the American Statistical Association, 105(489):375–389, 2010

    Larry Wasserman and Shuheng Zhou. A statistical framework for differential privacy.Journal of the American Statistical Association, 105(489):375–389, 2010

    2010

  24. [32]

    Privacy audit as bits transmission:(im) possibilities for audit by one run.arXiv preprint arXiv:2501.17750, 2025

    Zihang Xiang, Tianhao Wang, and Di Wang. Privacy audit as bits transmission:(im) possibilities for audit by one run.arXiv preprint arXiv:2501.17750, 2025. 14

    2025 arXiv

  25. [33]

    Bayesian estimation of differential privacy

    Santiago Zanella-B ´eguelin, Lukas Wutschitz, Shruti Tople, Ahmed Salem, Victor R¨uhle, Andrew Paverd, Mohammad Naseri, Boris K¨opf, and Daniel Jones. Bayesian estimation of differential privacy. In International Conference on Machine Learning, pages 40624–40636. PMLR, 2023

    2023

  26. [34]

    white- box

    Yuqing Zhu, Jinshuo Dong, and Yu-Xiang Wang. Optimal accounting of differential privacy via characteristic function. InInternational Conference on Artificial Intelligence and Statistics, pages 4782–4817. PMLR, 2022. Appendix A. Experimental Details of DP-SGD We follow [27]. We...

    2022

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.