Table of contents
Revealing Information while Preserving Privacy
The Hospital Story
Easy Tempting Solution
Our Model: Statistical Database (SDB)
The Privacy Game: Information-Privacy Tradeoff
Approaches to SDB Privacy [AW 89]
Perturbation Techniques [AW89]
Main Question: How much perturbation is needed to achieve privacy?
Privacy from ï‚»ïƒ–n Perturbation
The Useless Database Achieves Best Possible Perturbation: Perturbation << ïƒ–n Implies no Privacy!
The Adversary as a Decoding Algorithm
Goldreich-Levin Hardcore Bit
Comparing the Tasks
Recall Our Goal: Perturbation << ïƒ–n Implies no Privacy!
Proof of Main Theorem The Adversary Reconstruction Algorithm
Proof of Main Theorem Correctness of the Algorithm
Extensions of the Main Theorem
Notes on Impossibility Results
Bounded Adversary Model
Summary and Open Questions
Our Privacy Definition (bounded adversary model)