TL;DR
This paper presents a novel framework for generating differentially private (DP) synthetic data from distributed, siloed sources without ever revealing raw data to a central authority. By implementing the Multiplicative Weights with Exponential Mechanism (MWEM) algorithm using Secure Multiparty Computation (MPC), the authors enable multiple data holders to collaboratively produce high-utility synthetic datasets while keeping their original records end-to-end encrypted.
What Problem Does This Paper Address?
Data science often hits a "logjam" in sensitive fields like healthcare and finance. While synthetic data is a promising solution—providing datasets that mimic real-world distributions without exposing individual records—existing methods usually rely on a trusted curator. In this traditional model, all data holders must send their raw, plaintext data to a single central entity.
In the real world, legal frameworks like GDPR and competitive concerns make this "central aggregator" a non-starter. Data remains locked in silos. The challenge this paper tackles is: How can we generate a single synthetic dataset based on the combined information of multiple parties who do not trust each other or any third party with their raw data?
Methods
The authors bridge the gap between Differential Privacy (DP) (which protects the output) and Secure Multiparty Computation (MPC) (which protects the input).
The Core Algorithm: MWEM
They adapt the Multiplicative Weights with Exponential Mechanism (MWEM) algorithm. MWEM is an iterative process that maintains a synthetic distribution and improves it by:
- Using the Exponential Mechanism to pick a query (e.g., "how many people have X condition?") where the synthetic data currently performs poorly compared to the real data.
- Using the Laplace Mechanism to get a noisy (private) answer to that query from the real data.
- Updating the synthetic distribution to better match that answer.
The Innovation: MPC Integration
The authors developed specific MPC protocols to run the privacy-critical parts of MWEM over encrypted data:
- $\pi_{QEM}$ (Secure Exponential Mechanism): A protocol for secure sampling. It computes the "scores" for queries and selects one without revealing which query was the best or what the underlying data looked like.
- $\pi_{LAP}$ (Secure Laplace Mechanism): A protocol to generate noise from a Laplacian distribution and add it to the query results, all within the encrypted domain.
Crucially, they realized that the synthetic distribution itself does not need to be encrypted—only the steps that interact with the real, distributed data. This "hybrid" approach keeps the computation efficient.
Datasets
The framework was evaluated using two well-known benchmarks in the DP community:
- Car Evaluation Dataset: A smaller dataset (1,728 records, 7 attributes) used to test basic utility.
- Adult Dataset (Census Income): A larger, more complex dataset (12,499 records, 12 attributes) used to evaluate how the system scales.
Key Insights and Ideas
- Input Privacy + Output Privacy: This is a "best of both worlds" approach. MPC ensures that the servers running the computation never see the raw data (input privacy), while DP ensures that the final synthetic dataset doesn't leak individual info (output privacy).
- Eliminating the Single Point of Failure: By using MPC (supporting 2, 3, or 4 computing parties), the system remains secure even if one of the computing servers is compromised.
- Side-Channel Resistance: The authors specifically designed their MPC loops to be deterministic. For example, in the sampling protocol ($\pi_{QEM}$), they avoid "early exits" in loops that could leak information about which index was selected through timing differences.
- Fixed-Point Arithmetic: To avoid known privacy vulnerabilities associated with floating-point math in DP, the authors implemented their mechanisms using 32-bit fixed-point precision.
Key Results
The experiments show that moving from a centralized model to a distributed MPC model results in virtually no loss in data utility.
- Utility: As seen in Figure 1, the performance (AUC-ROC) of machine learning models trained on the synthetic data is nearly identical for both the centralized and distributed modes across various privacy budgets ($\epsilon$).
- Runtime: While MPC is naturally slower than plaintext computation, the runtimes remain practical. For the Adult dataset with 500 queries, the process takes between 40 seconds (3-party passive security) and 3 minutes (2-party passive), depending on the security configuration and number of iterations ($T$).
Limitations and Future Work
- Dimensionality: MWEM is effective but can struggle with extremely high-dimensional data (e.g., hundreds of features) because the size of the synthetic distribution grows exponentially.
- Advanced Generative Models: The authors suggest that future work should focus on developing MPC protocols for more complex generators, such as DP-GANs (Generative Adversarial Networks), which might handle high-dimensional data better than MWEM.
- Preprocessing: The current work assumes data is already cleaned and aligned across holders. Future iterations could include secure MPC-based preprocessing and data joining.
Summary updated