VertiMRF: Differentially Private Vertical Federated Data Synthesis

Data synthesis is a promising solution to share data for various downstream analytic tasks without exposing raw data. However, without a theoretical privacy guarantee, a synthetic dataset would still leak some sensitive information in raw data. As a countermeasure, differential privacy is widely adopted to safeguard data synthesis by strictly limiting the released information. This technique is advantageous yet presents significant challenges in the vertical federated setting, where data attributes are distributed among different data parties. The main challenge lies in maintaining privacy while efficiently and precisely reconstructing the correlation between attributes. In this paper, we propose a novel algorithm called VertiMRF, designed explicitly for generating synthetic data in the vertical setting and providing differential privacy protection for all information shared from data parties. We introduce techniques based on the Flajolet-Martin (FM) sketch for encoding local data satisfying differential privacy and estimating cross-party marginals. We provide theoretical privacy and utility proof for encoding in this multi-attribute data. Collecting the locally generated private Markov Random Field (MRF) and the sketches, a central server can reconstruct a global MRF, maintaining the most useful information. Two critical techniques introduced in our VertiMRF are dimension reduction and consistency enforcement, preventing the noise of FM sketch from overwhelming the information of attributes with large domain sizes when building the global MRF. These two techniques allow flexible and inconsistent binning strategies of local private MRF and the data sketching module, which can preserve information to the greatest extent. We conduct extensive experiments on four real-world datasets to evaluate the effectiveness of VertiMRF. End-to-end comparisons demonstrate the superiority of VertiMRF.