Data Synthesis with Differential Privacy

Abstract:

Databases store sensitive information, raising significant privacy concerns when the data is utilized and shared. A canonical approach to address this concern is to generate a synthetic database from the input database under differential privacy, which provides rigorous guarantees to safeguard privacy. The synthetic database mimics the input database and can be released to the public, enabling downstream applications to use it indefinitely without compromising privacy.

This thesis investigates the generation of synthetic databases from an input database under differential privacy. It first introduces PrivMRF, a novel solution for synthesizing single-relation databases without foreign keys. PrivMRF presents a novel method for constructing a Markov Random Field that accurately captures the correlations among the attributes in the relation, resulting in synthetic data with superior utility compared to state-of-the-art methods. Next, the thesis presents PrivLava, the first solution capable of synthesizing multi-relation databases where foreign key references form a directed acyclic graph. PrivLava incorporates latent variables into graphical models to synthesize relations, effectively capturing the correlations among data tuples linked by foreign keys. Finally, the thesis introduces PrivPetal, an advanced method for synthesizing multi-relation databases with foreign keys under differential privacy. PrivPetal constructs a flattened relation from the input relations, synthesizes this flattened relation, and then decomposes the synthesized relation into base relations. As such a flattened relation is of very high dimensionality, PrivPetal proposes to use permutation relations as a surrogate during the synthesis, thereby reducing privacy costs while maintaining data utility. Extensive experiments demonstrate that PrivMRF, PrivLava, and PrivPetal significantly outperform state-of-the-art methods by a large margin.