2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | P.4.2 | ||
| Paper Title | Linear and Range Counting under Metric-based Local Differential Privacy | ||
| Authors | Zhuolun Xiang, University of Illinois at Urbana-Champaign, United States; Bolin Ding, Alibaba Group, United States; Xi He, University of Waterloo, Canada; Jingren Zhou, Alibaba Group, United States | ||
| Session | P.4: Information Privacy II | ||
| Presentation | Lecture | ||
| Track | Cryptography, Security and Privacy | ||
| Manuscript | Click here to download the manuscript | ||
| Virtual Presentation | Click here to watch in the Virtual Symposium | ||
| Abstract | 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. | ||
Plan Ahead
2021 IEEE International Symposium on Information Theory
11-16 July 2021 | Melbourne, Victoria, Australia
