Dynamic Anonymization: Accurate Statistical Analysis with Privacy Preservation

Xiaokui Xiao and Yufei Tao

In ACM Conference on Management of Data (SIGMOD), 2008

A statistical database (StatDB) retrieves only aggregate results, as opposed to individual tuples. This paper investigates the construction of a privacy preserving StatDB that can (i) accurately answer an infinite number of counting queries, and (ii) effectively protect privacy against an adversary that may have acquired all the previous query results. The core of our solutions is a novel technique called dynamic anonymization. Specifically, given a query, we on the fly compute a tailor-made anonymized version of the microdata, which maximizes the precision of the query result. Privacy preservation is achieved by ensuring that the combination of all the versions deployed to process the past queries does not allow accurate inference of sensitive information. Extensive experiments with real data confirm that our technique enables highly effective data analysis, while offering strong privacy guarantees.