We consider the problem of property testing for differential privacy: with black-box access to a purportedly private algorithm, can we verify its privacy guarantees? In particular, we show that any privacy guarantee that can be efficiently verified is also efficiently breakable in the sense that there exist two databases between which we can efficiently distinguish. We give lower bounds on the query complexity of verifying pure differential privacy, approximate differential privacy, random pure differential privacy, and random approximate differential privacy. We also give algorithmic upper bounds. The lower bounds obtained in the work are infeasible for the scale of parameters that are typically considered reasonable in the differential privacy literature, even when we suppose that the verifier has access to an (untrusted) description of the algorithm. A central message of this work is that verifying privacy requires compromise by either the verifier or the algorithm owner. Either the verifier has to be satisfied with a weak privacy guarantee, or the algorithm owner has to compromise on side information or access to the algorithm.
Several algorithms and tools have been proposed for formal verification of the DP guarantee of an algorithm . Much of this work focuses on verifying privacy given access to a description of the algorithm. There is a line of work using logical arguments (type systems, I O automata, Hoare logic, etc.) to verify privacy. These tools are aimed at automatic (or simplified) verification of privacy of source code. There is another related line of work where the central problem is testing software for privacy leaks. This work focuses on privacy leaks, such as a smart phone application surreptitiously leaking a user's email . Given sample access to two distributions @math and @math and a distance measure @math , the question of distinguishing between @math and @math is called . This question is closely related to the question of whether @math is private. There is a large body of work exploring lower bounds and algorithmic upper bounds for tolerant testing using standard distances (TV, KL, @math , etc.) with both @math and @math . In our work, we draw most directly from the techniques of @cite_7 .
@cite_7
2002001845
We introduce the notion of a canonical tester for a class of properties on distributions, that is, a tester strong and general enough that “a distribution property in the class is testable if and only if the canonical tester tests it.” We construct a canonical tester for the class of properties of one or two distributions that are symmetric and satisfy a certain weak continuity condition. Analyzing the performance of the canonical tester on specific properties resolves two open problems, establishing lower bounds that match known upper bounds: we show that distinguishing between entropy @math on distributions over @math requires @math samples, and distinguishing whether a pair of distributions has statistical distance @math requires @math samples. Our techniques also resolve a conjecture about a property that our canonical tester does not apply to: distinguishing identical distributions from those with statistical distance @math requires @math samples.