Nebula: Efficient, Private and Accurate Histogram Estimation

We present $\mathit{\text{Nebula}}$, a system for differentially private histogram estimation on data distributed among clients. $\mathit{\text{Nebula}}$ allows clients to independently decide whether to participate in the system, and locally encode their data so that an untrusted server only learns data values whose multiplicity exceeds a predefined aggregation threshold, with $(\epsilon ,\delta )$ differential privacy guarantees. Compared to existing systems, $\mathit{\text{Nebula}}$ uniquely achieves: $\mathit{\text{i)}}$ a strict upper bound on client privacy leakage; $\mathit{\text{ii)}}$ significantly higher utility than standard local differential privacy systems; and $\mathit{\text{iii)}}$ no requirement for trusted third-parties, multi-party computation, or trusted hardware. We provide a formal evaluation of $\mathit{\text{Nebula}}$'s privacy, utility and efficiency guarantees, along with an empirical assessment on three real-world datasets. On the United States Census dataset, clients can submit their data in just 0.0036 seconds and 0.0016 MB ($\mathbf{\text{efficient}}$), under strong $(\epsilon =1,\delta ={10}^{-8})$ differential privacy guarantees ($\mathbf{\text{private}}$), enabling $\mathit{\text{Nebula}}$'s untrusted aggregation server to estimate histograms with over 88% better utility than existing local differential privacy deployments ($\mathbf{\text{accurate}}$). Additionally, we describe a variant that allows clients to submit multi-dimensional data, with similar privacy, utility, and performance. Finally, we provide an implementation of $\mathit{\text{Nebula}}$.