Overcoming the Randomness-Utility Trade-off in Answering Differentially Private Linear Queries

Abstract

We study the question of answering linear queries with differential privacy using few (expected) random bits. We provide a randomness-efficient analog of the $\Vert \cdot {\Vert }_K$-norm mechanism of Hardt and Talwar [HT10]. For the ${\ell }_{\infty }$-error, our algorithm can answer $d$ linear queries with $O(d/\epsilon )$ error using $O(\log d)$ random bits, improving upon algorithms of Canonne et al. and Ghentiyala [CSV25, Ghe26]; this is optimal when $\epsilon \le 1/d$. We also provide a computationally efficient version of our algorithm, albeit with an $O(\log d)$ multiplicative increase in the error.