PaperlayerView exact revision on arXiv

Source-linked AI summary

Distributed and Private Textual Data Synthesis from Embeddings

Ergute Bao, Hongyan Chang, Ali Shahin Shamsabadi, Ting Yu, Xiaokui Xiao

arXiv:2609.10104v2cs.CR

TL;DR

Distributed DP text synthesis faces a mismatch between centralized pipelines and settings without a trusted curator, where repeated synchronized participation may also be impractical. Fre-E2T combines embedding-space DP centroids and semantic support protection with a secure distributed implementation. Across real-world datasets, it achieves utility comparable to, and sometimes better than, the state-of-the-art centralized DP baseline.

  • Problem

    Existing DP synthesis pipelines are designed for centralized settings, while distributed adaptations may require trusted access, costly model capabilities, or repeated synchronized participation.

    Source: §1 · p. 1

  • Method

    Fre-E2T releases DP centroids for frequent embedding regions, adds semantic support protection, and implements the algorithm with a secure distributed protocol.

    Source: §4.1 · p. 4, §9 · p. 13

  • Results

    Fre-E2T achieves utility comparable to, and sometimes better than, the state-of-the-art centralized DP baseline across real-world datasets.

    Source: §9 · p. 13

  • Takeaways & Limitations

    The approach offers stronger protection for infrequent user data and better practicality in distributed settings than the compared state-of-the-art method.

    Source: §9 · p. 13

    The analysis is restricted to differential privacy under a semi-honest threat model, so arbitrary environments outside those assumptions are not covered.

    Source: Ethical Considerations · p. 14

Abstract

from arXiv · show

We revisit differentially private (DP) text synthesis in the realistic setting of distributed users, where privacy concerns preclude a trusted curator with access to raw user texts. Existing DP text synthesis pipelines are designed for a trusted, centralized curator and often cannot be deployed in distributed settings due to unrealistic trust and access assumptions; when adapted naively, they require repeated, tightly synchronized user participation and incur significant overhead. To address this gap, we propose a DP--cryptography co-design for textual data synthesis that requires no trusted curator and requires only lightweight user participation. Our approach has two optimized components. First, we design a distributed-friendly DP synthesis algorithm that releases a one-time DP summary in an embedding space: it identifies frequent semantic regions and releases their DP centroids, enabling training-free, non-iterative offline text synthesis. We further introduce semantic support protection, which ensures the released summary avoids semantic neighborhoods of infrequent texts, reducing the risk of exposing rare user data. Second, we develop a custom secure protocol that implements this algorithm over distributed user data, enforcing end-to-end DP guarantees without requiring a trusted curator. On four benchmarks, we achieve utility comparable to the state-of-the-art centralized DP synthesis method.

1 Introduction

Existing DP text synthesis assumes a trusted curator and can require repeated synchronized participation, costly model access, or unavailable metadata. Fre-E2T addresses these constraints with a distributed DP summary and adds protection against outputs near semantically infrequent texts.

1 Introduction

  • Centralized DP synthesis assumes a trusted curator, while distributed adaptations can require repeated synchronized participation, costly model access, or unavailable labels and metadata.These requirements conflict with distributed settings where users may not trust a curator and device availability and communication are constrained.Source: §1 · p. 1

1.1 Our Contributions

  • Fre-E2T pairs a distributed-friendly DP algorithm with a customized secure computation protocol.It builds a one-time embedding-space summary by identifying frequent semantic regions and releasing privacy-preserving DP centroids, without costly model fine-tuning.Source: §1.1 · p. 2

2 Problem Definition

  • The target setting has one private text per user, no trusted curator, two non-colluding servers, and at most two short user-server participation phases.Users and servers are honest-but-curious, and no publicly available labels or metadata are assumed.Source: §2 · p. 2

2.1 Differential Privacy Requirement

  • Differential privacy protects whether an individual text is present, but does not rule out outputs near a unique or rare text in embedding space.The paper targets standard text-level (ε,δ)-DP and motivates semantic support protection as an additional guarantee.Source: §2.1 · p. 2, §2.2 · p. 3

2.2 Semantic Support Protection (SSP)

  • Semantic support protection limits, with small probability, outputs near semantically infrequent texts in embedding space.An (r,t)-semantically infrequent text has fewer than t data points within distance r; the protection complements rather than follows directly from DP.Source: §2.2 · p. 3

3 Related Work

Prior distributed DP text-synthesis adaptations retain requirements such as model-gradient access, public labels, or repeated synchronized participation. Fre-E2T instead summarizes texts through frequent embedding clusters and produces synthetic text from their DP centroids.

3 Related Work

  • Distributed adaptations of centralized DP synthesis often require LM gradient access, public labels, or repeated synchronized user-server participation.Such requirements can be difficult to scale when device availability is intermittent and communication is costly.Source: §3 · p. 3

4 Synthesizing Texts via Frequent Embeddings

  • Fre-E2T avoids iterative clustering by summarizing embeddings into clusters and inverting their centroids into synthetic text.Clustering represents nearby data points by a centroid, while the text inverter maps each centroid back to textual data.Source: §4 · pp. 3–4

4.1 The Complete Algorithm

  • Fre-E2T projects text embeddings, partitions the projected space into randomly shifted grid buckets, and uses sample-and-threshold to identify heavy hitters.For heavy-hitting buckets, it adds Gaussian noise to the sum of original embeddings and computes centroids; inversion to text is post-processing.Source: §4.1 · p. 4

5 Privacy Analysis

Fre-E2T accounts for privacy loss from heavy-hitter identification and centroid release, using a probabilistic sensitivity bound for embedding sums. Its semantic support analysis bounds the chance that released centroids lie near infrequent texts.

5.1 Differential Privacy Guarantees

  • An unbounded worst-case embedding norm would make noise calibrated to the bucket-sum sensitivity destroy utility, so the analysis uses a probabilistic bound.In the stated default setting, the failure probability is 8.9 × 10^-11, a negligible share of the overall δ=10^-6.Source: §5.1 · p. 5
  • The overall DP guarantee composes the privacy costs of heavy-hitter identification and centroid release.The heavy-hitter histogram is analyzed with sample-and-threshold privacy, while centroid sums use a Gaussian mechanism under an L2 sensitivity bound.Source: §5.1 · pp. 5–6

5.2 Semantic Support Protection

  • For an infrequent embedding, the semantic support guarantee bounds the probability that a DP centroid lies within ψr of it.The theorem applies when at most t data points are within distance r; the failure probability δ* quickly converges to 0 as k and t increase under the stated moderate-parameter conditions.Source: §5.2 · p. 6
  • The centroid’s distance from an infrequent embedding is supported by the cluster’s majority of points being far from it, with DP noise not significantly reducing that distance.The authors do not claim existing methods lack similar guarantees; they note that explicit truncation of infrequent texts made their proof easier.Source: §5.2 · p. 6

6 Distributed Implementation

The distributed implementation realizes Fre-E2T with local preprocessing, encrypted heavy-hitter estimation, and secure noisy aggregation across two servers. The resulting DP centroids are inverted offline to produce synthetic text.

6 Distributed Implementation

  • The implementation reuses VOPRF, distributed discrete Gaussian noise with secure aggregation, and a shuffler-style channel, without claiming new cryptography protocols.The two-server implementation treats these existing protocols as black boxes with their inherited security guarantees.Source: §6 · p. 6
  • Users locally map text embeddings to bucket indices, obliviously encode the indices, and submit them with a sampling probability for heavy-hitter estimation.The synthesis server filters indices whose counts are below the public threshold.Source: §6 · pp. 6–7
  • Users sharing a frequent encrypted index securely aggregate their original embeddings with additive DP noise to obtain a DP centroid.The tagging and synthesis servers must not collude; only users who submitted the index in the prior phase respond to its broadcast.Source: §6 · p. 6
  • The synthesis server converts each perturbed centroid to text offline using Vec2Text, as post-processing that costs no additional privacy budget.Open-source language models can optionally paraphrase inverted texts to improve diversity.Source: §6 · p. 6

10 Synthesis server broadcasts H and C to all users

The distributed protocol estimates frequent embedding buckets, securely aggregates locally perturbed embeddings into DP centroids, and composes privacy guarantees across the releases. After the limited user participation, synthesis can run offline on the server.

10 Synthesis server broadcasts H and C to all users

  • Users perturb embeddings locally and secret-share them; the synthesis server combines bucket-specific shares and divides by the bucket count to form centroids.Centroid computation uses distributed discrete Gaussian noise and secure aggregation.Source: §10 · p. 7, §6.2 · pp. 7–8
  • Once users finish their participation, server-side synthesis runs offline; paraphrasing adds no privacy cost if its language model was not trained on user texts.The synthesis server reconstructs noisy centroids and inverts them into synthetic text.Source: §10 · p. 7, §6.2 · p. 8

6.1 Distributed Heavy Hitter Estimation

  • Oblivious tags hide bucket assignments; sampled reports are thresholded, while dummy indices protect non-frequent indices observed by the synthesis server.Dummy submissions follow a truncated shifted discrete Laplace distribution.Source: §6.1 · p. 7

6.2 Distributed Centroid Computation

  • For released buckets, users with matching tags add discrete Gaussian noise to embeddings and secret-share them for secure per-bucket aggregation.The local noises collectively provide the DP guarantee for the aggregated sum.Source: §6.2 · pp. 7–8, §6.3 · p. 8

6.3 Privacy in Distributed Settings

  • The distributed guarantee composes heavy-hitter and centroid privacy parameters; non-frequent points do not join centroid releases and compose in parallel.Theorem 8 states an overall (ε,δ)-DP guarantee for the algorithm.Source: §6.3 · pp. 8–9

7 Experiments

Experiments compare Fre-E2T with centralized Aug-PE across four datasets under matched privacy settings. Fre-E2T improves utility as privacy constraints loosen, with results varying by dataset and evaluation.

7.1 Main Results

  • Across four datasets, utility rises as ε loosens; Fre-E2T notably improves precision and recall on Instructions-2M and LMSYS Chat versus Aug-PE [110].On Yelp and TaylorAI, both methods achieve almost perfect precision and recall.Source: §7.1 · p. 9, Table 1 · p. 10
  • Fre-E2T’s L2 distance beats Aug-PE on Instructions-2M and LMSYS Chat at every privacy budget; on TaylorAI and Yelp, they are within 0.02.Fre-E2T’s distance falls monotonically with ε across all four datasets, while Aug-PE’s barely moves.Source: §7.1 · pp. 9–10

7.2 More Results on Text Quality

  • On Yelp, ε≥8 gives competitive classification accuracy with Aug-PE; higher paraphrasing temperature improves diversity, while classification utility stays largely unchanged.Average perplexity improves as ε grows and approaches that of real text samples.Source: §7.2 · p. 11, Table 3 · p. 12, Table 4 · p. 12

7.3 Ablation Studies

  • At ε=8, changing the budget split raises F1 from 0.36 to 0.42 on Instructions-2M and from 0.64 to 0.71 on LMSYS Chat.The tested budget split uses v=2 rather than the main-experiment choices.Source: §7.3 · p. 12
  • With finite ε, smaller buckets consistently improve F1; without noise, F1 first rises and then falls as buckets grow coarser.The authors attribute the finite-ε result to halved bucket edges halving noise while enough buckets still meet the threshold.Source: §7.3 · p. 12, Table 6 · p. 12
  • A second embedding model is evaluated at the centroid level because no public vector-to-text inverter exists for that embedding family.The alternative model is gte-modernbert-base; its radius is quantile-matched to the gtr embedding setup.Source: §7.3 · p. 12, Table 7 · p. 12

8 Design Choices and Limitations

Fre-E2T identifies frequent embedding-space clusters with high precision and recall, while the paper attributes its utility to sample-and-threshold identification and probabilistic sensitivity. Its end-to-end text quality remains limited by embedding inversion.

8 Design Choices and Limitations

  • The centralized-DP baseline removes distributed constraints and upper-bounds what any distributed realization of the same pipeline can achieve.It releases noisy counts and embedding sums, then retains buckets whose noisy count exceeds τ=100.Source: §8 · p. 13
  • At every ε, Fre-E2T identifies heavy clusters with precision and recall above 0.90; at ε=4, OUE recall is 3% on TaylorAI and 14% on Instructions-2M.Table 8 reports cluster-level precision and recall for heavy-hitting clusters with τ≥100.Source: §8 · p. 13, Table 8 · p. 13
  • Sample-and-threshold identifies clusters at almost no cost relative to a trusted curator, while probabilistic sensitivity keeps centroid-sum utility high at ε∈{4, 8, 16}.The paper contrasts its sensitivity-calibrated noise with local randomizers whose noise can overwhelm useful information.Source: §8 · p. 13
  • For Instructions-2M at ε=8, inversion reduces precision from 0.95 to 0.38 and recall from 0.98 to 0.34, with a substantial drop also seen centrally.The authors identify the black-box inverter, rather than distributed constraints, as the current end-to-end utility bottleneck.Source: §8 · p. 13, Table 9 · p. 13

9 Conclusion

The paper concludes that Fre-E2T offers a lightweight distributed approach to DP text synthesis with comparable and sometimes better utility, plus protection for infrequent texts. Its stated scope and supporting materials are qualified by the threat model and public-benchmark evaluation.

9 Conclusion

  • Fre-E2T is presented as a lightweight distributed text-synthesis algorithm that avoids trusted servers, LM gradient or parameter access, and tightly synchronized iterative participation.The conclusion reports comparable and sometimes better utility across real-world datasets, with extra protection for infrequent user data.Source: §9 · p. 13

Ethical Considerations

  • The work is restricted to differential privacy under a semi-honest threat model; arbitrary environments may involve exploits outside the analysis.The experiments use publicly available benchmark datasets and openly released language models, without human subjects or sensitive user data.Source: Ethical Considerations · p. 14

Open Science

  • The authors state that datasets are publicly available and that algorithm implementations, preprocessing scripts, and reproduction scripts will be released upon acceptance.Source: Open Science · p. 14

AI Use

  • ChatGPT was used to revise manuscript wording and figure presentation, not to design the algorithm or derive the privacy analysis.The authors state they verified that AI did not add claims or fabricate references.Source: AI Use · p. 14

Algorithm 3: CalibrateNoise

  • Algorithm 3 takes projection dimension, subsampling rate, budget factor, and sensitivity ratio as inputs and outputs the Gaussian noise scale for centroid sums.Source: Algorithm 3: CalibrateNoise · p. 17

A Additional Experiment Details and Results

The appendix specifies the datasets and default settings, then examines how embedding, projection, and frequency choices affect utility and protection. It also reports text-quality and full-input evaluations and gives distributed-protocol details.

A Additional Experiment Details and Results

  • TaylorAI, Instructions-2M, LMSYS Chat-1M, and Yelp provide the four evaluation datasets; non-English samples are filtered to limit potential multilingual embedding effects.LMSYS Chat-1M contains one million conversations from 210K unique IP addresses.Source: A Additional Experiment Details and… · p. 17

A.1 Hyperparameters

  • At k=20, the sensitivity-bound failure probability consumes only around 0.1% of the overall δ=10^-6 budget.The default setup uses r=0.5 and t=100; it varies ε across 4, 8, 16, and non-DP.Source: §A.1 · p. 17, Table 11 · p. 17

A.2 More Ablation Studies

  • With different embedding models, utility-privacy trends remain similar, and precision and recall nearly reach the non-DP baseline at ε≥8, though the protected and reconstructed texts differ.Table 7 compares transferability of observations, not which encoder is better.Source: §A.2 · p. 18
  • Larger projection dimensions generally improve F1 for finite ε by reducing sensitivity-bound failure probability, while the best k depends on ε.As t increases from 100 to 200, fewer buckets are released and utility shows no clear trend; the authors report feasibility at δ=10^-6 only for t≳100 at their subsampling rates.Source: §A.2 · p. 18, Table 13 · p. 18, Table 14 · p. 18

A.3 More on Text Utility

  • On TaylorAI, Fre-E2T output NLL approaches real-corpus NLL as the privacy budget increases.The evaluation reports median per-text NLL and the fraction of texts with NLL≤6, using GPT-2.Source: §A.3 · p. 18, Table 15 · p. 18

A.4 Evaluation on All Input Texts

  • Evaluating against all inputs leaves precision unchanged or higher but lowers recall by the infrequent-text mass, which Fre-E2T deliberately does not support.At ε=∞, TaylorAI recall falls from 0.97 on frequent texts to 0.41 on all inputs, where 66% are infrequent.Source: §A.4 · pp. 18–19, Table 16 · p. 19

B Details of Distributed Fre-E2T

  • The distributed protocol uses pseudorandom tags and TSDLap padding to make sub-threshold count-of-counts differentially private; secure aggregation combines locally quantized, noised vectors.The appendix says fine quantization yields utility almost the same as directly perturbing the sum with continuous Gaussian noise.Source: B Details of Distributed Fre-E2T · p. 19
  • The distributed discrete Gaussian mechanism gives the aggregated embedding sum a ρ_agg-CDP and (ε_agg,δ_agg)-DP guarantee.The centroid divides the perturbed sum by the released sampled count; the division is post-processing and incurs no additional privacy cost.Source: B Details of Distributed Fre-E2T · pp. 19–20

B.1 Deployment Costs

The deployment-cost comparison finds that Fre-E2T asks users to participate once, while Aug-PE requires repeated synchronous participation. The reported timings quantify this difference under the stated hardware and dataset conditions.

B.1 Deployment Costs

  • Aug-PE takes 21.7 minutes for a full run under the reported setup, requiring synchronous user updates and continuous participation, much longer than Fre-E2T.With N_syn=3000, L=7, and T=20, one Aug-PE iteration takes 64.6 seconds on an H100.Source: §B.1 · p. 20
  • A Fre-E2T user spends around 0.4 ms online, uploads 8.3 kB, and downloads 6.1 kB; its user-side cost is paid once, independent of iteration count and candidate-pool size.Costs were measured on an AMD EPYC 9554 and NVIDIA H100 using TaylorAI, with ε=2, k=20, and δ=10^-6.Source: §B.1 · p. 20, Table 17 · p. 20

C Proof for Semantic Support Protection

The proof argues that a heavy bucket containing an infrequent text is unlikely to have a centroid near that text, and that DP noise further increases the separation. The resulting guarantee concerns embedding-space distance; text-level protection also depends on inversion error.

C Proof for Semantic Support Protection

  • Conditioned on the proof's good event, most bucket points are at least r from x*, making the centroid's distance from x* dominated by those far points.The stated count is at least ℎ−2p_s n* far points in a bucket of count ℎ.Source: C Proof for Semantic Support Protection · pp. 21–22
  • The theorem's embedding-space guarantee does not by itself establish text-level protection: that requires quantifying the error when inverting a centroid to text.The authors report empirical observations suggesting inversion error is not large and text-level SSP is preserved.Source: C Proof for Semantic Support Protection · p. 22
  • For the distributed implementation, the authors state that semantic support protection is similar to the continuous-Gaussian conclusion after an algebraic substitution.The discussion describes discrete Gaussian noise and relates its squared-distance distribution to a noncentral chi-squared approximation.Source: C Proof for Semantic Support Protection · p. 22
  • For an infrequent x*, the proof bounds the probability that a released DP centroid lies within ψr of x* when the bucket contains ℎ subsampled items.The argument first limits close neighbors in a small-diameter bucket, then bounds centroid distance before and after DP noise.Source: C Proof for Semantic Support Protection · pp. 20, 22

D Extensions

The extension discusses privacy when each user contributes multiple data points, contrasting naive composition and group-DP approaches with a more tailored analysis. It also describes how the heavy-hitter and centroid privacy parameters scale with group size.

D Extensions

  • The naive composition approach limits each user to at most one embedding per bucket and multiplies ε and δ by the per-user bucket cap c.The authors identify choosing an optimal c as a possible future direction.Source: §D.0.1 · p. 22
  • A black-box group-DP argument for users with at most m data points yields parameters that can grow by a factor involving e^(mε)−1.The passage notes this factor can be very large when ε is not close to zero.Source: §D.0.1 · p. 22

D.0.1 Each User Has Multiple Data Points.

  • In the bespoke heavy-hitter analysis, changing l copies of the same index multiplies ε_HH by l, while δ_HH is bounded using a union bound.For l=1, the stated δ_1 expression matches the earlier sample-and-threshold result; δ_l increases with l.Source: §D.0.1 · p. 23
  • When all l data points fall in one cluster, centroid sensitivity and its failure probability scale by l, so the single-record analysis can be applied with sensitivity multiplied by l.The resulting parameters are denoted ε_agg,l and δ_agg,l.Source: §D.0.1 · p. 23
  • The discussion also sets out the bounded-DP neighboring relation, where datasets differ by altering one record rather than adding or removing one.The authors note this includes the scenario where a user's record is zeroed out.Source: §D.0.2 · p. 23

D.0.2 Bounded Differential Privacy.

The section converts unbounded-DP guarantees to bounded adjacency and notes how the conversion can be applied. It also describes a malicious-user threat to heavy-hitter privacy and a mitigation.

D.0.2 Bounded Differential Privacy.

  • Unbounded adjacency allows adding or removing one record, whereas bounded adjacency compares equal-sized datasets differing in one record.Source: §D.0.2 · p. 23
  • (2ε, (1 + e^ε)δ)-DP under bounded adjacency follows from (ε,δ)-DP under unbounded adjacency.The proof relates bounded-adjacent datasets through a shared dataset by removing one record and adding another.Source: §D.0.2 · p. 23
  • The black-box conversion lets the privacy parameters from Section D.0.1 yield corresponding guarantees under bounded adjacency.Source: §D.0.2 · p. 23
  • Malicious users submitting targeted indices can lower the heavy-hitter cutoff from τ to τ−n_mal; enforcing random submissions with MPC addresses this attack.The authors leave further defenses against such malicious acts to future work.Source: §D.0.3 · p. 24

D.0.3 Other Threat Models.

The security sketch analyzes a distributed implementation under stated cryptographic, channel, and adversary assumptions. It argues that the protocol reveals no information beyond the ideal released objects and specified leakage, so end-to-end DP reduces to the ideal release’s privacy.

E Simulation-Based Security Sketch

  • The model considers static semi-honest adversaries corrupting either server or a subset of users, assumes the servers do not collude, and models anonymous submissions with an ideal shuffler.User–server collusion is excluded from the main statement; allowing it would add corrupted users’ VOPRF-tag multiplicities to leakage.Source: E Simulation-Based Security Sketch · p. 24
  • The ideal functionality runs embedding, bucketing, sampled heavy-hitter identification, and quantized centroid release, while specifying leakage to each server.The synthesis server’s leakage includes sub-threshold count-of-counts; the tagging server’s includes VOPRF invocation count and a public heavy-tag oracle.Source: E Simulation-Based Security Sketch · p. 24
  • The hybrid proof replaces VOPRF interactions with ideal calls, user channels with anonymous shuffling, and secret-shared aggregation with ideal tagged sums.The synthesis server learns multisets rather than sender identities or cross-phase links, and individual shares are independent of users’ vectors.Source: E Simulation-Based Security Sketch · pp. 24–25
  • After the replacements, the transcript is computationally indistinguishable from one generated using corrupted parties’ inputs and randomness, public output, and ideal leakage.The security statement assumes secure VOPRF, anonymous shuffling, and aggregation that reveals only sums for released tags.Source: E Simulation-Based Security Sketch · pp. 24–25
  • The implementation reveals no raw texts, bucket indices, or individual embeddings beyond the ideal released objects, making end-to-end privacy reduce to the ideal release.The DP analysis composes the distributed heavy-hitter and discrete-Gaussian centroid steps with a high-probability sensitivity term.Source: E Simulation-Based Security Sketch · p. 25

Related papers

Loading 2609.10104v2…