Differential Privacy of Hierarchical Census Data: An Optimization Approach

Ferdinando Fioretto, Pascal Van Hentenryck

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

This paper is motivated by applications of a Census Bureau interested in releasing aggregate socio-economic data about a large population without revealing sensitive information. The released information can be the number of individuals living alone, the number of cars they own, or their salary brackets. Recent events have identified some of the privacy challenges faced by these organizations. To address them, this paper presents a novel differential-privacy mechanism for releasing hierarchical counts of individuals satisfying a given property. The counts are reported at multiple granularities (e.g., the national, state, and county levels) and must be consistent across levels. The core of the mechanism is an optimization model that redistributes the noise introduced to attain privacy in order to meet the consistency constraints between the hierarchical levels. The key technical contribution of the paper shows that this optimization problem can be solved in polynomial time by exploiting the structure of its cost functions. Experimental results on very large, real datasets show that the proposed mechanism provides improvements up to two orders of magnitude in terms of computational efficiency and accuracy with respect to other state-of-the-art techniques.

Original languageEnglish (US)
Title of host publicationPrinciples and Practice of Constraint Programming - 25th International Conference, CP 2019, Proceedings
EditorsThomas Schiex, Simon de Givry
PublisherSpringer
Pages639-655
Number of pages17
ISBN (Print)9783030300470
DOIs
StatePublished - 2019
Externally publishedYes
Event25th International Conference on Principles and Practice of Constraint Programming, CP 2019 - Stamford , United States
Duration: Sep 30 2019Oct 4 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11802 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference25th International Conference on Principles and Practice of Constraint Programming, CP 2019
CountryUnited States
CityStamford
Period9/30/1910/4/19

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Differential Privacy of Hierarchical Census Data: An Optimization Approach'. Together they form a unique fingerprint.

  • Cite this

    Fioretto, F., & Van Hentenryck, P. (2019). Differential Privacy of Hierarchical Census Data: An Optimization Approach. In T. Schiex, & S. de Givry (Eds.), Principles and Practice of Constraint Programming - 25th International Conference, CP 2019, Proceedings (pp. 639-655). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11802 LNCS). Springer. https://doi.org/10.1007/978-3-030-30048-7_37