  Differential Privacy (DP) is often presented as a strong privacy-enhancing
technology with broad applicability and advocated as a de-facto standard for
releasing aggregate statistics on sensitive data. However, in many embodiments,
DP introduces a new attack surface: a malicious entity entrusted with releasing
statistics could manipulate the results and use the randomness of DP as a
convenient smokescreen to mask its nefariousness. Since revealing the random
noise would obviate the purpose of introducing it, the miscreant may have a
perfect alibi. To close this loophole, we introduce the idea of
\textit{Verifiable Differential Privacy}, which requires the publishing entity
to output a zero-knowledge proof that convinces an efficient verifier that the
output is both DP and reliable. Such a definition might seem unachievable, as a
verifier must validate that DP randomness was generated faithfully without
learning anything about the randomness itself. We resolve this paradox by
carefully mixing private and public randomness to compute verifiable DP
counting queries with theoretical guarantees and show that it is also practical
for real-world deployment. We also demonstrate that computational assumptions
are necessary by showing a separation between information-theoretic DP and
computational DP under our definition of verifiability.
