Secure Multiparty Computation for Synthetic Data Generation from Distributed Data

Mayana Pereira, Sikha Pentyala, Anderson Nascimento, Rafael T. de Sousa Jr., Martine De Cock

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:

  1. 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.
  2. Using the Laplace Mechanism to get a noisy (private) answer to that query from the real data.
  3. 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$).
Figure 1: AUC-ROC of LR models trained on synthetic data generated by two different modes (centralized and distributed) with varying privacy budget. The results presented are averaged over 10 runs.
  • 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$).
Table 1: Runtime for different values of T (MWEM iterations). Central: Centralized setting runs the MWEM algorithm Rosenblatt et al. [2020]; Other columns: Distributed setting with 2 data holders and MPC protocols run on different number of computing servers with different security settings: 2PC Cramer et al. [2018], 3PC Araki et al. [2016], Dalskov et al. [2021], 4PC Dalskov et al. [2021]. |Q| is the number of queries, (a x b) denotes the dataset dimension.

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

Abstract

Legal and ethical restrictions on accessing relevant data inhibit data science research in critical domains such as health, finance, and education. Synthetic data generation algorithms with privacy guarantees are emerging as a paradigm to break this data logjam. Existing approaches, however, assume that the data holders supply their raw data to a trusted curator, who uses it as fuel for synthetic data generation. This severely limits the applicability, as much of the valuable data in the world is locked up in silos, controlled by entities who cannot show their data to each other or a central aggregator without raising privacy concerns. To overcome this roadblock, we propose the first solution in which data holders only share encrypted data for differentially private synthetic data generation. Data holders send shares to servers who perform Secure Multiparty Computation (MPC) computations while the original data stays encrypted. We instantiate this idea in an MPC protocol for the Multiplicative Weights with Exponential Mechanism (MWEM) algorithm to generate synthetic data based on real data originating from many data holders without reliance on a single point of failure.
BibTeX
@misc{pereira2022secure,
  author = {Mayana Pereira and Sikha Pentyala and Anderson Nascimento and Rafael T. de Sousa Jr. and Martine De Cock},
  title = {{Secure Multiparty Computation for Synthetic Data Generation from Distributed Data}},
  year = {2022},
  eprint = {2210.07332},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2210.07332},
}
Figure