Privacy in Databases

Abstract

The question of how to analyze large amounts of data while preserving privacy now prevails more than ever. In the course of history there have been many failed attempts, showing that reasoning about privacy is fraught with pitfalls. This caused an increased interest in a mathematically robust definition of privacy.

We will prove that absolute disclosure prevention is impossible. In other words, a person that gains access to a database can always breach the privacy of an individual. This motivated the move to assuring relative disclosure prevention. One of the most promising definitions in this area is differential privacy. It addresses all the currently known attacks and is applicable in many situations.

Networked data also poses challenging privacy issues. Both active and passive attacks, where the underlying structure of the network is used to de-anonymize individuals, are discussed. Degree anonymization and algorithms to create a degree anonymous graphs will also be given.