Differentially Private Histograms for Range-Sum Queries

University:
Boston University
Course:
MET CS 201 | Introduction to Programming
Academic year:

2023
Views:

332

Pages:

19
Author:

szkafut4kac

Differentially Private Histograms for Range-‐Sum Queries: A Modular Approach Privacy-‐preserving data publishing • A curator (e.g., a company, a hospital, an institution, etc.) gathers data about its users • Third-‐parties (e.g., research labs, advertising agencies, etc.) wish to learn statistical facts about the collected data • How can the curator release useful statistics while preserving user privacy? Users Curator 3rd party 1 ϵ-‐differential privacy [Dwork, ICALP’06] • Publishing statistics can reveal potentially private information 2 ϵ-‐differential privacy [Dwork, ICALP’06] • Publishing statistics can reveal potentially private information D the database is hidden Curator 2 ϵ-‐differential privacy [Dwork, ICALP’06] • Publishing statistics can reveal potentially private information D the database is hidden Curator 2 ϵ-‐differential privacy [Dwork, ICALP’06] • Publishing statistics can reveal potentially private information D’ Before publishing, the adversary happens to know everything, except for Alice 2 ϵ-‐differential privacy [Dwork, ICALP’06] • Publishing statistics can reveal potentially private information D’ 2 ϵ-‐differential privacy [Dwork, ICALP’06] • Publishing statistics can reveal potentially private information Published data Adversary’s view 2 ϵ-‐differential privacy [Dwork, ICALP’06] • Publishing statistics can reveal potentially private information Published data Adversary’s view 2 ϵ-‐differential privacy [Dwork, ICALP’06] • Main idea – Randomized Mechanism: Hide the presence of any user, by hiding the effect he has on the published statistics M Randomized Mechanism t 3 ϵ-‐differential privacy [Dwork, ICALP’06] • Main idea – Any output (called transcript) of M is produced with almost the same probability, whether any single user was in the database (D) or not (D’) M OR Randomized Mechanism t 3 Laplace Perturbation Algorithm (LPA) [Dwork et al., TCC’06] • Add noise drawn from the Laplace distribution with mean 0 4 Laplace Perturbation Algorithm (LPA) [Dwork et al., TCC’06] • Add noise drawn from the Laplace distribution with mean 0 How much noise? 4 Laplace Perturbation Algorithm (LPA) [Dwork et al., TCC’06] • The scale of the distribution depends on the sensitivity Δ – Δ: maximum amount of statistical information that can be affected by any single user • I.e. how much the statistics will change if we remove any single user 4 Laplace Perturbation Algorithm (LPA) [Dwork et al., TCC’06] Lap(1/ϵ) + Lap(1/ϵ) + Lap(1/ϵ) + Lap(1/ϵ) Lap(1/ϵ) + + Lap(1/ϵ)Lap(1/ϵ) + + 4 Setting: Range queries on histograms • Range query: – Give me the number of HIV+ patients with age range 25-‐40 5 Problem definition • Publish a differentially private histogram • Any range query (not known a priori) on the released histogram should get an answer close to the real one • Focus on both accuracy and time efficiency 6 Laplace Perturbation Algorithm (LPA) Pros • • Each output bin value very close to the original (small error per bin) Very fast (O(n)) Lap(1/ϵ) + Lap(1/ϵ) + Lap(1/ϵ) + Lap(1/ϵ) Lap(1/ϵ) + + Lap(1/ϵ)Lap(1/ϵ) + + 7 Laplace Perturbation Algorithm (LPA) Pros • • • Each output bin value very close to the original (small error per bin) Very fast (O(n)) Cons When computing ranges, the error due to noise accumulates (error proportional to range size) Lap(1/ϵ) + Lap(1/ϵ) + Lap(1/ϵ) + Lap(1/ϵ) Lap(1/ϵ) + + Lap(1/ϵ)Lap(1/ϵ) + + 7