skip to main content
10.1145/3264820.3264827acmconferencesArticle/Chapter ViewAbstractPublication PagespldiConference Proceedingsconference-collections
short-paper

Geometric Noise for Locally Private Counting Queries

Published: 15 January 2018 Publication History

Abstract

Local differential privacy (LDP) is a variant of differential privacy (DP) where the noise is added directly on the individual records, before being collected. The main advantage with respect to DP is that we do not need a trusted third party to collect and sanitise the sensitive data of the user. The main disadvantage is that the trade-off between privacy and utility is usually worse than in DP, and typically to retrieve reasonably good statistics from the locally sanitised data it is necessary to have access to a huge collection of them. In this paper, we focus on the problem of estimating the counting queries on numerical data, and we propose a variant of LDP based on the addition of geometric noise. Such noise function is known to have appealing properties in the case of counting queries. In particular, it is universally optimal for DP, i.e., it provides the best utility for a given level of DP, regardless of the side knowledge of the attacker. We explore the properties of geometric noise for counting queries in the LDP setting, and we conjecture an optimality property, similar to the one that holds in the DP setting.

References

[1]
April 20, 2011. 3G Apple iOS Devices Are Storing Users' Location Data. The New York Times (April 20, 2011).
[2]
Dakshi Agrawal and Charu C. Aggarwal. 2001. On the Design and Quantification of Privacy Preserving Data Mining Algorithms. In Proceedings of the Twentieth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS '01). ACM, New York, NY, USA, 247--255.
[3]
Mário S. Alvim, Konstantinos Chatzikokolakis, Catuscia Palamidessi, and Anna Pazii. 2018. Metric-based local differential privacy for statistical applications, In Proceedings of the IEEE Symposium on Foundations of Computing Security (CSF'18). CoRR abs/1805.01456. arXiv:1805.01456 http://arxiv.org/abs/1805.01456
[4]
Miguel E. Andrés, Nicolás E. Bordenabe, Konstantinos Chatzikokolakis, and Catuscia Palamidessi. 2013. Geo-indistinguishability: differential privacy for location-based systems. In Proceedings of the 20th ACM Conference on Computer and Communications Security (CCS 2013). ACM, 901--914.
[5]
James Ball. 2014. Angry birds and 'leaky' phone apps targeted by NSA and GCHQ for user data. The Guardian (January 27, 2014). www.theguardian.com/world/2014/jan/27/nsa-gchq-smartphone-app-angry-birds-personal-data.
[6]
Konstantinos Chatzikokolakis, Miguel E. Andrés, Nicolás E. Bordenabe, and Catuscia Palamidessi. 2013. Broadening the scope of Differential Privacy using metrics. In Proceedings of the 13th International Symposium on Privacy Enhancing Technologies (PETS 2013) (Lecture Notes in Computer Science), Emiliano De Cristofaro and Matthew Wright (Eds.), Vol. 7981. Springer, 82--102.
[7]
John C. Duchi, Michael I. Jordan, and Martin J. Wainwright. 2013. Local Privacy and Statistical Minimax Rates. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, 429--438.
[8]
Cynthia Dwork, Frank Mcsherry, Kobbi Nissim, and Adam Smith. 2006. Calibrating noise to sensitivity in private data analysis. In In Proceedings of the Third Theory of Cryptography Conference (TCC) (Lecture Notes in Computer Science), Shai Halevi and Tal Rabin (Eds.), Vol. 3876. Springer, 265--284.
[9]
Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. 2014. RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response. In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security (CCS), Gail-Joon Ahn, Moti Yung, and Ninghui Li (Eds.). ACM, 1054--1067.
[10]
Arpita Ghosh, Tim Roughgarden, and Mukund Sundararajan. 2009. Universally utility-maximizing privacy mechanisms. In Proceedings of the 41st annual ACM Symposium on Theory of Computing (STOC). ACM, 351--360.
[11]
Ashwin Machanavajjhala, Daniel Kifer, Johannes Gehrke, and Muthuramakrishnan Venkitasubramaniam. 2007. l-diversity: Privacy beyond k-anonymity. ACM Transactions on Knowledge Discovery from Data (TKDD) 1, 1, Article 3 (2007).
[12]
A. Narayanan and V. Shmatikov. 2008. Robust De-anonymization of Large Sparse Datasets. In 2008 IEEE Symposium on Security and Privacy (S&P 2008). 111--125.
[13]
Arvind Narayanan and Vitaly Shmatikov. 2009. De-anonymizing Social Networks. In Proceedings of the 30th IEEE Symposium on Security and Privacy (S&P 2009). IEEE Computer Society, 173--187.
[14]
Pierangela Samarati. 2001. Protecting Respondents' Identities in Microdata Release. IEEE Trans. Knowl. Data Eng 13, 6 (2001), 1010--1027.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PLAS '18: Proceedings of the 13th Workshop on Programming Languages and Analysis for Security
October 2018
59 pages
ISBN:9781450359931
DOI:10.1145/3264820
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 January 2018

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. counting queries
  2. geometric noise
  3. local differential privacy

Qualifiers

  • Short-paper

Funding Sources

  • ANR

Conference

CCS '18
Sponsor:

Acceptance Rates

PLAS '18 Paper Acceptance Rate 2 of 4 submissions, 50%;
Overall Acceptance Rate 43 of 77 submissions, 56%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)7
  • Downloads (Last 6 weeks)1
Reflects downloads up to 03 Jan 2025

Other Metrics

Citations

Cited By

View all

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media