Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR24-169 | 4th November 2024 22:56

The Randomness Complexity of Differential Privacy

RSS-Feed




TR24-169
Authors: Clément Canonne, Francis Su, Salil Vadhan
Publication: 4th November 2024 22:57
Downloads: 308
Keywords: 


Abstract:

We initiate the study of the *randomness complexity* of differential privacy, i.e., how many random bits an algorithm needs in order to generate accurate differentially private releases. As a test case, we focus on the task of releasing the results of $d$ counting queries, or equivalently all one-way marginals on a $d$-dimensional dataset with boolean attributes. While standard differentially private mechanisms for this task have randomness complexity that grows linearly with $d$, we show that, surprisingly, only $\log_2 d+O(1)$ random bits (in expectation) suffice to achieve an error that depends polynomially on $d$ (and is independent of the size $n$ of the dataset), and furthermore this is possible with pure, unbounded differential privacy and privacy-loss parameter $\varepsilon=1/\mathrm{poly}(d)$. Conversely, we show that at least $\log_2 d-O(1)$ random bits are also necessary for nontrivial accuracy, even with approximate, bounded DP, provided the privacy-loss parameters satisfy $\varepsilon,\delta\leq 1/\mathrm{poly}(d)$. We obtain our results by establishing a close connection between the randomness complexity of differentially private mechanisms and the geometric notion of "secluded partitions" of $\mathbb{R}^d$ recently introduced and studied by Vander Woude et al. (2022, 2023).



ISSN 1433-8092 | Imprint