Click here to start

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

Defining Privacy

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)

Slide 24