Differentially Private Verification of Distribution Properties

arXiv:2604.10819 · cs.DS, cs.CC, cs.LG · Submitted 2026-08-14 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "Differentially Private Verification of Distribution Properties".

Jane: The paper was written by Elbert Du, Cynthia Dwork, Pranay Tankala and Linjun Zhang from Harvard University and Rutgers University.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Title: Tom: Welcome back to the show, everyone. Today we're digging into a fresh arXiv paper called "Differentially Private Verification of Distribution Properties" — and honestly, the title alone got me excited. Jane, you've been reading this one too, right?

Jane: Oh, absolutely, Tom. And I think the title packs a lot in. We've got "differentially private" — that's the privacy guarantee — and "verification of distribution properties," which is about checking whether some data really comes from a distribution with certain features. Like, is this dataset actually uniform? Does it have the right amount of entropy? That sort of thing.

Tom: Right, and the twist here is that you're not doing this alone. You've got a prover — this powerful, knowledgeable helper who claims to know everything about the distribution. But here's the catch: you don't trust them. So you want to verify their claims using only a small sample of data.

Jane: And the authors — Elbert Du, Cynthia Dwork, Pranay Tankala, and Linjun Zhang — they're asking a really natural question. If you don't trust the prover to be honest, why would you trust them with your sensitive data? So they're adding privacy on top of this whole verification game.

Tom: That's such a good point. I mean, the whole setup is already about distrust — the prover might be lying to you. But then there's this second layer: even if the prover is honest, your sample itself contains sensitive information about real people. So the verifier's own messages and decisions could leak that information.

Jane: Exactly. And that's what makes this paper interesting. It's not just about verifying properties anymore. It's about doing that verification while making sure the verifier's own behavior doesn't spill secrets. The authors map out a whole landscape of what's possible and what's not in this private, prover-aided setting.

Tom: And they get some pretty surprising results. I mean, there's this whole question about whether private coins — secret randomness the verifier uses — actually help you. In the non-private world, they do. But once you add privacy, the answer gets complicated.

Jane: Yeah, and we'll get into that. But first, let's just appreciate the setup. You've got a sample, you've got a prover who claims to know the distribution, and you want to check whether the distribution has some property — all while keeping the sample private. That's the core problem.

Tom: And the paper's got results across multiple fronts — private coin protocols, public coin protocols, independence testing, even arguments of proximity. It's a big landscape.

Jane: So stick around, because next we're going to talk about what they actually found. And trust me, there's a result in here about private coins versus public coins that really surprised me.

Tom: You're not kidding. Let's get into it.

Summary: Jane: So, Tom, we're back with "Differentially Private Verification of Distribution Properties," and I want to talk about the main results. The paper's got this really clean way of framing things. There are two kinds of interactive proofs: private-coin, where the verifier has secret randomness, and public-coin, where all the randomness is shared with the prover.

Tom: And in the non-private world, private coins give you a huge advantage. I mean, the paper mentions that you can verify properties like support size or entropy with only square-root-of-N samples using private coins, while public coins need way more.

Jane: Right, but here's the kicker. The authors show that if your privacy guarantee is strong enough — specifically, if epsilon is on the order of one over the square root of the sample size, and delta is tiny — then private coins buy you nothing. You can convert any private-coin protocol into a public-coin one with the same sample and communication complexity.

Tom: That's wild. So privacy actually erases the advantage of private coins?

Jane: In that regime, yes. And the intuition is beautiful. They use this connection between differential privacy and something called replicability. If an algorithm is private enough, then running it on two different samples from the same distribution gives you the same output with high probability. So the verifier's message doesn't really depend on the specific sample — it's almost deterministic.

Tom: So if the message is basically determined by the distribution, the prover could just compute it themselves. The verifier doesn't need to send anything secret.

Jane: Exactly. The prover draws their own sample, computes what the verifier would have said, and sends that along with their response. The verifier just checks that the guess matches. And because of replicability, it matches almost all the time.

Tom: But wait — that only works for really strong privacy. What if the privacy guarantee is weaker?

Jane: That's where it gets interesting. If you relax epsilon to be logarithmic in the sample size, private coins do help again. The paper cites a protocol that achieves square-root-of-N sample complexity for label-invariant properties, while the best public-coin protocols are stuck at N to the two-thirds.

Tom: So there's a threshold effect. Strong privacy kills the private-coin advantage, but weak privacy lets it come back.

Jane: And there's also a middle ground. If the verifier's message is locally differentially private — meaning each data point is randomized before being sent — then they can use privacy amplification by shuffling to get the same reduction to public coins, even with a much more relaxed privacy parameter.

Tom: That's the Feldman-McMillan-Talwar result they're using, right?

Jane: Yeah. Shuffling the messages before they reach the prover amplifies the privacy guarantee, so you get the same effect as the strong-privacy regime.

Tom: Okay, so that's the private-coin story. But the paper also has results for independence testing and for arguments of proximity. What's the deal there?

Jane: For independence testing — checking whether a distribution is a product distribution — they get a matching upper and lower bound. The upper bound is a simple protocol where the prover sends the marginals, and the verifier tests identity against the induced product distribution. The lower bound comes from reducing uniformity testing to independence testing.

Tom: And the sample complexity is roughly square-root of N over sigma squared, right?

Jane: Yeah, up to log factors. And that's actually better than what you can do without a prover in the non-private case. So having a prover genuinely helps here.

Tom: Alright, so we've got private coins, public coins, independence testing. What about the arguments of proximity? That's the computational soundness stuff.

Jane: That's next. But let me just say — the fact that they can take the non-private argument system from Herman and Rothblum and make it differentially private with almost no extra cost when epsilon is large enough? That's a really practical result.

Tom: Practical is the word. Let's bring in Lu and Meng for that part.

Improvements: Lu: So we're continuing with "Differentially Private Verification of Distribution Properties," and I want to talk about the improvements the paper makes over the generic approach. There's this standard trick for making any distribution tester private — you just run it on a random subsample of your data, and that gives you epsilon-differential privacy with a one-over-epsilon blowup in sample complexity.

Meng: Right, that's the classic reduction. But the paper shows you can do much better for label-invariant properties — properties that don't care about the labels of the domain elements, just their probabilities. They use this Propose-Test-Release framework to avoid paying that full one-over-epsilon cost.

Jane: And the improvement is significant. Instead of N to the two-thirds over epsilon samples, they get N to the two-thirds over epsilon to the two-thirds. That's a real saving when epsilon is small.

Lu: The intuition is that the non-private protocol already has to tolerate some noise because of sampling randomness. So you can add a bit of privacy noise on top without breaking the guarantees — as long as you're careful about which statistics you're adding noise to.

Meng: But there's a catch, right? The non-private protocol assumes the distribution has a certain minimum entropy — no element is too heavy. In the private setting, you can't just filter out heavy elements without leaking information. So they have to handle elements with weight up to log-of-one-over-delta over epsilon-s times the sample size.

Lu: Exactly. And that changes the analysis significantly. The protocol has to be robust to heavier elements, which means the collision counts — the statistics they're checking — have different variance properties. They had to redo the whole concentration analysis with this weaker assumption.

Jane: And that's where the Propose-Test-Release comes in. One of the statistics they check is the number of three-way collisions, which has sensitivity that depends on the data itself. So they propose a bound on that sensitivity, test it privately, and only then add noise calibrated to that bound.

Meng: That's the clever part. The sensitivity of the three-way collision count could be as large as s-squared if the data is pathological. But typically it's much smaller. So instead of adding noise for the worst case, they test whether the actual sensitivity is small, and only proceed if it is.

Lu: And the completeness and soundness guarantees still hold. If the prover is honest, the verifier accepts with high probability and gets tagged samples — pairs of elements and their approximate probabilities. If the prover is dishonest, the verifier either rejects or gets tagged samples that are still accurate enough to verify any label-invariant property.

Tom: So this is a black-box reduction? Once you have the tagged samples, you can verify any label-invariant property?

Lu: Yes, that's the beauty of it. The tagged samples give you an approximate histogram of the distribution, and any label-invariant property can be checked from that histogram. So this one protocol unlocks private verification for a whole class of properties.

Meng: And then there's the argument of proximity result, which is even more practical. They take the computationally sound protocol from Herman and Rothblum and swap in a private identity tester. The only step that touches the sensitive data is the identity test, so that's the only place privacy matters.

Jane: And the sample complexity there is square-root of N over sigma-squared, plus square-root of N over sigma times square-root of epsilon. When epsilon is large enough — on the order of sigma-squared — the privacy cost vanishes entirely.

Meng: That's the kind of result that could actually get deployed. If you're already using a cryptographic argument system, adding privacy is nearly free in the right parameter regime.

Lu: And that's the theme of the paper, really. Privacy doesn't have to be expensive if you're clever about where you add the noise.

Tom: So what's the big picture here? Where does this leave the field?

Conclusion: Jane: We're wrapping up our discussion of "Differentially Private Verification of Distribution Properties," and I think the big takeaway is that privacy and prover-aided verification can coexist without destroying the benefits of having a prover.

Tom: Yeah, the paper really maps out the landscape. Strong privacy kills the private-coin advantage, weak privacy lets it come back, and there's this whole middle ground with local differential privacy and shuffling.

Lu: And the independence testing result is clean — matching upper and lower bounds, with a simple protocol that beats the no-prover lower bound. That's a nice contribution.

Meng: The practical stuff matters too. The argument of proximity result shows that if you're already using cryptographic assumptions, you can get privacy almost for free in the right regime. That's the kind of thing that could actually be built.

Jane: And the Propose-Test-Release protocol for label-invariant properties — that's a genuine improvement over the generic reduction. It's not just a theoretical curiosity; it's a technique that could be reused.

Tom: So what's next? The paper lists some open questions. The big one is whether public-coin protocols can match the private-coin lower bound of square-root of N for label-invariant properties.

Lu: That's the gap. We know private coins can do square-root of N, and public coins are stuck at N to the two-thirds. Closing that gap would be a major result.

Meng: And there's also the question about whether there's a meaningful notion of public-coin protocols where the verifier can send sample-dependent messages as long as the randomness is shared. That would be a different model entirely.

Jane: I also liked the question about weaker adversary models. If you assume the adversary doesn't know your specific sample — just the distribution — then maybe you can get away with less privacy machinery.

Tom: That's a really interesting direction. The paper's already thinking about what comes next.

Jane: It does. And honestly, this paper feels like it opens more questions than it answers, which is a good sign for a research area.

Tom: Absolutely. So let's say goodbye to "Differentially Private Verification of Distribution Properties" — a paper that asks whether we can verify properties of distributions without leaking the sample, and gives us a rich set of answers.

Jane: And we'll be back with the next paper soon. Until then, keep questioning your provers — and keep your data private.

Tom: See you next time.

Elbert Du, Cynthia Dwork, Pranay Tankala, Linjun Zhang

Harvard University · Rutgers University

cs.DS, cs.CC, cs.LG

Submitted: 2026-08-14

Updated: 2026-08-18

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 82/100

Key concepts

Private Coins: Interactive proofs where the verifier uses secret randomness. In non-private settings, this offers a significant advantage for verifying properties like support size or entropy using only square-root-of-N samples compared to public coins.
Differential Privacy (Privacy Guarantee): A guarantee ensuring that the verifier's messages do not leak sensitive information about real people. The paper explores how strong privacy guarantees can eliminate the advantage of private coins, while weaker guarantees allow private coins to still provide benefits.
Propose-Test-Release Framework: A technique used to improve verification for label-invariant properties. Instead of a generic noise reduction, this framework allows the verifier to test the sensitivity of statistics like three-way collisions before adding privacy noise calibrated specifically to that sensitivity.

Terminology

Verifier — 162× in this paper · explained in 2 episodes
Sample Complexity — 50× in this paper · explained in 15 episodes
Differentially Private — 46× in this paper · explained in 3 episodes
Verification — 23× in this paper · explained in 2 episodes
Differential Privacy — 21× in this paper · explained in 4 episodes
Annual Symposium on Foundations of Computer Science — 4× in this paper
Generalization — 4× in this paper · explained in 13 episodes
Adam — 3× in this paper · explained in 2 episodes
Approximate Max-Information — 2× in this paper · explained in 1 episode
Combinatorial Optimization — 1× in this paper · explained in 2 episodes
Core — 1× in this paper · explained in 2 episodes
Post-Selection — 1× in this paper · explained in 2 episodes

Summary

Summary

This paper initiates the study of differentially private (DP) distribution property testing in the presence of an untrusted prover. The authors note that if a prover cannot be trusted to be honest in its claims about a distribution, then it should also not be trusted with sensitive information in the dataset. The paper maps a landscape of differentially private prover-aided proofs of properties of distributions, focusing on the sample and communication complexity of such protocols.

Main Results:

Lower Bound for Private Coin DP Interactive Proofs (Theorem 3.1 / Corollary 4.5): For sufficiently small privacy parameters, private coins provide no advantage over public coins. Specifically, given a one-round (ε, δ)-DP interactive proof verifying a property P with sample complexity n and communication complexity c, where ε = O(1/√n) and δ = O(1/n(5/2)), there exists a one-round (ε, δ)-DP public coin interactive proof verifying P with the same sample and communication complexities. The proof relies on converting differential privacy to replicability via transfer theorems from [BGH+ 23], which allows the verifier's message to be replaced with a random seed, since replicable algorithms produce the same output with high probability on different samples from the same distribution.
Local DP Result (Corollary 4.8): If the verifier's message in a private-coin interactive proof is O(1/√log n) locally differentially private, then applying privacy amplification via shuffling from [FMT21] yields a one-round public-coin protocol with the same privacy bound and the same sample and computational complexities. This is a far more relaxed privacy parameter regime than the first reduction, but in the more constrained local DP model. The authors note this bound is tight up to log factors: for ε = Θ(log n), the protocol from [HR23] satisfies ε-local DP in the communication phase and achieves Õ(√N) sample and communication complexity for label-invariant properties, while the best known public coin bound is Õ(N(2/3)).
Independence Testing (Theorem 5.1 and Theorem 5.3): The authors derive matching upper and lower bounds for one-message (MA) protocols for testing whether a distribution is a product distribution. The upper bound is achieved by a non-interactive proof where the prover sends the marginal distribution, and the verifier runs a DP identity tester against the induced product distribution. The protocol has sample complexity O(√N/(σ√ε) + √N/σ2), verifier runtime O(√N log N/(σ√ε) + √N log N/σ2), and communication complexity O(Σi Ai). The lower bound is proved by reducing uniformity testing to independence testing with Boolean attributes, yielding s ≥ Ω̃(√N/σ2). This shows the upper bound is tight up to log factors. The authors note this MA protocol achieves lower sample complexity than the lower bound in [AAK+ 07] for non-private standard (no-prover) algorithms, showing that having a prover helps.
Generic Reduction for ε-DP AM Protocols (Theorem 6.2): Any non-private AM distribution tester with sample complexity s and communication complexity c can be converted to an ε-DP AM tester with sample complexity (6/ε)s and the same communication complexity, with error probability at most 1/3. This extends the generic reduction from [ADR18, ADR17] to the public-coin interactive proof setting, since in AM protocols the verifier's messages are random strings independent of the sample, so the only privacy threat is in the decision.
Improved Bounds for Label-Invariant Properties with Propose-Test-Release (Theorem 7.3): The authors modify the AM protocol of [Her24] for verifying label-invariant properties to achieve privacy with a smaller cost than the generic reduction. Using the Propose-Test-Release framework of Dwork and Lei [DL09], they achieve sample complexity Õ(N(2/3)/ε(2/3))·poly(log(1/δ)/σ), which is smaller than the O(N(2/3)/ε) cost of the generic reduction. The protocol (Algorithm 3) adds Laplace noise scaled to the sensitivity of each check, uses propose-test-release to bound the sensitivity of the three-way collision check, and handles elements with weight up to log(1/δ)/εs (as opposed to 1/s in the non-private protocol). The completeness and soundness guarantees are stated in terms of tagged samples (Si, πi) satisfying certain inequalities involving the ratio of reported weights to true probabilities.
Differentially Private Arguments of Proximity (Theorem 8.2): The authors adapt the interactive argument system from [HR25] to achieve ε-DP with asymptotically identical bounds as the non-private protocol for ε ≥ σ2. The only step in the original protocol that accesses the data is testing identity against the prover's committed distribution Q, so replacing the non-private identity tester with the private identity tester from [ADR18] yields an ε-DP protocol. The sample complexity is Õ(√N/(σ√ε) + √N/σ2), and the communication complexity is Õ(√N/(σ√ε) + √N/σ2 + S). For label-invariant properties and efficiently decidable properties, the tagged samples obtained can be used in post-processing via the corresponding results from [HR25].

Key Technical Ideas:

The reduction from private-coin to public-coin DP protocols uses the connection between differential privacy and replicability: replicable algorithms produce the same output with high probability on different samples from the same distribution, so the prover can generate the verifier's message itself.
The independence testing upper bound leverages the fact that a product distribution is uniquely determined by its marginals, so the prover sending marginals reduces the problem to identity testing.
The lower bound for independence testing uses a reduction from uniformity testing, mapping the uniform distribution onto 0,1 n and using Pinsker's inequality to relate total variation distance to KL divergence, showing the closest product distribution to a distribution with approximately uniform marginals is close to the product distribution with the same marginals.
The Propose-Test-Release framework is used to handle the data-dependent sensitivity of the three-way collision count in the label-invariant property verification protocol, proposing a bound on the local sensitivity and testing it privately before proceeding.
For arguments of proximity, the only privacy-sensitive step is identity testing, which can be replaced with a private identity tester without affecting the rest of the protocol's guarantees.

Improvements for AI systems

Based on the paper, here are specific improvements that can be made to AI systems, particularly in the areas of privacy-preserving machine learning, data validation, and trustworthy AI.

Improvement: Implement a differentially private (DP) verification protocol that allows an AI system to prove to an external, untrusted auditor that its training data distribution satisfies certain properties (e.g., is not biased, is uniform, or is a product distribution) without revealing the raw data.

Specific Implementation:

Use the Propose-Test-Release framework (Section 7) to create a verifier that can check if a model's training data is typical (e.g., has low sensitivity) before adding noise.
For label-invariant properties (like fairness metrics or class balance), use the improved AM protocol (Algorithm 3) which requires only O(N(2/3) / ε(2/3)) samples instead of the generic O(N(2/3) / ε) blowup.
The system can output tagged samples (data points with their true probability weights) that are DP and can be used for post-hoc verification of any symmetric property.

Capability: An AI system can now provide a certificate of fairness or data quality to a regulator, where the certificate is (ε, δ)-DP, meaning the regulator learns nothing about individual data points, only aggregate properties. The sample complexity is sublinear in the domain size.

Improvement: Integrate the MA (Merlin-Arthur) proof system for independence testing (Section 5) into AI pipelines that need to verify whether features are independent (e.g., for causal inference or feature selection) while protecting the privacy of the underlying dataset.

Improvement: Use the reduction from DP to replicability (Section 4) to make AI systems more reproducible and stable, which is a key requirement for scientific and regulatory settings.

Improvement: Implement the computationally sound argument system (Section 8) for scenarios where the auditor is computationally bounded (e.g., a third-party API service) and cannot be trusted with the full dataset.

Improvement: Replace the generic DP reduction (which multiplies sample complexity by 1/ε) with the improved Propose-Test-Release based approach for label-invariant properties.

Improvement: For one-round interactive protocols with small privacy parameters, convert private-coin protocols to public-coin (AM) protocols without increasing sample or communication complexity.