skip to main content
10.1145/2676726.2677005acmconferencesArticle/Chapter ViewAbstractPublication PagespoplConference Proceedingsconference-collections
research-article

Differential Privacy: Now it's Getting Personal

Published: 14 January 2015 Publication History

Abstract

Differential privacy provides a way to get useful information about sensitive data without revealing much about any one individual. It enjoys many nice compositionality properties not shared by other approaches to privacy, including, in particular, robustness against side-knowledge.
Designing differentially private mechanisms from scratch can be a challenging task. One way to make it easier to construct new differential private mechanisms is to design a system which allows more complex mechanisms (programs) to be built from differentially private building blocks in principled way, so that the resulting programs are guaranteed to be differentially private by construction.
This paper is about a new accounting principle for building differentially private programs. It is based on a simple generalisation of classic differential privacy which we call Personalised Differential Privacy (PDP). In PDP each individual has its own personal privacy level. We describe ProPer, a interactive system for implementing PDP which maintains a privacy budget for each individual. When a primitive query is made on data derived from individuals, the provenance of the involved records determines how the privacy budget of an individual is affected: the number of records derived from Alice determines the multiplier for the privacy decrease in Alice's budget. This offers some advantages over previous systems, in particular its fine-grained character allows better utilisation of the privacy budget than mechanisms based purely on the concept of global sensitivity, and it applies naturally to the case of a live database where new individuals are added over time.
We provide a formal model of the ProPer approach, prove that it provides personalised differential privacy, and describe a prototype implementation based on McSherry's PINQ system.

Supplementary Material

MPG File (p69-sidebyside.mpg)

References

[1]
A. Birgisson, F. McSherry, and M. Abadi. Differential privacy with information flow control. In Proceedings of the ACM SIGPLAN 6th Workshop on Programming Languages and Analysis for Security, PLAS '11, pages 2:1--2:6. ACM, 2011.
[2]
J. Cheney, L. Chiticariu, and W.-C. Tan. Provenance in databases: Why, how, and where. Found. Trends databases, 1(4):379--474, Apr. 2009. .
[3]
Y. Cui and J. Widom. Lineage tracing for general data warehouse transformations. The VLDB Journal The International Journal on Very Large Data Bases, 12(1):41--58, 2003.
[4]
S. B. Davidson, S. Khanna, S. Roy, J. Stoyanovich, V. Tannen, and Y. Chen. On provenance and privacy. In Proceedings of the 14th International Conference on Database Theory, pages 3--10. ACM, 2011.
[5]
C. Dwork. Differential privacy. In 33rd International Colloquium on Automata, Languages and Programming, part II (ICALP 2006), volume 4052, pages 1--12. Springer Verlag, 2006.
[6]
C. Dwork. Differential privacy: A survey of results. In Theory and Applications of Models of Computation, volume 4978 of Lecture Notes in Computer Science, pages 1--19. Springer Berlin Heidelberg, 2008.
[7]
C. Dwork. A firm foundation for private data analysis. Communications of the ACM, 54(1):86--95, 2011.
[8]
C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography, pages 265--284. Springer, 2006.
[9]
H. Ebadi. PINQuin, a framework for differentially private analysis. Master's thesis, Chalmers University of Technology, 2013.
[10]
M. Gaboardi, A. Haeberlen, J. Hsu, A. Narayan, and B. C. Pierce. Linear dependent types for differential privacy. In Proceedings of the 40th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL '13, pages 357--370. ACM, 2013.
[11]
P. W. Grefen and R. A. de By. A multi-set extended relational algebra: a formal approach to a practical issue. In Data Engineering, 1994. Proceedings. 10th International Conference, pages 80--88. IEEE, 1994.
[12]
A. Haeberlen, B. C. Pierce, and A. Narayan. Differential privacy under fire. In USENIX Security Symposium, 2011.
[13]
I. Hayes. Multi-relations in z. Acta Informatica, 29(1):33--62, 1992.
[14]
G. Kellaris and S. Papadopoulos. Practical differential privacy via grouping and smoothing. In Proceedings of the 39th international conference on Very Large Data Bases, PVLDB'13, pages 301--312. VLDB Endowment, 2013.
[15]
C. Li, M. Hay, V. Rastogi, G. Miklau, and A. McGregor. Optimizing linear counting queries under differential privacy. In Proceedings of the Twenty-ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database System, PODS '10, pages 123--134. ACM, 2010.
[16]
F. McSherry and R. Mahajan. Differentially-private network trace analysis. SIGCOMM Comput. Commun. Rev., 40(4):123--134, 2010. ISSN 0146--4833.
[17]
F. D. McSherry. Privacy integrated queries: an extensible platform for privacy-preserving data analysis. In Proceedings of the 2009 ACM SIGMOD International Conference on Management of data, pages 19--30. ACM, 2009.
[18]
D. Mir, S. Muthukrishnan, A. Nikolov, and R. N. Wright. Pan- private algorithms via statistics on sketches. In Proceedings of the Thirtieth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS '11, pages 37--48. ACM, 2011.
[19]
I. Mironov. On significance of the least significant bits for differential privacy. In ACM Conference on Computer and Communications Security. ACM, 2012.
[20]
K. R. O'Neill, M. R. Clarkson, and S. Chong. Information-flow security for interactive programs. In CSFW, pages 190--201. IEEE Computer Society, 2006.
[21]
C. Palamidessi and M. Stronati. Differential Privacy for relational algebra: improving the sensitivity bounds via constraint systems. In QAPL -- Tenth Workshop on Quantitative Aspects of Programming Languages, volume 85 of Electronic Proceedings in Theoretical Computer Science, pages 92--105. Open Publishing Association, 2012.
[22]
D. Proserpio, S. Goldberg, and F. McSherry. Calibrating data to sensitivity in private data analysis. 40th International Conference on Very Large Data Bases, VLDB'14, 7(8):637--648, 2014.
[23]
J. Reed and B. C. Pierce. Distance makes the types grow stronger: A calculus for differential privacy. In Proceedings of the 15th ACM SIG- PLAN International Conference on Functional Programming, ICFP'10, pages 157--168. ACM, 2010.
[24]
I. Roy, S. T. V. Setty, A. Kilzer, V. Shmatikov, and E. Witchel. Airavat: Security and privacy for mapreduce. In NSDI, pages 297--312. USENIX Association, 2010.
[25]
M. C. Tschantz, D. Kaynar, and A. Datta. Formal verification of differential privacy for interactive systems (extended abstract). Electron. Notes Theor. Comput. Sci., 276:61--79, Sept. 2011.
[26]
L. Waye. Privacy integrated data stream queries. In Proceedings of the 5th annual conference on Systems, programming, and applications: software for humanity. ACM, 2014.
[27]
J. T. Wittbold and D. M. Johnson. Information flow in nondeterministic systems. In IEEE Symposium on Security and Privacy, pages 144--161, 1990.
[28]
Y. Xiao, L. Xiong, and C. Yuan. Differentially private data release through multidimensional partitioning. In Proceedings of the 7th VLDB Conference on Secure Data Management. Springer-Verlag, 2010.

Cited By

View all
  • (2024)Cookie Monster: Efficient On-Device Budgeting for Differentially-Private Ad-Measurement SystemsProceedings of the ACM SIGOPS 30th Symposium on Operating Systems Principles10.1145/3694715.3695965(693-708)Online publication date: 4-Nov-2024
  • (2024)DPI: Ensuring Strict Differential Privacy for Infinite Data Streaming2024 IEEE Symposium on Security and Privacy (SP)10.1109/SP54263.2024.00124(1009-1027)Online publication date: 19-May-2024
  • (2023)DProvDB: Differentially Private Query Processing with Multi-Analyst ProvenanceProceedings of the ACM on Management of Data10.1145/36267611:4(1-27)Online publication date: 12-Dec-2023
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
POPL '15: Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages
January 2015
716 pages
ISBN:9781450333009
DOI:10.1145/2676726
  • cover image ACM SIGPLAN Notices
    ACM SIGPLAN Notices  Volume 50, Issue 1
    POPL '15
    January 2015
    682 pages
    ISSN:0362-1340
    EISSN:1558-1160
    DOI:10.1145/2775051
    • Editor:
    • Andy Gill
    Issue’s Table of Contents
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

In-Cooperation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 January 2015

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. differential privacy
  2. provenance

Qualifiers

  • Research-article

Conference

POPL '15
Sponsor:

Acceptance Rates

POPL '15 Paper Acceptance Rate 52 of 227 submissions, 23%;
Overall Acceptance Rate 860 of 4,328 submissions, 20%

Upcoming Conference

POPL '26

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)173
  • Downloads (Last 6 weeks)13
Reflects downloads up to 19 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Cookie Monster: Efficient On-Device Budgeting for Differentially-Private Ad-Measurement SystemsProceedings of the ACM SIGOPS 30th Symposium on Operating Systems Principles10.1145/3694715.3695965(693-708)Online publication date: 4-Nov-2024
  • (2024)DPI: Ensuring Strict Differential Privacy for Infinite Data Streaming2024 IEEE Symposium on Security and Privacy (SP)10.1109/SP54263.2024.00124(1009-1027)Online publication date: 19-May-2024
  • (2023)DProvDB: Differentially Private Query Processing with Multi-Analyst ProvenanceProceedings of the ACM on Management of Data10.1145/36267611:4(1-27)Online publication date: 12-Dec-2023
  • (2023)A Differential Privacy-based System for Efficiently Protecting Data Privacy2023 International Conference on Sustainable Computing and Smart Systems (ICSCSS)10.1109/ICSCSS57650.2023.10169412(1399-1404)Online publication date: 14-Jun-2023
  • (2023)Using Differential Privacy to Define Personal, Anonymous, and Pseudonymous DataIEEE Access10.1109/ACCESS.2023.332157811(109225-109236)Online publication date: 2023
  • (2023)dpUGC: Learn Differentially Private Representation for User Generated Contents (Best Paper Award, Third Place, Shared)Computational Linguistics and Intelligent Text Processing10.1007/978-3-031-24337-0_23(316-331)Online publication date: 26-Feb-2023
  • (2023)Self-adaptive Privacy Concern Detection for User-Generated ContentComputational Linguistics and Intelligent Text Processing10.1007/978-3-031-23793-5_14(153-167)Online publication date: 26-Feb-2023
  • (2022)Solo: a lightweight static analysis for differential privacyProceedings of the ACM on Programming Languages10.1145/35633136:OOPSLA2(699-728)Online publication date: 31-Oct-2022
  • (2022)Interpreting Epsilon of Differential Privacy in Terms of Advantage in Guessing or Approximating Sensitive Attributes2022 IEEE 35th Computer Security Foundations Symposium (CSF)10.1109/CSF54842.2022.9919656(96-111)Online publication date: Aug-2022
  • (2022)dK-Personalization: Publishing Network Statistics with Personalized Differential PrivacyAdvances in Knowledge Discovery and Data Mining10.1007/978-3-031-05933-9_16(194-207)Online publication date: 16-May-2022
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media