Differentially Private Verification of Distribution Properties

Elbert Du; Cynthia Dwork; Pranay Tankala; Linjun Zhang

cs.DSApr 12, 2026

Differentially Private Verification of Distribution Properties

Authors: Elbert Du, Cynthia Dwork, Pranay Tankala, Linjun Zhang

Organizations: Harvard University · Rutgers University

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 distribution property verification. 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 differentially private verification of properties of distributions. In the non-private case it is known that one-round private-coin protocols can have substantially lower complexity than public-coin (AM) protocols. In contrast, the possibility for improvement in differentially private interactive proofs depends on the privacy parameter regime and model. Drawing on connections between privacy and replicability and privacy amplification techniques in the literature we show: 1. There exists a reduction from any one-round $(\varepsilon,δ)$ -differentially private private-coin protocol to a differentially private AM protocol for the parameter regime $\varepsilon = O(1/\sqrt{s})$ and $δ= O(1/s^{5/2})$ with the same privacy and sample and communication complexities. In the local model, this is relaxed to $\varepsilon = O(1/\sqrt{\log s})$ 2. However, when the privacy guarantee is very relaxed ( $\varepsilon \in Ω(\log s)$ ), private coins indeed reduce sample and communication complexities. We also obtain a computationally efficient Merlin-Arthur proof for privately testing whether samples are drawn from a product distribution and prove that its sample complexity is optimal up to a $polylog N$ factor by reducing uniformity testing to independence testing with Boolean attributes and appealing to known lower bounds on sample complexity for private uniformity testing.

Figures & tables

\pi_{i}=\begin{cases}D(S_{i})&\text{if }D(S_{i})\geq p_{\mathrm{min}},\\ 0&\text{if }D(S_{i})<p_{\mathrm{min}}.\end{cases}

Algorithm 7.1 Non-Private AM Protocol for Tagged Sample Retrieval From [ 43 ]

\pi_{i}=\begin{cases}D(S_{i})&\text{if }D(S_{i})\geq p_{\mathrm{min}},\\ 0&\text{if }D(S_{i})<p_{\mathrm{min}}.\end{cases}

Algorithm 7.3 Approximate DP AM Protocol for Tagged Sample Retrieval

Differential Privacy

Differential privacy limits how much an algorithm’s outputs can reveal about any one person’s data, with formal guarantees.

See all 276 papers

Dec 3, 2025

Efficient Public Verification of Private ML via Regularization

Training with differential privacy (DP) guarantees dataset members that they cannot be identified by users of the released model. However, those data providers, and, in general, the public, lack methods to efficiently verify that models trained on their data satisfy DP guarantees. The amount of compute needed to verify DP guarantees for current algorithms scales with the amount of computation required to train the model. In this paper we design the first DP algorithm with near optimal privacy-utility trade-offs but whose DP guarantees can be verified cheaper than training. We focus on DP stochastic convex optimization (DP-SCO), where optimal privacy-utility trade-offs are known. Here we show we can obtain tight privacy-utility trade-offs by privately minimizing a series of regularized objectives and only using the standard DP composition bound. Crucially, this method can be verified with much less compute than training. This leads to the first known DP-SCO algorithm with near optimal privacy-utility whose DP verification scales better than training cost, significantly reducing verification costs on large datasets.

Zoë Ruha Bell, Anvith Thudi, Olive Franzese-McLaughlin +2

Department of Computer Science, University of California, Berkeley, USA · Department of Computer Science, University of Toronto, Toronto, Canada · Vector Institute, Toronto, Canada

Differential Privacy

Ask PDF

Sep 30, 2026

PrivCert: Certifying Statement Support under Differential Privacy

Differentially private (DP) text generation can protect individual records, but privacy alone does not specify what evidence a released statement carries about the underlying data. We identify this as an evidence gap: a private report may contain plausible claims without indicating whether they are strongly supported by the private dataset. We introduce PrivCert, a framework for privacy-preserving reporting that makes statement support explicit through privacy-preserving certificates and emit-or-abstain decisions. As a canonical instantiation, PrivCert-PF (Proposal-and-Filter) separates data-independent candidate discovery from private support certification, emitting only statements whose support passes a private evidence test. We provide theoretical grounding for this framework by characterizing the limits of implicit evidence under DP, deriving a sharp privacy--honesty frontier for single-statement certification, and establishing a worst-case cost for fine-grained multi-statement certification. Experiments on synthetic tasks and TAB, WildChat, and Yelp show that explicit certification maintains low unsupported emission, while free-text DP baselines frequently produce low-support claims under the same declared support semantics. We further show that the PrivCert contract can be realized with histogram, sparse-vector, and Gaussian mechanisms, and use DP synthetic data to illustrate an important boundary: support in a private proxy does not automatically certify support in the original data. Together, these results position privacy-preserving reporting as an evidence-design problem: not only how to generate private text, but what a private report can substantiate about its underlying data.

Tsubasa Takahashi, Takumi Hiraoka

Acompany Co., Ltd.

Differential Privacy Privacy-Utility Tradeoff

Ask PDF

Jul 17, 2026

Testing Distributions Against Bounded Distinguishers

Motivated by the challenge of testing distributions over high-dimensional or continuous domains, we study distribution testing with respect to bounded classes of distinguishers. A representative task is to use samples from an unknown distribution

P

over a very large domain to decide between two cases:

P = P_{\mathsf{ref}}

for a fixed reference distribution

P_{\mathsf{ref}}

, or there exists a distinguisher

f

in a bounded class

\mathcal{F}

which witnesses the separation

|\mathbf{E}_P[f] - \mathbf{E}_{P_{\mathsf{ref}}}[f]| > ε

. This is the task of identity testing with respect to fooling distance, a name inspired by the conceptual connection with pseudorandomness. (Formally, our model instantiates integral probability metrics from Boolean classes of bounded expressivity.) We show that testing with respect to fooling distance is not only a natural computational problem that admits sample-efficient algorithms even in high-dimensional settings, but also one that reveals and underlies connections between three seemingly unrelated areas of study: testable learning, verification of learning algorithms, and testing of structured distributions (whose "

\mathcal{A}_k

-testing" model our framework extends). These connections yield new results for all of these models, including: 1. Testable proper learners using membership queries for halfspaces and decision trees. 2. A lower bound for testable PAC verification in terms of Rademacher complexity, and a distribution-free verification protocol for disjoint unions of

k

multidimensional rectangles. 3. Identity testers (with respect to total variation distance) for decision tree distributions and distributions with low-degree polynomial densities, over Boolean and continuous hypercube domains.

Mark Bun, Rathin Desai, Renato Ferreira Pinto

Boston University · Columbia University

Integral Probability Metrics

Ask PDF

Abstract

Differential Privacy

Explore similar work

Efficient Public Verification of Private ML via Regularization

PrivCert: Certifying Statement Support under Differential Privacy

Testing Distributions Against Bounded Distinguishers