  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.
