Researchers Prove Private Coins Lose Their Edge Under Strict Differential Privacy
A new theory paper asks what happens when a verifier wants to check claims about a distribution using a helpful, untrusted prover, while keeping the sample private.
ProTakeaways
- New arXiv paper initiates differentially private prover-aided distribution property testing.
- Motivating question: if the prover is untrusted, why trust it with sensitive samples?
- Under strict (ε, δ)-DP, private-coin protocols reduce to public-coin ones at identical cost.
- Locally DP verifier messages allow the same collapse via one extra transformation.
- With very loose ε in Ω(log n), private coins still yield genuine complexity savings.
- Merlin-Arthur protocol for privately testing product distributions is proven sample-optimal.
A new theory paper on arXiv opens a corner of differential privacy that had been sitting quietly untouched: what happens when a data-poor verifier tries to check properties of a distribution with help from an untrusted prover, and also wants to protect the sensitive samples it drew? The authors, Elbert Du, Cynthia Dwork, Pranay Tankala, and Linjun Zhang, argue this combination is almost obligatory. Their punchline: if we do not trust the prover to help with verification, why should we trust it with our sensitive sample?
A setup nobody had formalized
The paper builds on a line of work started by Chiesa and Gur and pushed further by Herman and Rothblum. In that world, a data-poor verifier determines whether a probability distribution has a property of interest by interacting with an all-powerful, data-rich but untrusted prover bent on convincing them that it has the property. The verifier sees only a handful of samples; the prover claims something like "this distribution has entropy m" or "its support size is s" and tries to convince the verifier.
Why bother? For many natural questions about a distribution over a domain of size N, testing without help needs close to N samples. With a prover to lean on, the verifier can slash that sample count dramatically. Nothing in the prior framework, however, said anything about privacy of the samples the verifier actually holds.