We present Nebula, a system for differentially private histogram estimation on data distributed among clients. 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 ((\varepsilon,\delta)) differential privacy guarantees. Compared to existing systems, Nebula uniquely achieves: i) a strict upper bound on client privac...
