Cryptography, Security and Privacy
Information Privacy II

Linear and Range Counting under Metric-based Local Differential Privacy

Zhuolun Xiang, Bolin Ding, Xi He, Jingren Zhou

Date & Time

01:00 am – 01:00 am


Local differential privacy (LDP) enables private data sharing and analytics without the need for a trusted data collector. Error-optimal primitives (for, e.g., estimating means and item frequencies) under LDP have been well studied. For analytical tasks such as range queries, however, the best known error bound is dependent on the domain size of private data, which is potentially prohibitive. This deficiency is inherent as LDP protects the same level of indistinguishability between any pair of private data values for each data downer. In this paper, we utilize an extension of eps-LDP called Metric-LDP or E-LDP, where a metric E defines heterogeneous privacy guarantees for different pairs of private data values and thus provides a more flexible knob than eps does to relax LDP and tune utility-privacy trade-offs. We show that, under such privacy relaxations, for analytical workloads such as linear counting, multi-dimensional range counting queries, and quantile queries, we can achieve significant gains in utility. In particular, for range queries under E-LDP where the metric E is the L1-distance function scaled by eps, we design mechanisms with errors independent on the domain sizes; instead, their errors depend on the metric E, which specifies in what granularity the private data is protected. We believe that the primitives we design for E-LDP will be useful in developing mechanisms for other analytical tasks, and encourage the adoption of LDP in practice.


Zhuolun Xiang

University of Illinois at Urbana-Champaign

Bolin Ding

Alibaba Group

Xi He

University of Waterloo

Jingren Zhou

Alibaba Group

Session Chair

Flavio Calmon

Harvard University