pith. sign in

arxiv: 2604.10819 · v1 · submitted 2026-04-12 · 💻 cs.DS · cs.CC· cs.LG

Differentially Private Verification of Distribution Properties

Elbert Du , Cynthia Dwork , Pranay Tankala , Linjun Zhang This is my paper

Pith reviewed 2026-05-10 15:03 UTC · model grok-4.3

classification 💻 cs.DS cs.CCcs.LG
keywords differentially privateinteractive proofsdistribution property testingpublic-coin protocolsMerlin-Arthur proofssample complexityprivate coins
0
0 comments X

The pith

Private-coin differentially private interactive proofs for distribution properties reduce to public-coin versions without added cost in moderate privacy regimes.

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

The paper maps out how to verify properties of distributions when samples must be protected by differential privacy and an untrusted prover assists the process. It establishes that in the regime where the privacy parameter epsilon is on the order of one over square root of n and delta is one over n to the five-halves, any one-round private-coin protocol converts to a public-coin one while keeping the same sample count and communication. This conversion uses replicability and amplification ideas. The work also constructs a one-message Merlin-Arthur protocol for testing whether samples come from a product distribution and proves that the number of samples required is optimal.

Core claim

We show a reduction from any one-round (ε,δ)-DP private-coin interactive proof to a one-round public-coin DP interactive proof with the same privacy parameters, for the parameter regime ε=O(1/√n) and δ=O(1/n^{5/2}), and with the same sample and communication complexities. If the verifier's message is O(1/√log n) locally DP then one further transformation again yields a public-coin protocol. When privacy is very relaxed with ε in Omega(log n), private coins do reduce complexity. We obtain a Merlin-Arthur proof for privately testing whether samples are drawn from a product distribution and prove that its sample complexity is optimal.

What carries the argument

The reduction that converts private-coin differentially private interactive proofs into public-coin ones while preserving privacy, sample, and communication costs in the moderate privacy regime.

If this is right

  • Public-coin differentially private protocols achieve the same sample and communication complexity as private-coin ones for distribution verification in the moderate privacy regime.
  • For very relaxed privacy guarantees where epsilon is at least logarithmic in n, private coins provide a genuine complexity advantage.
  • The optimal one-message protocol for testing product distributions gives a concrete benchmark for other distribution properties under differential privacy.
  • The same sample complexity suffices whether the verifier uses private or public randomness when the stated privacy bounds apply.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Public randomness may suffice for many practical differentially private verification tasks, simplifying implementation and analysis.
  • The optimality result for product distributions can serve as a template for deriving tight bounds on other properties such as uniformity or independence.
  • Extending the reduction beyond the moderate privacy regime or to multi-round protocols would require new techniques.

Load-bearing premise

The reduction from private-coin to public-coin protocols holds only when the privacy parameters satisfy epsilon on the order of one over square root of n and delta on the order of one over n to the five-halves.

What would settle it

An explicit distribution property together with a private-coin protocol whose sample complexity is strictly lower than that of every public-coin protocol in the stated privacy regime would disprove the reduction.

read the original abstract

A recent line of work initiated by Chiesa and Gur and further developed by Herman and Rothblum investigates the sample and communication complexity of verifying properties of distributions with the assistance of a powerful, knowledgeable, but untrusted prover. In this work, we initiate the study of differentially private (DP) distribution property testing. After all, if we do not trust the prover to help us with verification, why should we trust it with our sensitive sample? We map a landscape of DP prover-aided proofs of properties of distributions. In the non-private case it is known that one-round (two message) private-coin protocols can have substantially lower complexity than public-coin AM protocols, but in the private case, the possibility for improvement depends on the parameter regime and privacy model. Drawing on connections to replicability and techniques for amplification, we show: (1) There exists a reduction from any one-round $(\varepsilon,\delta)$-DP private-coin interactive proof to a one-round public-coin DP interactive proof with the same privacy parameters, for the parameter regime $\varepsilon=O(1/\sqrt{n})$ and $\delta=O(1/n^{5/2})$, and with the same sample and communication complexities. (2) If the verifier's message in the private-coin interactive proof is $O(1/\sqrt{\log n})$ locally DP -- a far more relaxed privacy parameter regime in a different model -- then applying one additional transformation again yields a one-round public-coin protocol with the same privacy bound and the same sample and computational complexities. (3) However, when the privacy guarantee is very relaxed ($\varepsilon\in\Omega(\log n)$), private coins indeed reduce complexity. We also obtain a Merlin-Arthur (one-message) proof for privately testing whether samples are drawn from a product distribution, and prove that its sample complexity is optimal.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper initiates the study of differentially private (DP) distribution property testing in the presence of an untrusted but powerful prover. It maps the landscape of DP prover-aided proofs, showing a reduction from any one-round (ε,δ)-DP private-coin interactive proof to a one-round public-coin DP interactive proof with matching privacy parameters, sample complexity, and communication complexity, specifically in the regime ε=O(1/√n) and δ=O(1/n^{5/2}) via replicability and amplification techniques. A second transformation applies when the verifier's message is O(1/√log n) locally DP. For relaxed privacy (ε=Ω(log n)), private coins do reduce complexity. The paper also gives a Merlin-Arthur proof for privately testing whether samples are drawn from a product distribution and proves its sample complexity is optimal.

Significance. If the reductions and optimality hold, the work provides a clear mapping of how differential privacy interacts with private-coin vs. public-coin interactive proofs for distribution properties, identifying precise regimes where private coins help or do not. The explicit scoping to parameter regimes, connections to replicability, and the tight optimality result for product-distribution testing are strengths that advance both the theory of DP verification and interactive proofs.

major comments (2)
  1. [§4] §4 (main reduction): the transformation from private-coin to public-coin protocols via replicability must be checked to ensure that the amplification step preserves exactly the same (ε,δ) bounds without introducing additive terms that would exit the O(1/√n) regime for ε; the abstract states matching complexities but the error analysis needs explicit verification against the stated δ=O(1/n^{5/2}).
  2. [§6] §6 (product-distribution MA protocol): the optimality claim requires that the upper-bound sample complexity of the Merlin-Arthur proof exactly matches the lower bound up to constant factors; confirm that the lower-bound construction does not rely on additional assumptions beyond standard DP and IP definitions.
minor comments (2)
  1. [Abstract] Abstract: the phrase 'one additional transformation' for the locally DP case should be expanded with a brief parenthetical on how local DP differs from the central (ε,δ)-DP model used elsewhere.
  2. [Introduction] Introduction: add one sentence contrasting the non-private Chiesa-Gur and Herman-Rothblum results with the DP setting to clarify where the privacy constraint changes the complexity landscape.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading, insightful comments, and recommendation for minor revision. We address each major comment below with clarifications and indicate the revisions that will be incorporated.

read point-by-point responses

  1. Referee: [§4] §4 (main reduction): the transformation from private-coin to public-coin protocols via replicability must be checked to ensure that the amplification step preserves exactly the same (ε,δ) bounds without introducing additive terms that would exit the O(1/√n) regime for ε; the abstract states matching complexities but the error analysis needs explicit verification against the stated δ=O(1/n^{5/2}).

    Authors: We appreciate the referee pointing this out. Re-examination of the proof in Section 4 confirms that the replicability-based amplification preserves the exact (ε, δ) parameters with no additive error terms that would exit the stated regime. The privacy loss is controlled multiplicatively, and the error analysis (detailed in the appendix) ensures the bounds remain ε = O(1/√n) and δ = O(1/n^{5/2}) without additive δ contributions. To address the request for explicit verification, we will insert a dedicated paragraph in the revised Section 4 that walks through the error propagation step by step. revision: yes

  2. Referee: [§6] §6 (product-distribution MA protocol): the optimality claim requires that the upper-bound sample complexity of the Merlin-Arthur proof exactly matches the lower bound up to constant factors; confirm that the lower-bound construction does not rely on additional assumptions beyond standard DP and IP definitions.

    Authors: We thank the referee for requesting this confirmation. The sample complexity of the Merlin-Arthur protocol in Section 6 matches the lower bound up to constant factors, as established by a direct information-theoretic argument. The lower-bound construction relies only on the standard definitions of differential privacy and interactive proofs (via a standard reduction from hypothesis testing); no additional assumptions are used. We will add a short clarifying remark in the revised Section 6 to make this explicit. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivations are independent transformations

full rationale

The paper's central results are explicit reductions from private-coin to public-coin DP one-round proofs (via replicability and amplification) and an MA protocol for product-distribution testing, all scoped to explicit parameter regimes and standard DP/IP definitions. No step reduces by construction to its own inputs, no fitted parameters are relabeled as predictions, and no load-bearing premise rests on self-citation chains. External citations to Chiesa-Gur and Herman-Rothblum supply independent prior context rather than self-referential justification. The optimality claim for the MA protocol is a separate lower-bound argument, not a renaming or self-definition. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Based on abstract only; no explicit free parameters, axioms, or invented entities are detailed. The work relies on standard definitions from interactive proofs and differential privacy.

pith-pipeline@v0.9.0 · 5644 in / 1102 out tokens · 34244 ms · 2026-05-10T15:03:39.043512+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

30 extracted references · 30 canonical work pages

  1. [1]

    Testing k-wise and almost k-wise independence

    Noga Alon, Alexandr Andoni, Tali Kaufman, Kevin Matulef, Ronitt Rubinfeld, and Ning Xie. Testing k-wise and almost k-wise independence. In Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing , STOC '07, page 496–505, New York, NY, USA, 2007. Association for Computing Machinery

    work page 2007

  2. [2]

    Better private distribution testing by leveraging unverified auxiliary data

    Maryam Aliakbarpour, Arnav Burudgunte, Cl\'ement Canonne, and Ronitt Rubinfeld. Better private distribution testing by leveraging unverified auxiliary data. In Nika Haghtalab and Ankur Moitra, editors, Proceedings of Thirty Eighth Conference on Learning Theory , volume 291 of Proceedings of Machine Learning Research , pages 22--63. PMLR, 30 Jun--04 Jul 2025

    work page 2025

  3. [3]

    Test without trust: Optimal locally private distribution testing

    Jayadev Acharya, Clement Canonne, Cody Freitag, and Himanshu Tyagi. Test without trust: Optimal locally private distribution testing. In Kamalika Chaudhuri and Masashi Sugiyama, editors, Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics , volume 89 of Proceedings of Machine Learning Research , pages 2067--...

    work page 2067

  4. [4]

    Differentially private identity and closeness testing of discrete distributions, 2017

    Maryam Aliakbarpour, Ilias Diakonikolas, and Ronitt Rubinfeld. Differentially private identity and closeness testing of discrete distributions, 2017. arXiv:1707.05497 [cs.LG]

    work page arXiv 2017

  5. [5]

    Differentially private identity and equivalence testing of discrete distributions

    Maryam Aliakbarpour, Ilias Diakonikolas, and Ronitt Rubinfeld. Differentially private identity and equivalence testing of discrete distributions. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning , volume 80 of Proceedings of Machine Learning Research , pages 169--178. PMLR, 10--15 Jul 2018

    work page 2018

  6. [6]

    Learning with privacy at scale, 2017

    Apple Differential Privacy Team . Learning with privacy at scale, 2017

    work page 2017

  7. [7]

    Trading group theory for randomness

    L \'a szl \'o Babai. Trading group theory for randomness. In Proceedings of the seventeenth annual ACM symposium on Theory of computing , pages 421--429, 1985

    work page 1985

  8. [8]

    Interactive proofs for distribution testing with conditional oracles, 2025

    Ari Biswas, Mark Bun, Cl \'e ment Canonne, and Satchit Sivakumar. Interactive proofs for distribution testing with conditional oracles, 2025. arXiv:2511.22122 [cs.CC]

    work page arXiv 2025

  9. [9]

    Tugkan Batu and Clément L. Canonne. Generalized uniformity testing. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages 880--889, 2017

    work page 2017

  10. [10]

    Testing that distributions are close

    Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D Smith, and Patrick White. Testing that distributions are close. In Proceedings 41st Annual Symposium on Foundations of Computer Science , pages 259--269. IEEE, 2000

    work page 2000

  11. [11]

    Stability is stable: Connections between replicability, privacy, and adaptive generalization, 2023

    Mark Bun, Marco Gaboardi, Max Hopkins, Russell Impagliazzo, Rex Lei, Toniann Pitassi, Satchit Sivakumar, and Jessica Sorrell. Stability is stable: Connections between replicability, privacy, and adaptive generalization, 2023

    work page 2023

  12. [12]

    Proofs of Proximity for Distribution Testing

    Alessandro Chiesa and Tom Gur. Proofs of Proximity for Distribution Testing . In Anna R. Karlin, editor, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018) , volume 94 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 53:1--53:14, Dagstuhl, Germany, 2018. Schloss Dagstuhl -- Leibniz-Zentrum f \"u r Informatik

    work page 2018

  13. [13]

    Generalization in adaptive data analysis and holdout reuse

    Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Roth. Generalization in adaptive data analysis and holdout reuse. In Proceedings of the 29th International Conference on Neural Information Processing Systems - Volume 2 , NIPS'15, page 2350–2358, Cambridge, MA, USA, 2015. MIT Press

    work page 2015

  14. [14]

    Our data, ourselves: Privacy via distributed noise generation

    Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Annual international conference on the theory and applications of cryptographic techniques , pages 486--503. Springer, 2006

    work page 2006

  15. [15]

    Differential privacy and robust statistics

    Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. In Proceedings of the forty-first annual ACM symposium on Theory of computing , pages 371--380, 2009

    work page 2009

  16. [16]

    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. In Theory of cryptography conference , pages 265--284. Springer, 2006

    work page 2006

  17. [17]

    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. Journal of Privacy and Confidentiality , 7(3):17–51, May 2017

    work page 2017

  18. [18]

    Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling, 2021

    Vitaly Feldman, Audra McMillan, and Kunal Talwar. Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling, 2021

    work page 2021

  19. [19]

    The knowledge complexity of interactive proof-systems

    S Goldwasser, S Micali, and C Rackoff. The knowledge complexity of interactive proof-systems. In Proceedings of the seventeenth annual ACM symposium on Theory of computing , pages 291--304, 1985

    work page 1985

  20. [20]

    The knowledge complexity of interactive proof systems

    Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof systems. SIAM Journal on Computing , 18(1):186--208, 1989

    work page 1989

  21. [21]

    On testing expansion in bounded-degree graphs

    Oded Goldreich and Dana Ron. On testing expansion in bounded-degree graphs. In Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation: In Collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevis...

    work page 2011

  22. [22]

    Private coins versus public coins in interactive proof systems

    S Goldwasser and M Sipser. Private coins versus public coins in interactive proof systems. In Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing , STOC '86, page 59–68, New York, NY, USA, 1986. Association for Computing Machinery

    work page 1986

  23. [23]

    Public coin interactive proofs for label-invariant distribution properties

    Tal Herman. Public coin interactive proofs for label-invariant distribution properties. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques , 2024

    work page 2024

  24. [24]

    Verifying the unseen: interactive proofs for label-invariant distribution properties

    Tal Herman and Guy N Rothblum. Verifying the unseen: interactive proofs for label-invariant distribution properties. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages 1208--1219, 2022

    work page 2022

  25. [25]

    Doubly-efficient interactive proofs for distribution properties

    Tal Herman and Guy Rothblum. Doubly-efficient interactive proofs for distribution properties. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages 743--751, 2023

    work page 2023

  26. [26]

    Rothblum

    Tal Herman and Guy N. Rothblum. How to verify any (reasonable) distribution property: Computationally sound argument systems for distributions. In The Thirteenth International Conference on Learning Representations, ICLR 2025, Singapore, April 24-28, 2025 . OpenReview.net, 2025

    work page 2025

  27. [27]

    Reproducibility in learning

    Russell Impagliazzo, Rex Lei, Toniann Pitassi, and Jessica Sorrell. Reproducibility in learning. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , STOC 2022, page 818–831, New York, NY, USA, 2022. Association for Computing Machinery

    work page 2022

  28. [28]

    Rogers, Aaron Roth, Adam D

    Ryan M. Rogers, Aaron Roth, Adam D. Smith, and Om Thakkar. Max-information, differential privacy, and post-selection hypothesis testing. In Irit Dinur, editor, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, Hyatt Regency, New Brunswick, New Jersey, USA, October 9-11, 2016 , pages 487--494. IEEE Computer Society, 2016

    work page 2016

  29. [29]

    Salil P. Vadhan. The complexity of differential privacy. In Yehuda Lindell, editor, Tutorials on the Foundations of Cryptography , pages 347--450. Springer International Publishing, 2017

    work page 2017

  30. [30]

    Estimating the unseen: Improved estimators for entropy and other properties

    Paul Valiant and Gregory Valiant. Estimating the unseen: Improved estimators for entropy and other properties. In C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems , volume 26. Curran Associates, Inc., 2013

    work page 2013