Differentially Private Verification of Distribution Properties

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.