betaFeedback

Reading v1View latest version

WorksComputer Science

Distributed and Private Textual Data Synthesis from Embeddings

Abstract

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.

Introduction

Users generate massive volumes of text on their devices [8, 9, 22, 26, 29, 52, 62, 92, 116]. These texts contain valuable insights into user needs and preferences as well as failure modes of deployed systems. However, collecting and analyzing raw user text poses significant privacy risks [10, 11, 25, 38, 54, 93, 99] as texts inherently contain sensitive information.

Differentially private (DP) text synthesis [49, 68, 96] is a promising approach to obtain population-level insights from user texts. DP [41] offers a robust, worst-case privacy guarantee for individual data against strong adversaries. In the ideal workflow, one releases a synthetic textual dataset generated under DP; the synthetic data can then be used for diverse downstream tasks such as data mining or model training without incurring additional privacy risks [74, ?, 113].

Most existing DP text synthesis methods are proposed in the centralized setting and typically adopt the following paradigms: (i) DP fine-tuning: Fine-tuning a generative language model (LM) with DP-SGD [1] or its variants on private texts, then sample synthetic texts from the fine-tuned model [19, 46, 113]; (ii) API-based private evolution: Iteratively refining synthetic text candidates generated from public LLM APIs using feedbacks from private texts [31, 110]. Such paradigms suffer from four main drawbacks.

(1) Trusted curator assumption. These approaches are designed for settings with a trusted curator that holds the full dataset [19, 31, 46, 110, 113]. In practice, user texts are often distributed and users may not trust a centralized curator with their sensitive data, as evidenced by recent data misuse and technical failures [11, 93].

(2) Repeated user participation in distributed deployments. When private texts originate from cross-device populations, straightforward deployments of iterative synthesis pipelines become multi-round protocols that require repeated user participation and synchronization [47, 55, 56, 110]. Such interactions are often misaligned with cross-device reality, where device availability is intermittent and communication is expensive [20, 70, 73, 83]. These constraints are worsened under DP due to the need for sufficient participation per round to offset noise and maintain utility [36, 65].

(3) Expensive computation and restrictive assumptions. DP fine-tuning methods require access to gradients (and often to model parameters) [19, 46, 47, 56, 113], whereas many capable models are available only through APIs. Even when gradients are available, DP fine-tuning can be prohibitively costly due to gradient computation and communication [57, 61, 65, 74, 75, 101, 112]. On the other hand, even though API-based private evolution methods do not compute gradients, they can still be costly—e.g., Aug-PE [110] generates thousands of candidate texts per iteration and broadcasts them to every participating user, who must compute nearest-neighbour distances in an embedding space and return a DP vote, blocking the next iteration, which can take hours across tens of iterations. Moreover, existing approaches often rely on publicly available labels [110, 113] or metadata information for private texts, which are frequently unavailable or too expensive/sensitive to obtain.

(4) Limited protection. Finally, standard DP ensures on the plausible deniability of membership information [42, 109], but does not explicitly prevent outputs from lying near a particular infrequent user data in the embedding space. This can be undesirable, motivating an additional protection tailored to text synthesis.

Our Contributions

We address the aforementioned gaps through a holistic approach. We design a DP text synthesis algorithm tailored to the distributed setting, alongside a customized secure computation protocol.

Our algorithm constructs a DP summary via two steps without any costly model fine-tuning: (i) identifying frequent semantic regions in the embedding space, and (ii) summarising embeddings within those regions into a privacy-preserving aggregated embedding called DP centroids. This DP summary can be post-processed to produce synthetic texts without further privacy loss.

For step (i), we use the Johnson–Lindenstrauss projection followed by randomized grid bucketing as a one-shot, training-free distributed clustering, replacing the existing iterative pipelines. For step (ii), we derive a probabilistic sensitivity bound from data-independent randomness, which lets us calibrate DP noise to a high-probability radius inside each frequent bucket, with the failure event absorbed into the δ\delta term of the overall DP guarantee.

Beyond standard DP, we formalize semantic support protection. This privacy notion strengthens protection for semantically infrequent user texts by ensuring that, with a high probability, the algorithm output avoids regions near infrequent texts in the embedding space (see Section 2.2 for details). We provide theoretical analysis and empirical validation of this property. We emphasize that DP does not directly lead to/violate semantic support protection.

We develop a secure distributed implementation of our algorithm in Section 6. Our inherently distributed-friendly DP algorithm supports local computation and requires only two phases of user participation. At a high level, each user locally maps their text to an index via sequential embedding, projection, and partitioning, and then shares the encrypted index, with some probability. After users estimate the frequency of their texts, they perform secure, perturbed aggregation of text embeddings associated within the same heavy-hitting group of semantically similar embeddings. The resulting DP centroids enable subsequent text synthesis entirely offline while avoiding model fine-tuning, additional user participation, and further privacy cost. We summarize our contributions as follows.

(1) New DP algorithm. We propose a new training-free DP synthesis algorithm based on a DP summary in an embedding space.

(2) New privacy notion. We introduce semantic support protection, which complements DP by limiting proximity to semantically infrequent user texts in the embedding space, and provide theoretical and empirical evidence for this property.

(3) Distributed-friendly algorithm design. We show that the core computations of the algorithm are simple aggregations admitting an efficient distributed implementation with only two phases of user participation. We do not claim new cryptography protocols.

(4) High utility. We comprehensively evaluate our approach using four datasets, most of which are not associated with publicly available labels or metadata information. Our algorithm achieves utility comparable to the state-of-the-art centralized DP baseline, while offering superior flexibility for deployment in distributed environments and stronger protection for infrequent texts.

Problem Definition

We study differentially private text synthesis. Let V={vi}i=1NV = \{v_i\}_{i=1}^{N} be a dataset of NN texts in which viv_i is the single text held by user ii on their own device. Our goal is to release a high-utility synthetic textual dataset V~\widetilde{V} while protecting user-level privacy.

We target settings in which no single party may hold the raw texts: there is no trusted curator that collects user texts off-device.

Instead, we assume there are two servers that do not collude. We name the two servers based on their roles: (i) The tagging server StagS_{\mathrm{tag}} assists users in encoding their reports into a random identifier, so that equal inputs receive equal identifiers, without itself learning either the inputs or the identifier. (ii) The synthesis server SsynS_{\mathrm{syn}} receives the encoded user reports, which is then used to produce a DP summary of users, and derives the synthetic texts from it. Section 6.2 explains the two roles concretely.

Threat model. All parties, including both servers and all users, are honest-but-curious: they follow the protocol but may try to infer information about other users’ texts from their views. Neither server is trusted with any user’s text or embedding vector. A user communicates with servers in at most two short phases and never communicate with another user. We discuss potential extensions to malicious settings in Appendix D.

The servers StagS_{\mathrm{tag}} and SsynS_{\mathrm{syn}} do not collude. It is a common assumption in two-server deployments [12, 14, 18, 35, 64, 87, 98] which can be supported by separate operators or collusion cost due to legal and regulatory constraints [5, 60, 72]. Every message a user/server sends to a server/user is through an anonymizing proxy, which was also used in prior work [14, 16, 21, 43, 64, 98].

We assume that both users and servers have black-box access to an embedding model EE that maps a text to a dd-dimensional embedding vector, with dd fixed. In particular, EE maps semantically similar texts to nearby vectors. Access to such a semantics-preserving embedding model was also assumed in prior work [110].

We treat the raw private text viv_i as a whole piece of user information to protect. We do not assume any publicly available label information associated with viv_i that can be used for free, such as domain/category labels for user reviews [55, 56, 110, 113]. We also do not assume that there is a trained model that extracts metadata information of the user data [31], since such data may be sensitive and are not used for any model training.

Differential Privacy Requirement

Differential privacy (DP) [41] is commonly regarded as the gold privacy standard for data synthesis [2, 49, 68, 96].

Definition 1 (Differential Privacy [41]). Let MM be a randomized algorithm with output domain range⁡(M)\operatorname{range}(M). Then MM satisfies DP if, for any neighboring datasets VV and V′V', the probability distributions of M(V)M(V) and M(V′)M(V') are similar as quantified by ϵ\epsilon and δ\delta, i.e.,

max⁡O∈range⁡(M)Pr⁡[M(V)∈O]≤eϵ⋅Pr⁡[M(V′)∈O]+δ.(1)\max_{O \in\operatorname{range}(M)} \Pr[M(V) \in O] \le e^{\epsilon} \cdot\Pr[M(V') \in O] + \delta. \tag*{(1)}

Here, VV and V′V' are neighboring datasets if one can be obtained from the other by adding or deleting a single record (i.e., a single text).

DP provides plausible deniability for the membership of any user text: with or without it, the output distribution is similar. Smaller ϵ\epsilon and δ\delta correspond to stronger privacy protection; and vice versa. Every parameter of the DP mechanism we propose, including the randomness it used, is public unless otherwise stated. Such randomness is fixed before any user input and is known to the DP adversary. The probability of an unfavorable draw is absorbed into δ\delta.

Semantic Support Protection (SSP)

DP does not preclude the mechanism from emitting outputs that are close to a unique or rare user text in the embedding space. The output of a DP mechanism can appear close to an infrequent user text, which may violate user expectations and can be undesirable [3, 109]. This motivates us to consider an additional protection tailored to text synthesis, named semantic support protection. The aim is to prevent a DP mechanism from emitting outputs near semantically infrequent texts except with small probability. We first define semantically infrequent texts.

Definition 2 ((r,tr,t)-Semantically Infrequent). Given r>0r > 0 and positive integer tt, textual dataset VV, and embedding model EE, we say a data point v∗∈Vv^{*} \in V is (r,t)(r,t)-semantically infrequent (for VV and EE) if fewer than tt data points from VV are within distance rr of v∗v^{*} in the embedding space:

∣{j∈[N] such that ∥E(vj)−E(v∗)∥2≤r}∣<t.(2)\left|\left\{j \in[N]\ \text{such that}\ \lVert E(v_j)-E(v^{*})\rVert_2 \le r\right\}\right| < t . \tag*{(2)}

We denote the set of (r,t)(r,t)-semantically infrequent and frequent texts in VV as Vinfre(r,t)V_{\mathrm{infre}}(r,t) and V∖Vinfre(r,t)V \setminus V_{\mathrm{infre}}(r,t), respectively.

Definition 3 ((r,t,r∗,δ∗)r,t,r^{*},\delta^{*})-Semantic Support Protection). Let M\mathcal{M} be an (ε,δ)(\varepsilon,\delta)-DP mechanism that outputs a set of texts V~\widetilde{V}. We say that M\mathcal{M} satisfies (r,t,r∗,δ∗)(r,t,r^{*},\delta^{*})-semantic support protection (SSP) if for any (r,t)(r,t)-semantically infrequent v∗∈Vinfre(r,t)v^{*} \in V_{\mathrm{infre}}(r,t),

Pr⁡[∃v~∈V~ such that ∥E(v~)−E(v∗)∥2≤r∗]≤δ∗,(3)\Pr\left[\exists\widetilde{v} \in\widetilde{V}\ \text{such that}\ \lVert E(\widetilde{v})-E(v^{*})\rVert_2 \le r^{*}\right] \le\delta^{*}, \tag*{(3)}

where r∗>0r^{*} > 0, and δ∗∈(0,1)\delta^{*} \in(0,1) is the failure probability.

Difference from DP, LDP, and metric-DP. This definition provides an additional privacy layer beyond DP [41] and local DP [66] by explicitly limiting the probability that released outputs lie within radius r∗r^{*} of any semantically infrequent input in the embedding space. As we will see in Figure 4, a standard DP method for text synthesis such as Aug-PE [110] does not automatically achieve SSP. Indeed, DP or LDP permits events such as “the output lies close to an infrequent input text” to occur with non-negligible probability as long as the probability ratio under neighboring datasets is bounded. SSP explicitly complements this limitation. Metric-LDP [6, 45, 76, 84] guarantees that outputs cannot distinguish embeddings that are close in metric, such as the L2L_2 distance measured on the embedding space. Similar to DP and LDP, metric-LDP does not explicitly bound the probability of emitting a value near a rare user input.

Empirical semantic support protection plots for TaylorAI, Instructions-2M, LMSYS Chat, and Yelp

Figure 4. Empirical semantic support protection. Probability (lower is better) that an infrequent text has a neighbor among the synthetic texts within distance ψr\psi r where ψ\psi sweeps in [0.1,1.5][0.1, 1.5]. Lighter and darker colors show results on (r,t)(r,t)-infrequent texts with t=10t = 10 and t=100t = 100, respectively.

At first sight, requiring the released output to avoid a neighbourhood of an infrequent input v∗v^{*} may look like it could distinguish the dataset VV that contains v∗v^{*} from the neighbourhood V′=V∖{v∗}V' = V \setminus\{v^{*}\} that does not. The key observation is that: if v∗v^{*} is (r,t)(r,t)-infrequent in VV then it is at least (r,t−1)(r,t-1)-infrequent in V′V', and conversely a point that is infrequent under V′V' remains infrequent under VV. Definition 3 therefore applies to the same v∗v^{*} under both VV and V′V', and the neighbourhood location E(v∗)E(v^{*}) is never released.

Simplified definition. Setting r∗=rr^{*} = r, we obtain the following simplified SSP.

Definition 4 ((r,t,δ∗)r,t,\delta^{*})-Semantic Support Protection). Mechanism M\mathcal{M} satisfies (r,t,δ∗)(r,t,\delta^{*})-SSP if for any v∗∈Vinfre(r,t)v^{*} \in V_{\mathrm{infre}}(r,t),

Pr⁡[∃v~∈V~ such that ∥E(v~)−E(v∗)∥2≤r]≤δ∗.(4)\Pr\left[\exists\widetilde{v} \in\widetilde{V}\ \text{such that}\ \lVert E(\widetilde{v})-E(v^{*})\rVert_2 \le r\right] \le\delta^{*}. \tag*{(4)}

As we have mentioned in Section 1, DP text synthesis has been studied primarily in the centralized setting with a trusted curator holding the full private dataset [19, 31, 46, 78, 110, 113]. Adapting the existing paradigms to distributed settings has been explored in recent work, but existing solutions typically retain at least one of the following requirements: gradient/parameter access to an LM for training, publicly available labels/categories for private texts, or multi-round synchronized user and server participation. For example, methods that update or optimize models using user feedback, such as POPri [56] and federated DP fine-tuning variants [47], require gradient access and repeated rounds with tight synchronization between users and the server. Similarly, distributed adaptations of private evolution [55] require users to repeatedly process server-provided public candidates and return DP-perturbed signals in each round. Such designs can be difficult to scale in cross-device environments, where user availability is intermittent and communication is costly [20, 70, 73, 83], and these constraints are further amplified under DP due to the need for sufficient participation per round to offset noise [36, 65].

A complementary line of work directly perturbs token, sentence, or document embeddings under metric-LDP (also called dd-privacy), so that the indistinguishability guarantee scales with a distance in embedding space rather than being uniform across all pairs [45, 69, 82, 84]. We target the standard text-level (ε,δ)(\varepsilon,\delta)-DP rather than a distance-scaled guarantee.

Beyond formal DP mechanisms, recent works have explored privacy-preserving analysis of user text corpora via layered, non-DP protections. For example, Clio [104] uses LLM-based summarization and embedding-based clustering to surface aggregated usage patterns, and then applies multiple privacy layers such as PII-avoiding prompts and automated auditing to reduce exposure of private information. Clio focuses on the output utility rather than worst-case privacy guarantees such as DP, making it prone to attacks [7]. There are also some other work in the literature, e.g., secret protection [51, 108], privacy with respect to sensitive references [106], and control codes [117]. These methods often rely on assumptions about sensitive information and prior knowledge regarding the data distribution, and sometimes the computation power of an adversary.

Synthesizing Texts via Frequent Embeddings

We present our DP algorithm for synthesizing texts, named Fre-E2T. Fre-E2T achieves formal differential privacy guarantees for individual texts (Definition 1) and also provide semantic support protection for infrequent texts (Definition 3). Section 6 gives the two-server protocol that realizes the functionality of Fre-E2T under the threat model introduced in Section 2.

To reduce the number of traversals on input and therefore enable a lightweight distributed implementation, we first sketch the user texts as a summary, and then synthesize texts from the summary.

Clustering embedding vectors. A canonical method for summarizing data is clustering [79, 81, 111]. In clustering, similar data points are grouped together based on some measure. Such a group of data points is referred to as a cluster. The goal of clustering is to find representative structures to summarize the input dataset. A common approach for accomplishing that is to ensure that each input data point lies within a ball of some radius centered at a centroid, the Euclidean average of all points within the same cluster. We could apply this approach to text embeddings and obtain cluster centroids for input texts.

Inverting embeddings to texts. For each centroid (a vector in Rd\mathbb{R}^{d}), we can then use a function/model that inverts embedding vectors into textual data [80, 88] to generate high-utility synthetic texts. Intuitively, if each centroid is near some data points, then the texts synthesized from the centroid should also bear similarity to the original texts corresponding to those data points.

Technical Challenges. Existing DP clustering methods generally rely on an iterative approach to refine centroids, based on their distances from each data point xix_i: each iteration traverses the whole dataset in order to evaluate the distances from each data point to all the centroids, followed by updating the centroids to maximize the overall utility [17, 90, 94, 100]. To build a more distributed-friendly algorithm, we avoid such iterative updates and computing pairwise distances between data points, which would require user-user communication in the distributed setting. Furthermore, when computing the centroid for each cluster, standard worst-case DP analysis [1] requires an additive random noise whose scale is proportional to the maximum norm of any data point, which is not ideal. Intuitively, we should be able to utilize the structural information of clusters to reduce the amount of noise needed for DP.

The Complete Algorithm

Our algorithm named Fre-E2T (Frequent Embedding to Text) consists of four sequential steps, presented as Algorithm 1 and Figure 1.

Overall idea of Fre-E2T, illustrated in the centralized setting.

Figure 1. Overall idea of Fre-E2T, illustrated in the centralized setting.

Step 1: Projection and Partitioning. We first obtain the embedding vector xi∈Rdx_i \in\mathbb{R}^{d} for each text. Each embedding vector xi=E(vi)∈Rdx_i = E(v_i) \in\mathbb{R}^{d} is obtained via an embedding function EE. The entire matrix of embedding vectors is written as X∈RN×dX \in\mathbb{R}^{N \times d}. Next, we project each vector to Rk\mathbb{R}^{k}, by computing yi=1kxiZ∈Rky_i = \frac{1}{\sqrt{k}}x_iZ \in\mathbb{R}^{k}. Here, ZZ is a random Rd×k\mathbb{R}^{d \times k} matrix where each entry is sampled independently from the standard Gaussian distribution. Pairwise L2L_2 distances are preserved up to a small multiplicative distortion with high probability for Gaussian projectors, when kk is large enough, by the Johnson Lindenstrauss Lemma [33, 63]. In other words, two records are close in Rk\mathbb{R}^{k} if and only if their originals are close in Rd\mathbb{R}^{d}. As a result, data points with a high support in their neighborhood in Rd\mathbb{R}^{d} will still have a high support in Rk\mathbb{R}^{k}. The Euclidean average of data points in the same cluster can thus serve as a good representation of them and frequent texts will be placed in a cluster with many close neighbors.

To group nearby projected points without computing all pairwise distances, we partition the kk-dimensional space into “buckets.” To do that, we first discretize Rk\mathbb{R}^{k} with a randomly shifted grid of edge length L>0L > 0. In particular, for each coordinate j∈{1,…,k}j \in\{1,\ldots,k\}, a public random offset ojo_j is sampled from Unif⁡[0,L)\operatorname{Unif}[0,L). The grid boundaries are placed at oj+mLo_j + mL for all m∈Zm \in\mathbb{Z}. The kk-dimensional bucket index for user ii is the integer vector bi=(bi,1,…,bi,k)b_i = (b_{i,1},\ldots,b_{i,k}), with bi,j=⌊yi,j−ojL⌋∈Zb_{i,j} = \left\lfloor\frac{y_{i,j}-o_j}{L} \right\rfloor\in\mathbb{Z}. We refer to Figure 6 for an illustration. bib_i is then randomly permuted to obtain hih_i. Vectors that are close to each other in Rk\mathbb{R}^{k} are likely to end up with the same index before and after the permutation; and vice versa [34, 53, 59].

Partitioning the k-dimensional space with a fixed edge length L and random offsets

Figure 6. Partitioning the kk-dimensional space with a fixed edge length LL and random offsets.

The edge length LL is fixed a priori as a public design parameter of the protocol. Choosing LL controls the granularity of the partitioning and clustering: a smaller LL yields finer buckets, making it less likely that two nearby points fall into the same bucket (thus producing more, smaller clusters), while a larger LL coarsens the grid and increases the probability that points which are potentially farther apart in Rd\mathbb{R}^{d} collide in the same kk-dimensional bucket. As we will see later, LL also influences the privacy guarantees. Consequently, the appropriate choice of LL is application-dependent and should be guided by the desired trade-off between resolution and the privacy protection for user texts.

Step 2: DP heavy hitters. With the buckets assigned, we then count the number of data points in each bucket. For each data point, we flip a coin to decide whether it contributes to the corresponding bucket and filter out buckets with counts <τ< \tau. This sample-and-threshold process separates heavy-hitting bucket indices from those that have not accumulated enough counts while introducing enough randomness to ensure DP [15] and also has an efficient distributed implementation [98]. Our design has avoided injecting random noises to each user’s embedding vector directly as in local DP [44, 66], which would introduce a large perturbation to the results, compromising utility.

Step 3: DP Centroid computation. Now that we have identified the “heavy-hitting buckets”, we can then compute the average of the original data points within each of these buckets in Rd\mathbb{R}^{d}. In particular, each text that has contributed to a heavy-hitting bucket index (with coini=1_i = 1) contributes to the vector sum; those that are not sampled during the last step are not counted. Additive random Gaussian noise is injected to the sum. For DP analysis, we avoid considering the worst-case sensitivity of the vector sum, which is the radius of the whole dd-dimensional space. Instead, we rely on the crucial property that only data points that are close to each other can reside in the same cluster, except with a small error probability. Therefore, we only need to inject DP noise that is proportional to the radius of the cluster rather than the whole space.

Step 4: Embedding to text conversions. Finally, from the centroids of each heavy-hitting bucket, we invert it to obtain synthesized texts. DP is preserved under post-processing [41].

Algorithm 1: Fre-E2T

Input: Text entries {v1,…,vN}\{v_1,\ldots,v_N\}; embedding function EE; random projection matrix ZZ; bucket edge length LL; random offsets {oj}j=1k\{o_j\}_{j=1}^{k}; random hash function HH; subsampling rate psp_s; threshold τ\tau; noise scale σ\sigma.

  1. Initialize B←∅\mathcal{B}\leftarrow\varnothing, S←∅S\leftarrow\varnothing, O←∅\mathcal{O}\leftarrow\varnothing

  2. Projection and Partitioning

  3. for i=1,…,Ni=1,\ldots,N do

  4. Compute embedding xi←E(vi)∈Rdx_i\leftarrow E(v_i)\in\mathbb{R}^{d}

  5. Compute projection yi←1kxiZ∈Rky_i\leftarrow\frac{1}{\sqrt{k}}x_iZ\in\mathbb{R}^{k}

  6. Identify bucket index bib_i based on yiy_i, {oj}j=1k\{o_j\}_{j=1}^{k}, LL

  7. Randomly permute hi=H(bi)h_i=H(b_i).

  8. DP Heavy Hitters

  9. for i=1,…,Ni=1,\ldots,N do

  10. if coin⁡i∼Bernoulli⁡(ps)\operatorname{coin}_i\sim\operatorname{Bernoulli}(p_s) is 1 then

  11. Add xix_i to bucket B[hi]\mathcal{B}[h_i]

  12. for each bucket index hh in B\mathcal{B} do

  13. Count nh=∣B[h]∣n_h=|\mathcal{B}[h]|

  14. if nh<τn_h<\tau then

  15. Remove bucket index hh from B\mathcal{B}

  16. DP Centroid Computation

  17. for each bucket index hh in B\mathcal{B} do

  18. Compute sum Sh←∑xi∈B[h](coin⁡i⋅xi)S_h\leftarrow\sum_{x_i\in\mathcal{B}[h]}(\operatorname{coin}_i\cdot x_i)

  19. Compute μ^h←1nh(Sh+N(0,σ2Id))\hat{\mu}_h\leftarrow\frac{1}{n_h}(S_h+\mathcal{N}(0,\sigma^2I_d))

  20. Add μ^h\hat{\mu}_h to SS

  21. Embedding to Text Conversion

  22. for each centroid μ^h\hat{\mu}_h in SS do

  23. Synthesize text v~h←Invert⁡(μ^h)\tilde{v}_h\leftarrow\operatorname{Invert}(\hat{\mu}_h)

  24. Output v~h\tilde{v}_h

Privacy Analysis

Differential Privacy Guarantees

Privacy loss comes from two components, identifying heavy hitting buckets and computing the centroid within each heavy hitting bucket. Without loss of generality, we work on the matrix of embedding vectors, written as XX. The ii-th row of XX is associated with text ii. We consider a neighboring input X′X' such that XX has an additional embedding vector xx. We condition on the event that inputs XX and X′X' work with the same projection matrix ZZ and the same hash function HH. We let the permuted bucket index of xx be hh.

Heavy Hitters. For the truncated heavy hitter histogram, it suffices to analyze the count of index hh, when it reaches threshold τ\tau.

Lemma 1 (Sample-and-threshold privacy [15]). With q:=1−(1−ps)exp⁡(−εfre)q:=1-(1-p_s)\exp(-\varepsilon_{\mathrm{fre}}) and D(q∥p):=qlog⁡qp+(1−q)log⁡1−q1−pD(q\mathbin\Vert p):=q\log\frac{q}{p}+(1-q)\log\frac{1-q}{1-p}, the heavy hitter histogram {(h,nh)}\{(h,n_h)\} in Alg. 1 satisfies (εfre,δfre)(\varepsilon_{\mathrm{fre}},\delta_{\mathrm{fre}})-DP with

εfre≤log⁡11−ps,δfre≤exp⁡(−τq⋅D(q∥ps)).(5)\varepsilon_{\mathrm{fre}}\le\log\frac{1}{1-p_s},\qquad\delta_{\mathrm{fre}}\le\exp\left(-\frac{\tau}{q}\cdot D(q\mathbin\Vert p_s)\right). \tag*{(5)}

The sum of all random contributions of XX, denoted as nhn_h, therefore follows the Bernoulli distribution Bin⁡(Nh,ps)\operatorname{Bin}(N_h,p_s), where NhN_h is the overall number of users with index hh. For its neighboring dataset, this distribution becomes Bin⁡(Nh−1,ps)\operatorname{Bin}(N_h-1,p_s). Lemma 1 bounds this divergence, with a high probability.

Choosing τ\tau. The threshold τ\tau is a public parameter that controls which buckets are declared heavy hitters. We set τ=ps⋅t\tau=p_s\cdot t, so that in expectation a bucket with strictly fewer than tt neighbors within distance rr contributes at most pstp_st sampled submissions and is therefore filtered out. Larger τ\tau leads to fewer heavy hitting buckets and smaller δfre\delta_{\mathrm{fre}} via Lemma 1.

Heavy Hitting Indices. The indices of heavy hitters correspond to frequent embedding vectors. These indices are conceptually close to labels of user texts (e.g., “Texas barbecue joints”), which were utilized in prior works [110, 113]. In our setting, such information is not publicly available beforehand. Here, the index of a heavy-hitting bucket index is conceptually similar and obtained in a privacy-preserving manner, albeit being less informative (since we cannot interpret the indices themselves).

Computing Centroids. Again, we consider any bucket hh with count nh≥τn_h\ge\tau. There are two cases. If the additional data point in XX, denoted as xx, is not added to the bucket (due to the zero outcome of the coin flip), then the privacy cost is 0. Otherwise, we need to analyze the privacy cost for releasing the sum of embedding vectors perturbed by the Gaussian noise. To do that, we need to first analyze the sensitivity of the sum of embedding vectors.

The worst-case L2L_2 sensitivity of a bucket’s embedding sum is the largest embedding norm, which is unbounded; adding noise scaled to it would destroy all utility. We instead use a probabilistic bound whose failure probability is paid in the final δ\delta.

Lemma 2 (High-probability Sensitivity). Consider any bucket in the kk-dimensional projection space, with bucket edge length LL. It holds that the sensitivity for the sum of embedding vectors within the bucket is bounded by Δdist\Delta_{\mathrm{dist}}, with probability

Pr⁡[succeed]≥1−(f(kLΔdist))k,(6)\Pr[\mathrm{succeed}]\ge1-\left(f\left(\frac{\sqrt{k}L}{\Delta_{\mathrm{dist}}}\right)\right)^k, \tag*{(6)}
with f(v):=erf⁡(v2)−2π1v(1−e−v2/2).(7)\text{with } f(v):=\operatorname{erf}\left(\frac{v}{\sqrt{2}}\right)-\sqrt{\frac{2}{\pi}}\frac{1}{v}\left(1-e^{-v^2/2}\right). \tag*{(7)}

We choose the sensitivity bound Δdist\Delta_{\mathrm{dist}} so that the coupled pair violates it has a small, negligible probability. Conditioned on its complement, Theorem 3 applies with sensitivity Δdist\Delta_{\mathrm{dist}}. Our default experiment setting with k=20k=20, L=2r/kL=2r/\sqrt{k}, and Δdist=2r\Delta_{\mathrm{dist}}=2r (for any r>0r>0) gives 8.9×10−118.9\times10^{-11}, a negligible share of the overall δ=10−6\delta=10^{-6}.

Proof sketch of Lemma 2. Consider neighboring inputs X′=X∪{x}X'=X\cup\{x\} and condition on the added point being assigned to bucket hh. The sampled contributions to hh under XX and X′X' can be coupled so that they differ in a single replaced point x′x' that is assigned to the same bucket hh. The sum over bucket hh therefore changes by at most ∥x−x′∥2\lVert x-x'\rVert_2 for two points x,x′x,x' that collide in all kk projected coordinates, and it suffices to bound the distance of same-bucket collisions. Let D=∥x−x′∥2D=\lVert x-x'\rVert_2. Each projection coordinate is yj=⟨x,Zj⟩/ky_j=\langle x,Z_j\rangle/\sqrt{k} with independent Zj∼N(0,Id)Z_j\sim\mathcal{N}(0,I_d), so the coordinate-wise gap gj=yj−yj′g_j=y_j-y'_j is i.i.d. N(0,D2/k)\mathcal{N}(0,D^2/k). Buckets have edge length LL per coordinate with an independent uniform random offset, so two points with gap gjg_j share a cell in coordinate jj with probability

{#eq:8}

max(0,1−∣gj∣/L)(0,1-|g_j|/L). Taking the expectation over gjg_j gives the per-coordinate collision probability and independence across the kk coordinates yields the statement. □

Theorem 3 (Gaussian mechanism). Let Δdist\Delta_{dist} be the L2\mathcal{L}_2 sensitivity for the vector sum and σ\sigma be the parameter of the Gaussian noise. The centroids {μh}\{\mu_h\} in Alg. 1 satisfies ρagg\rho_{agg}-CDP, and (εagg,δagg)(\varepsilon_{agg},\delta_{agg})-DP with

ρagg=Δdist22σ2,andδagg=inf⁡α∈(1,∞)e(α−1)(αρagg−εagg)α−1⋅(1−1α)α(8)\rho_{agg}=\frac{\Delta_{dist}^{2}}{2\sigma^{2}},\quad\text{and}\quad\delta_{agg}=\inf_{\alpha\in(1,\infty)}\frac{e^{(\alpha-1)(\alpha\rho_{agg}-\varepsilon_{agg})}}{\alpha-1}\cdot\left(1-\frac{1}{\alpha}\right)^{\alpha} \tag*{(8)}

The overall DP guarantee comes from linear composition [42], and accounting for failure probability of sensitivity bound into δ\delta.

Theorem 4 (Overall DP guarantee). With L2\mathcal{L}_2 sensitivity Δdist\Delta_{dist}, ff defined as in (7), and the parameters εfre,εagg,δfre,δagg\varepsilon_{fre},\varepsilon_{agg},\delta_{fre},\delta_{agg} computed as in Lemma 1 and Theorem 3, Algorithm 2 satisfies (ε,δ)(\varepsilon,\delta)-DP for

ε=εfre+εagg,andδ=δfre+δagg+(f(kLΔdist))k(9)\varepsilon=\varepsilon_{fre}+\varepsilon_{agg},\quad\text{and}\quad\delta=\delta_{fre}+\delta_{agg}+\left(f\left(\frac{\sqrt{kL}}{\Delta_{dist}}\right)\right)^k \tag*{(9)}

Semantic Support Protection

For any infrequent user embedding x∗x^*, there will not be any DP centroid μ^\hat{\mu} such that μ^\hat{\mu} is close to x∗x^* in terms of L2\mathcal{L}_2 distance.

Theorem 5 (SSP by Alg. 1). For any x∗∈Xx^* \in X such that there are at most tt data points from XX that has distance at most rr to x∗x^* in XX and any DP centroid μ^\hat{\mu} with hh items subsampled into the cluster, we have ∥μ^−x∗∥2<ψr\|\hat{\mu}-x^*\|_2<\psi r with probability

δ∗≤(h2)(f(kLr))k+e−0.38pst+Fχd2(Λ)(ψ2r2h2σ2)(10)\delta^*\leq\binom{h}{2}\left(f\left(\frac{\sqrt{kL}}{r}\right)\right)^k+e^{-0.38p_st}+F_{\chi_d^2(\Lambda)}\left(\frac{\psi^2r^2h^2}{\sigma^2}\right) \tag*{(10)}

where Λ=τ−6pst2τr\Lambda=\frac{\tau-6p_st}{2\tau}r, and FF is the cumulative density function (cdf) of noncentral chi-squared distribution

Fχd2(Λ)(a)=e−Λ/2∑j=0∞(Λ/2)jj!γ(d2+j,a2)Γ(d2+j),a≥0,withF_{\chi_d^2(\Lambda)}(a)=e^{-\Lambda/2}\sum_{j=0}^{\infty}\frac{(\Lambda/2)^j}{j!}\frac{\gamma\left(\frac{d}{2}+j,\frac{a}{2}\right)}{\Gamma\left(\frac{d}{2}+j\right)},\quad a\geq0,\quad\text{with}
γ(s,a)=∫0ats−1e−t dt,Γ(s)=∫0∞ts−1e−t dt, s>0.\gamma(s,a)=\int_0^a t^{s-1}e^{-t}\,dt,\quad\Gamma(s)=\int_0^\infty t^{s-1}e^{-t}\,dt,\ s>0.

Namely, Algorithm 1 satisfies (r,t,ψr,δ∗)(r,t,\psi r,\delta^*) semantic support protection for the DP centroids. This δ∗\delta^* quickly converges to 0 as kk, and tt increases, when σ\sigma, ψ\psi, and psp_s are moderate and L≈rkL\approx\frac{r}{\sqrt{k}} times some constant. We include text-level evaluation in Section 7, where additional error may come from the vector-to-text inversion process.

We sketch the proof (detailed in Appendix C). We condition on the high-probability good event “Within any bucket, there are at most 2pst2p_st data points that are rr close to x∗x^* and every two data points have distance at most rr”. This can be proved using the fact that we cluster data points based on the L2\mathcal{L}_2 distance together with a concentration argument [86]. Next, we can argue that for any DP centroid in Alg. 1, the corresponding cluster has many data points that are far from x∗x^* and these “far data points” are close to each other. Based on this, we can argue that the average of all data points’ embedding vectors in this cluster is far from x∗x^*, since the average is dominated by the majority data points that are far from x∗x^*. Finally,

injecting random DP noise to the centroid will not decrease its distance to x∗x^* by a significant margin. Note that we do not claim that existing solutions such as [110, 113] do not achieve similar guarantees. Nevertheless, working directly on the embedding space with explicit truncation for infrequent texts has made the proof easier.

Distributed Implementation

Algorithm 2 implements Algorithm 1 in the distributed environment, with threat model specified as in Section 2. We refer to Figure 5 in Appendix B for an illustration.

Overall idea of the algorithm in the distributed setting

Figure 5. Overall idea of our algorithm in the distributed setting.

The implementation mainly makes use of three existing distributed protocols: (i) Verifiable oblivious pseudorandom function (VOPRF) [35]; (ii) distributed discrete Gaussian with secure aggregation (SecAgg) [21, 64] for differential privacy; and (iii) a standard shuffler-style channel that strips per-user identifiers from messages [16, 30, 35, 98]. We treat each of these as a black-box with the security guarantees inherited from the original papers.

Step 1: Local pre-processing. The local data pre-processing step is identical to the centralized setting, assuming that all users have access to the same embedding function EE and the same public randomness. In the end of this step, each user ii obtains a kk-dimensional bucket index bib_i for its embedded vector xix_i (line 8 of Algorithm 2).

Step 2: Distributed heavy hitter estimation. There is no trusted curator to directly process the bucket indices for finding heavy hitters. Instead, each user ii obliviously communicates with the tagging server to encrypt index bib_i into a random string hih_i (line 3 of Algorithm 2). User ii then flips a coin to decide whether to submit the encrypted string hih_i to the synthesis server (lines 4–6 of Algorithm 2). The synthesis server collects the encrypted indices from the users and computes a heavy-hitter histogram to identify frequent indices (lines 7–9 of Algorithm 2).

Step 3: Aggregation of frequent text embeddings. The synthesis server broadcasts the frequent encrypted indices to all users (line 10 of Algorithm 2). Every user who shares the same encrypted index and has submitted the index in the last phase proceeds to securely aggregate their original data embedding vectors in the dd-dimensional space with additive DP noise (lines 11–15 of Algorithm 2), obtaining a DP average for embedding vectors (i.e., a DP centroid for the cluster). For this phase, we need the two non-colluding servers, tagging server StagS_{tag} and synthesis server SsynS_{syn}. The two servers can then combine their secret shares to reconstruct the noisy private centroid for each heavy hitting index (lines 16–19 of Algorithm 2). Note that only users who already submitted the encrypted index in Step 2 respond to the Step 3 broadcast for that index. The synthesis server therefore observes that “some set of ≥τ\geq\tau anonymized endpoints share encrypted index hih_i”, which is exactly the heavy-hitter event whose existence is already covered by the DP guarantee in Lemma 1.

Step 4: Offline post-processing. Finally, the synthesis server uses each perturbed centroid to synthesize new textual data by inverting it back to a token sequence using the Vec2Text algorithm [89]. This is post-processing and does not cost additional privacy budget.

Paraphrasing. In addition, one can also use open-sourced language models such as GPT-2 [95] to paraphrase the generated texts to improve the diversity of the generated texts—e.g., 10 times for each text inverted from a centroid. Inversion and paraphrasing steps

Algorithm 2: Differentially text synthesis (distributed version of Fre-E2T)
Input: $N$ users, each one of which holds a private textual data point $v_i$; public embedding function $E$; embedding dimension $d$; projected dimension $k$; public Gaussian matrix $Z \in \mathbb{R}^{d \times k}$; edge length $L$; public offsets $\{o_j\}_{j=1}^{k}$; tagging server $S_{\mathrm{tag}}$; synthesis server $S_{\mathrm{syn}}$; subsampling rate $p_s$; truncated shifted Laplace distribution $\operatorname{TSDLap}(\lambda,\gamma)$; heavy-hitter threshold $\tau$; Discrete Gaussian noise std $\sigma$ and quantization granularity $\beta$.
Output: Synthesized texts.
1 for User $i = 1,\ldots,N$ do
2 Compute the $k$-dimensional bucket index $b_i$ for $v_i$ using Local-Preprocess$(v_i)$ // done locally
3 Obtain $h_i$ using User-TaggingServer$(b_i)$ // interacting with the Tagging Server
4 Sample $\operatorname{coin}_i \in \{0,1\}$ with $p_s$ probability of 1 // done locally
5 if $\operatorname{coin}_i = 1$ then
6 Submit index $h_i$ to the synthesis Server
7 Dummy = Dummy-Data-Creation$(\tau,\operatorname{TSDLap}(\lambda,\gamma))$
8 Synthesis server receives ReceivedData = sampled$\{h_i\} \cup$ Dummy
9 Synthesis server filters out indices with counts smaller than $\tau$, obtaining index set $\mathcal{H}$ and corresponding counts $C$
10 Synthesis server broadcasts $\mathcal{H}$ and $C$ to all users
11 for User $i = 1,\ldots,N$ do
12 if $\operatorname{coin}_i = 1$ then
13 if $h_i \in \mathcal{H}$ then
14 Obtain $\tilde{x}_i = \operatorname{Discrete\text{-}Gaussian}(x_i,\sigma,\beta)$ // Locally perturb the embedding vector
15 Compute two secret shares $\tilde{x}_i[1]$ and $\tilde{x}_i[2]$ for $\tilde{x}_i$ and send to tagging server and synthesis server, respectively
16 for $h \in \mathcal{H}$ do
17 Tagging server and synthesis server reconstruct $\hat{x}^{(h)} = \frac{1}{\beta}\sum \tilde{x}_i$ with index $h$ $\tilde{x}_i$
18 Synthesis server computes centroid $\hat{x}^{(h)} \leftarrow \frac{1}{c^{(h)}}\cdot\hat{x}^{(h)}$ // $c^{(h)}$ is the count of index $h$
19 Generate text $\tilde{v}_h \leftarrow \operatorname{Invert}(\hat{x}_h)$
20 Output $\tilde{v}_h$

require no further involvement from the users and can be done completely offline on the server side. In addition, assuming that the language model used for paraphrasing is not trained on the user texts, this paraphrasing step also incurs no additional privacy cost. Step 1 and 4 are done completely on the user and server side, respectively. Next, we discuss the distributed Step 2 and 3 in details.

Distributed Heavy Hitter Estimation

The idea is similar to the recent Nebula system [98] for distributed heavy hitter estimation. Each user ii first communicates obliviously with the tagging server to obtain the encrypted index hih_i for its kk-dimensional bucket index bib_i (line 2 in Algorithm 2) while ensuring that the tagging server learns nothing about users’ bucket assignments. A Verifiable Oblivious PseudoRandom Function [35] is applied to hash the kk-dimensional bucket indices so that users in the same bucket obtain the same encrypted index without the tagging server noticing and no user-to-user communications (Algorithm 4 in Appendix B).

Next, user ii submits hih_i with probability psp_s to the synthesis server (lines 4-6 in Algorithm 2), who then computes the aggregate counts and filters out all the indices that have not accumulated to τ\tau submissions from the users (lines 8-10 in Algorithm 2). This truncated histogram satisfies DP.

In addition to that, the non-frequent (encrypted) indices should also receive proper privacy protection, since they are observed by server SsynS_{\mathrm{syn}}. To that end, we follow [98] and introduce a dummy user who can send additional dummy indices to the server such that the non-frequent indices will also receive DP protection while preserving the correctness of the aggregation result (line 7 in Algorithm 2). Roughly speaking, if the number of dummy indices follows the truncated shifted discrete Laplace distribution (TSDLap), then the impact of an encrypted index is negligible compared with the dummy submission, ensuring DP. We refer to Definition 5 and Algorithm 5 in Appendix B for more details.

Distributed Centroid Computation

For each encrypted frequent index hh, each user ii who has submitted its index to the aggregate server in Step 2 examines hih_i: if it matches hh, then the user obtain a perturbed version for the embedding vector xix_i, written as x~i=Discrete-Gaussian⁡(xi,σ,β)\tilde{x}_i = \operatorname{Discrete\text{-}Gaussian}(x_i,\sigma,\beta), where σ\sigma is computed based on the target privacy budget ϵ\epsilon and δ\delta and the quantization factor β\beta, using the distributed discrete Gaussian mechanism [64]. Practical distributed DP protocols employ discrete noises [4, 24, 64] to reliably enforce privacy guarantees. However, we note that switching to discrete noises does not change the privacy–utility trade-off as long as the discretization granularity is not too coarse, according to [64], which is why we simulate with the continuous Gaussian noise in our experiments. We defer more technical details to Section 6.3 and Appendix B.

Next, the perturbed data points with the same frequent index hh are aggregated securely, then divided by the occurrence c(h)c^{(h)} and the quantization parameter β\beta. Here, the DP guarantee is collectively contributed by the local discrete Gaussian noises generated by users with the same index hh. To perform the secure aggregation, we reuse the tagging server and synthesis server from heavy hitter estimation: each user computes two secret shares for her/his perturbed embedding vector and sends them to the servers. The secret shares are tagged by the encrypted index hih_i so that the servers can later combine them to reconstruct the overall sum, as is done in federated analytics [32, 103]. One may also consider using the implementations from [21, 50]. Note that we cannot use the anonymous channel to replace distributed DP protocol, since the shuffle-model amplification for vector sums attains meaningful guarantees only in restricted ε\varepsilon regimes [30]; while secret-shared aggregation reconstructs the exact noisy sum at any ε\varepsilon.

Deployment costs. Recall that we write NN for the number of users, dd for the embedding dimension, kk for the projection dimension, psp_s for the subsampling rate, τ\tau for the heavy-hitter threshold, HH for the set of released buckets, and S=∑h∈Hc(h)S = \sum_{h\in H} c(h) for the number of submissions that participate in the centroid phase. On the user side, it first embeds its own text once and projects it in O(dk)O(dk) time offline. The distributed protocol is one-shot: the heavy-hitter phase costs each user O(1)O(1), and a user whose bucket is released spends a further O(dlog⁡d)O(d\log d) for the rotation and O(d)O(d) for quantization, discrete-Gaussian noise and secret sharing. Per-user communication is O(1)O(1) upstream in the heavy-hitter phase and O(d)O(d) upstream if participating in the centroid phase, and O(∣H∣)O(\lvert H\rvert) downstream to receive the released bucket set. For the server side, the tagging server performs O(N)O(N) VOPRF evaluations and O(Sd)O(Sd) share accumulation, while the synthesis server performs O(psN)O(p_sN) tag counting, O(Sd)O(Sd) accumulation and O(∣H∣dlog⁡d)O(\lvert H\rvert d\log d) reconstruction.

Party roles and observations. User ii performs all data-dependent computation on its own device: it embeds text viv_i, projects it, derives the bucket index bib_i, obtains the tag hih_i, draws its participation coin and its noise, and forms its two shares for DP centroid computation. It learns about other users only through the public release: the broadcast heavy-hitter histogram and the published centroids, both of which are differentially private results.

The tagging server StagS_{\mathrm{tag}} issues the bucket tags obliviously, generates the dummy tags that pad the sub-threshold histogram (Algorithm 5), and contributes one of the two additive shares of every perturbed embedding, sending SsynS_{\mathrm{syn}} the per-bucket aggregate share.

The synthesis server SsynS_{\mathrm{syn}} collects the sampled tag reports, counts them, discards tags below the threshold τ\tau, broadcasts heavy-hitting tags with their sampled counts, combines the two secret shares into the noisy per-bucket sum, and inverts the noisy centroids into synthetic text offline. Our privacy guarantee applies to the whole multiset of tags with their multiplicities and the DP centroids; therefore applies to every party.

Privacy in Distributed Settings

The privacy guarantees of the distributed implementation are largely similar to Algorithm 1. We highlight some differences.

Non-released indices in distributed heavy hitters. For each index that has accumulated <τ<\tau user submissions, the synthesis server observes the encrypted version of its index, and the noisy count. To argue the privacy for such statistics, we note that the index itself carries no information, as it looks random to any computationally bounded adversary [85]. So, the problem becomes analyzing the privacy cost for releasing an anonymized histogram (sometimes referred to as the count-of-counts [23, 71]), which reports the number of indices that have a count of QQ, for each Q=1,2,…,τ−1Q = 1, 2, \ldots, \tau- 1. According to [14, 37, 98], injecting TSDLap(λ,γ\lambda,\gamma) into the number of indices of each count satisfies (2λ,12exp⁡(−γ−2λ))(\frac{2}{\lambda}, \frac{1}{2}\exp(-\frac{\gamma-2}{\lambda}))-DP, which is exactly why we need to create dummy indices as in Alg. 5. The subsampling ratio of psp_s amplifies the privacy guarantee to (εunre,δunre)(\varepsilon_{\mathrm{unre}},\delta_{\mathrm{unre}})-DP with

εunre=ln⁡(1+ps(e2λ−1)),δunre=ps2e−γ−2λ.(11)\varepsilon_{\mathrm{unre}} = \ln\left(1+p_s(e^{\frac{2}{\lambda}}-1)\right), \qquad\delta_{\mathrm{unre}} = \frac{p_s}{2}e^{-\frac{\gamma-2}{\lambda}}. \tag*{(11)}

We can then obtain the following guarantee for all indices.

Lemma 6 (DP heavy hitter estimation). For any adversary who observes the broadcast heavy hitter histogram and the synthesis server who observes the counts of all indices (including dummies), Algorithm 2 satisfies (max⁡{εfh,εunre},max⁡{δfh,δunre})(\max\{\varepsilon_{\mathrm{fh}},\varepsilon_{\mathrm{unre}}\},\max\{\delta_{\mathrm{fh}},\delta_{\mathrm{unre}}\})-DP, where εfh\varepsilon_{\mathrm{fh}} and δfh\delta_{\mathrm{fh}} are from Lemma 1; εunre\varepsilon_{\mathrm{unre}} and δunre\delta_{\mathrm{unre}} are from (11).

Computing Centroids with Discrete Gaussian. The data preprocessing is not influenced by the distributed protocol. Hence, we can use the same L2L_2 sensitivity Δdist\Delta_{\mathrm{dist}}, with a high probability. Conditioned on this, we can apply the distributed discrete Gaussian mechanism (DDG) [64]. More concretely, the user first quantizes the embedding vector xi∈Rdx_i \in\mathbb{R}^d with parameter β\beta to an integer-valued vector in Zd\mathbb{Z}^d by multiplying the real vector by 1/β1/\beta and then randomly rounding each coordinate to the nearest integer. We note that while some biases will appear due to rounding, they can be offset to a negligibly small influence on the final result if β\beta is small enough, according to [64]. Then, for each coordinate of the integer-valued vector, the user perturbs it with a discrete Gaussian noise NZ(0,σ2)\mathcal{N}_{\mathbb{Z}}(0,\sigma^2) independently, computes two secret shares for the perturbed vector, and then sends them to the synthesis server and the perturbation server along with the encrypted index, using the framework suggested in [32, 103]. During secure aggregation, the discrete Gaussian noises contributed by independent users will aggregate into a larger noise (of standard deviation at least τσ\sqrt{\tau\sigma}) to amplify the DP guarantee. After obtaining the aggregated result, the synthesis server will then multiply it by β\beta to obtain an estimation for the original vector sum. We give the privacy guarantee of DDG as follows for completeness. Details are in Appendix B.

Theorem 7 (Distributed discrete Gaussian [64]). Let β>0\beta> 0 be the quantization parameter and σ\sigma be the parameter of the local discrete Gaussian noise. Under the same assumption as Theorem 3, define

ρagg:=min⁡(Δ222τσ2+κd, 12(Δ2τσ+κd)2),(12)\rho_{\mathrm{agg}} := \min\left(\frac{\Delta_2^2}{2\tau\sigma^2}+\kappa d,\ \frac{1}{2}\left(\frac{\Delta_2}{\sqrt{\tau}\sigma}+\kappa\sqrt{d}\right)^2\right), \tag*{(12)}

where Δ22=O(Δdist2)\Delta_2^2 = O(\Delta_{\mathrm{dist}}^2), and κ=10⋅∑j=1τ−1exp⁡(−2π2σ2β2⋅j1+j)\kappa= 10\cdot\sum_{j=1}^{\tau-1}\exp\left(-\frac{2\pi^2\sigma^2}{\beta^2} \cdot\frac{j}{1+j}\right) is some constant; see Theorem 9 for more details. The perturbed sum of embedding vectors from Alg. 2 satisfies ρagg\rho_{\mathrm{agg}}-CDP, and (εagg,δagg)(\varepsilon_{\mathrm{agg}},\delta_{\mathrm{agg}})-DP with

δagg=inf⁡α∈(1,∞)exp⁡((α−1)(αρagg−εagg))α−1⋅(1−1α)α.\delta_{\mathrm{agg}} = \inf_{\alpha\in(1,\infty)} \frac{\exp((\alpha-1)(\alpha\rho_{\mathrm{agg}}-\varepsilon_{\mathrm{agg}}))}{\alpha-1}\cdot\left(1-\frac{1}{\alpha}\right)^\alpha.

Overall DP guarantee. The overall DP guarantee comes from linearly composing the parameters from Lemma 6 and Theorem 7, and accounting for failure probability of sensitivity bound into the final δ\delta. Inverting centroids to texts costs no privacy. The only difference is that composition of parameters only occurs on the data points that appear in frequent buckets. Those data points that are not frequent do not participate in the release of DP sum of embedding vectors; hence, they compose in parallel [42].

Theorem 8 (Overall DP guarantee). With the parameters specified as in Lemma 1, Lemma 2, Lemma 6, and Theorem 7, and ff defined as in (7), Algorithm 2 satisfies (ε,δ)(\varepsilon,\delta)-DP for any adversary with

ε=max⁡(εfre+εagg,εunre), and(13)\varepsilon= \max(\varepsilon_{fre} + \varepsilon_{agg}, \varepsilon_{unre}), \text{ and} \tag*{(13)}
δ=max⁡(δfre+δagg+f(kLΔdist)k,δunre).(14)\delta= \max\left(\delta_{fre} + \delta_{agg} + f\left(\frac{\sqrt{kL}}{\Delta_{dist}}\right)^k, \delta_{unre}\right). \tag*{(14)}

Experiments

We demonstrate the utility of our algorithm and compare it with the state of the art [110]. Our goal is to show that our Fre-E2T achieves utility comparable to the strong centralized baseline under the same privacy constraints while being more distributed-friendly and offering additional protection for infrequent texts.

Datasets. Our experiments include four datasets containing user queries to search engines/LLMs: TaylorAI [105], Instructions-2M [89], LMSYS Chat [118], and Yelp [115]. See Appendix A for details.

Infrequent and frequent texts. Recall Section 2.2. We enforce additional privacy protection for infrequent user texts that have fewer than tt neighbors in its rr-neighborhood in the embedding space. Conversely, we say a text is frequent if it has more than tt neighbors in the rr-neighborhood. We take r=0.5r = 0.5 and t=100t = 100, unless otherwise stated.

Baseline and implementation. We focus on the state-of-the-art baseline for DP text synthesis from the centralized setting, i.e., Aug-PE [110], and use it as the reference point for evaluating the utility of our distributed Fre-E2T. We omit other baselines as they achieve similar performance as [110], while some of them relying on additional gradient access to the LM [47, 56, 113]. Since we assume no label information is available before hand and some datasets such as [89, 105] do not have such information, we remove such information (if there is any) from the prompts for a fair comparison. We follow their setup and use Aug-PE’s published hyperparameters. We use GPT-2 [95] as the generator API for [110] and gtr-t5-base [91] as the embedding model. gtr-t5-base maps each text input into a 768-dimensional vector.

For our implementation, we simulate our algorithm on a single machine with 4×\times A100 GPUs. We use the same embedding model. For the projected dimension, we focus on k=20k = 20 unless otherwise stated. We set the heavy hitter threshold τ=ρst\tau= \rho_s t, where ρs\rho_s is the subsampling rate controlling the privacy budget for the heavy hitter release. We vary ρs∈{0.3,0.5,0.6}\rho_s \in\{0.3, 0.5, 0.6\}. Next, the Gaussian noise parameter σ\sigma for centroid computation is determined by the remaining privacy budget. Throughout we fix the overall δ=10−6\delta= 10^{-6} and vary the overall ε∈{4,8,16,∞}\varepsilon\in\{4, 8, 16, \infty\}. For ε=∞\varepsilon= \infty, we run our Fre-E2T without any additional noise or privacy constraint. We leverage the open-sourced vec2text [88] to invert embeddings back to texts. This model contains 235M parameters. By default, the server uses vec2text to synthesize one text for each obtained DP centroid of embedding vectors. For our Fre-E2T, we also include a variant that uses GPT-2 to obtain more variations of each synthetic text generated from the released embedding vector, ensuring a fair comparison with Aug-PE. GPT-2 never touches the user data without affecting DP (see Section 6). To ensure a fair comparison, both Aug-PE and our Fre-E2T obtain 3000 texts in total.

Utility metrics. Given a synthetic dataset V~\widetilde{V} and the original private dataset VV, and constants rr and tt, we measure utility using three metrics that largely follow prior work [110, 113]: precision (higher is better), recall (higher is better), and average L2\mathcal{L}_2 distance (lower is better). We also report F1 score, the harmonic mean of precision and recall. The main here difference is that we compute these metrics on semantically frequent texts, i.e., V∖Vinfre(r,t)V \setminus V_{\mathrm{infre}}(r,t), since Definition 3 explicitly restricts outputs near semantically infrequent texts.

Prec⁡:=∑v~∈V~1(min⁡v∈V∖Vinfre(r,t)∥E(v~)−E(v)∥2≤αr)∣V~∣.(15)\operatorname{Prec} := \frac{\sum_{\widetilde{v}\in\widetilde{V}} \mathbb{1}\left(\min_{v\in V\setminus V_{\mathrm{infre}}(r,t)} \lVert E(\widetilde{v}) - E(v)\rVert_2 \le\alpha r\right)}{|\widetilde{V}|}. \tag*{(15)}
Rec⁡:=∑v∈V∖Vinfre(r,t)1(min⁡v~∈V~∥E(v~)−E(v)∥2≤αr)∣V∖Vinfre(r,t)∣.(16)\operatorname{Rec} := \frac{\sum_{v\in V\setminus V_{\mathrm{infre}}(r,t)} \mathbb{1}\left(\min_{\widetilde{v}\in\widetilde{V}} \lVert E(\widetilde{v}) - E(v)\rVert_2 \le\alpha r\right)}{|V\setminus V_{\mathrm{infre}}(r,t)|}. \tag*{(16)}
Dist⁡:=∑v~∈V~min⁡v∈V∖Vinfre(r,t)∥E(v~)−E(v)∥2∣V~∣.(17)\operatorname{Dist} := \frac{\sum_{\widetilde{v}\in\widetilde{V}} \min_{v\in V\setminus V_{\mathrm{infre}}(r,t)} \lVert E(\widetilde{v}) - E(v)\rVert_2}{|\widetilde{V}|}. \tag*{(17)}

Here, a larger α\alpha makes the neighborhood condition in Precision/Recall easier to satisfy. We fix α=1.5\alpha= 1.5 throughout unless otherwise stated, giving a threshold αr=0.75\alpha r = 0.75.

Main Results

Precision and recall. We report the utility of our Fre-E2T under different privacy budgets in Table 1. Overall, the precision, recall, and F1 score increases as the privacy constraint ε\varepsilon increases from 4 to ∞\infty. Namely, as the privacy constraint loosens, the synthetic texts achieve higher utility. This trend is consistent across all four datasets. On TaylorAI, both Aug-PE [110] and our method achieve almost perfect precision and recall. On Instructions-2M and LMSYS Chat, our Fre-E2T achieves notable improvements. We attribute such differences to the datasets: TaylorAI and Yelp have long sequences, leading to embedding vectors of smaller norms in general, hence easier to synthesize due to a smaller space. Other datasets contain shorter sequences and are in general more difficult to obtain closer synthetic texts.

Datasetε\varepsilonFre-E2T (no GPT-2) PrecisionRecallF1L2\mathcal{L}_2Fre-E2T (GPT-2) PrecisionRecallF1L2\mathcal{L}_2Aug-PE (GPT-2) PrecisionRecallF1L2\mathcal{L}_2
TaylorAI40.310.920.470.821.000.980.990.410.990.990.990.40
TaylorAI80.620.950.750.741.000.980.990.410.990.990.990.40
TaylorAI160.820.970.880.681.000.980.990.410.980.990.990.40
TaylorAI∞\infty0.830.970.890.671.000.980.990.400.980.990.980.40
Instructions-2M40.250.320.280.920.970.710.820.610.980.600.750.84
Instructions-2M80.380.340.360.800.970.740.840.570.980.600.750.83
Instructions-2M160.560.370.450.710.980.760.860.540.990.590.740.84
Instructions-2M∞\infty0.690.390.500.620.990.790.880.540.990.600.750.83
LMSYS Chat40.310.740.430.920.960.820.890.730.920.800.860.86
LMSYS Chat80.520.830.640.850.960.870.910.560.920.800.860.91
LMSYS Chat160.750.860.800.690.970.880.920.530.900.810.850.89
LMSYS Chat∞\infty0.830.840.830.670.970.860.910.570.910.800.850.91
Yelp40.300.960.460.821.001.001.000.370.981.000.990.37
Yelp80.651.000.760.721.001.001.000.370.941.000.970.37
Yelp160.871.000.930.671.001.001.000.380.981.000.990.36
Yelp∞\infty0.971.000.980.641.001.001.000.370.951.000.970.37

Table 1. Precision, recall, F1 score, and L2\mathcal{L}_2 distance (lower is better) across datasets for ε∈{4,8,16,∞}\varepsilon\in\{4, 8, 16, \infty\}. ε=∞\varepsilon= \infty denotes the non-DP setting. GPT-2 is used for paraphrasing by Fre-E2T and for generation and variation by Aug-PE.

Comparing the utility of Fre-E2T (no GPT-2) and Fre-E2T (GPT-2), we see that paraphrasing leads to higher utility. Utilizing stronger embedding models and corresponding vec2text reconstruction models will likely lead to further improvements. We leave that as a future work direction (discussed in Section 8).

L2\mathcal{L}_2 distance. The distance metric of (17) is an absolute distance in embedding space. Here, we include two references using the same embedding model. The same-dataset reference replaces the synthetic set by 3000 texts drawn uniformly from the frequent subset and scores them against the remaining frequent texts, setting the lower bound. The unrelated reference instead draws 3000 texts uniformly from the other three datasets and scores them against the target corpus: demonstrating what the distance metric looks like when the released text is irrelevant with the data. On TaylorAI, Instructions-2M, LMSYS Chat, and Yelp, the same-dataset and unrelated references are 0.20 and 1.37, 0.12 and 1.42, 0.06 and 1.29, and 0.26 and 1.51, respectively. Both methods fall into the range set up by the two references on all four datasets.

On Instructions-2M and LMSYS Chat, Fre-E2T is closer to the real input texts than Aug-PE under every privacy budget. On TaylorAI and Yelp, the two are within 0.02 of each other and quite close to the lower bound. Aug-PE and Fre-E2T also differ in how they use the privacy budget. The distance of Fre-E2T falls monotonically with ε\varepsilon on all four datasets shown, whereas Aug-PE barely moves. Similar trends are observed in Table 1. We explain this next.

To further inspect the closeness between a synthetic text and a input private text, in Figure 2, we report histograms of the smallest L2\mathcal{L}_2 distance from a frequent text (in blue) and an infrequent text (in red) to a synthetic text, with Instructions-2M dataset as the input. For private texts that are frequent, the L2\mathcal{L}_2 distances to the nearest synthetic texts are smaller, compared with infrequent texts, which is aligned with our utility objective and the privacy framework of semantic support protection—texts that are infrequent in the input should not find close neighbors in the synthetic output. We observe similar trends on other datasets and omit them here.

Histograms of the smallest distance from a frequent/infrequent text to a synthetic text on Instructions-2M

Figure 2. The smallest distance from a frequent/infrequent text (blue/red) to a synthetic text on Instructions-2M.

We also group the frequent texts from Instructions-2M dataset by their number of neighbors within distance r=0.5r = 0.5, and report the average L2\mathcal{L}_2 distance to the closest synthetic text within each frequent-text group in Figure 3. The trend is similar: as the number of neighbors of a frequent text increases, the L2\mathcal{L}_2 distance to its closest synthetic text decreases. This aligns with our algorithm design: for each heavy hitting bucket, the count of items in general increases as the number of neighbors for a frequent text therein increases. As we inject DP noises to the sum of embedding vectors, the DP noise averaged by the bucket count decreases as the count increases, leading to smaller L2\mathcal{L}_2 distances.

Average distances to synthetic texts for frequent texts as a function of neighbor number on Instructions-2M

Figure 3. Average distances to synthetic texts for frequent texts as a function of neighbor number on Instructions-2M.

Comparison with Aug-PE [110]. Aug-PE refines a population of candidate texts by having each private text vote for its nearest

candidate, releasing that vote histogram under DP, and asking a language model for variations of the candidates that receive more votes. When no label or category information is available, the histogram is the only signal connecting the candidate synthetic texts with the real inputs. It reports how many private texts lie near a candidate, but not which region of the input distribution that candidate should evolve towards. The variation step is therefore undirected and the population never separates into clusters matching the structure of the input data, so reducing the noise on the histogram only sharpens a signal that carries little directional information. That is what the flat trend of Aug-PE shows. The same insensitivity of text utility to the privacy budget is also observed in the original paper [110]. Fre-E2T supplies this missing structure: it clusters the frequent texts and generates each released text from one cluster centroid. This centroid is a soft label that tells what the texts therein is meant to represent in the embedding space. The privacy budget influences the accuracy of those centroids; hence, less noise translates directly into shorter distances and higher precision and recall.

Semantic support protection. Recall Definition 3, the parameters r∗r^* and δ∗\delta^* control the strength of semantic support protection: larger r∗r^* and smaller δ∗\delta^* impose stronger restrictions on the probability of outputs appearing near—i.e., within distance r∗r^*—semantically infrequent texts, which are defined by rr and tt (recall Definition 2). We empirically evaluate the level of δ∗\delta^* from (r,t,r∗,δ∗)(r,t,r^*,\delta^*)-Semantic Support Protection in Figure 4. We fix ε=4\varepsilon= 4 and vary r∗=ψrr^* = \psi r for ψ∈[0.1,1.5]\psi\in[0.1, 1.5] and tt from 10 to 100. We observe highly similar results on different tt’s and report only for t=10t = 10 and 100. In TaylorAI and Yelp, we achieve perfect protections of infrequent texts (i.e., δ∗=0\delta^* = 0) that vanish in the log-scale plot. Also, fixing r∗=rr^* = r (namely, ψ=1\psi= 1), Fre-E2T achieves a δ∗\delta^* near 10−510^{-5} under the simplified Definition 4 across all datasets. In general, the semantic support protection of our Fre-E2T is much stronger than Aug-PE [110], and sometimes by orders of magnitude.

In practice, we advise to set r∗=rr^* = r following Definition 4, with δ∗\delta^* set to 10−510^{-5}—a small failure probability that is also widely used in DP [1, 64]. Regarding rr, any value smaller than the reference distance from unrelated datasets makes sense. Here, we have chosen r=0.5r = 0.5 for an illustration. For tt, we recommend a negligible number compared with the population. Here, each dataset contains around 1 million records and we have chosen t=10t = 10 and 100.

More Results on Text Quality

Downstream utility. For dataset Yelp with labels, we train a classifier to rate the released texts, and evaluate on the official 50,000 test split, which is never used during synthesis. The task is five-way star prediction. We consider two ways of using the output of Fre-E2T. The first is directly operated on the released noisy centroids: a test review is embedded using the same model and classified by a majority vote over the kk nearest centroids released by Fre-E2T, across all 5 labels. We sweep k∈{1,5,10,20}k \in\{1, 5, 10, 20\} and report the best result. The second uses the inverted texts from Fre-E2T to fine-tune the RoBERTa-base classifier, following the setup in [110]. For Fre-E2T, we paraphrase each text 5 times, obtaining around 3000 texts in total for each temperature. We also make Aug-PE output the same number of texts, to make it a fair comparison.

Table 2 reports the classification accuracy. The non-DP baseline fine-tuned on RoBERTa achieves accuracy of 0.63 while the random guessing baseline is 0.20. With ε≥8\varepsilon\ge8, our method achieves competitive performance as directly obtained by Aug-PE. Notably, the difference between using the inverted texts and the centroids directly is not large, which confirms the utility of the DP centroids obtained by Fre-E2T. Still, there remains some gap to fill, and we conjecture that a better vector-to-text inverter could bridge this gap. We defer further discussions on the limitations and future work to Section 8.

Methodε=4\varepsilon= 4881616∞\infty
Fre-E2T: nearest centroid, k=1k = 10.350.450.460.47
Fre-E2T: nearest centroid, best kk0.350.460.480.49
Fre-E2T: RoBERTa (paraphrase T=0.7T = 0.7)0.320.440.460.48
Fre-E2T: RoBERTa (paraphrase T=1.0T = 1.0)0.320.420.460.47
Fre-E2T: RoBERTa (paraphrase T=1.4T = 1.4)0.300.450.470.51
Aug-PE: RoBERTa (default T=1.4T = 1.4)0.490.510.520.52
Non-DP: RoBERTa0.63

Table 2. Downstream classification accuracy on Yelp.

Diversity. Each cluster of Fre-E2T emits one text from the inversion model. However, diversity can be improved by paraphrasing and tuning the temperature of the paraphraser model (larger TT means more randomness and therefore higher diversity). In Table 2, we can see that the classification utility is largely unaffected by the paraphrasing temperature, which is aligned with [110]. Table 3 shows that higher temperature leads to better diversity, measured as the Self-BLEU (smaller is more diverse) per cluster, averaged over all clusters. Still, paraphrasing does not fully close the gap to real texts, since each cluster ultimately emits only one centroid based on the users’ contributions. We acknowledge this as a limitation.

Temperatureε=4\varepsilon= 4ε=8\varepsilon= 8ε=16\varepsilon= 16ε=∞\varepsilon= \inftyReal
T=0.7T = 0.752.350.848.446.4
T=1.0T = 1.049.647.346.345.427.7
T=1.4T = 1.447.544.142.141.7

Table 3. Diversity in BLEU score (↓\downarrow) of Fre-E2T under different temperatures for paraphrasing, evaluated on Yelp.

Perplexity. We also evaluate the released texts directly against matched-size random samples from the frequent subset of the original input, based on the perplexity score (smaller is more natural) computed from GPT-2. As we can see from Table 4, the average perplexity score of Fre-E2T improves monotonically as ε\varepsilon grows and approaches the real text samples. Note that the average metric can be affected by outliers. We show that most of the texts are deemed natural—namely, they have a low perplexity—in Appendix A.3 (see also the formal definition of perplexity).

Datasetε=4\varepsilon= 4ε=8\varepsilon= 8ε=16\varepsilon= 16ε=∞\varepsilon= \inftyReal
TaylorAI196125745122
Instructions-2M9542262657
LMSYS Chat13587523130
Yelp18490513427

Table 4. Average perplexity (↓\downarrow) of Fre-E2T evaluated with GPT-2.

Ablation Studies

We ablate each parameter of Fre-E2T on Instructions-2M and LMSYS Chat. Unless otherwise stated, parameters take their default values k=20k = 20, t=100t = 100, bucket edge L=2r/kL = 2r/\sqrt{k}, r=0.5r = 0.5 and we conduct experiments mostly on ε=8\varepsilon= 8 to observe a stable trend. Results are evaluated on text level, without GPT-2 paraphrasing, unless otherwise stated. Finally, we recall the couplings of the parameters: the heavy-hitter threshold enters the accounting only through τ=pst\tau= p_s t, and the sensitivity bound Δ=ur\Delta= ur is paid for with δsens=f(2/u)k\delta_{\mathrm{sens}} = f(2/u)^k, so Δ\Delta must be calibrated together with LL and kk.

Subsampling rate psp_s. At fixed tt, psp_s moves both terms of the budget: εfre=vln⁡(1/(1−ps))\varepsilon_{\mathrm{fre}} = v \ln(1/(1-p_s)) grows with psp_s, while δfre\delta_{\mathrm{fre}} shrinks with τ=pst\tau= p_s t. Here, vv controls the budget split between the heavy hitter histogram and the centroid computation. The feasible region at overall δ=10−6\delta= 10^{-6} is therefore bounded on both sides: ps≤0.1p_s \le0.1 exhausts the δ\delta budget for every v≤5v \le5 (δfre≥4⋅10−5\delta_{\mathrm{fre}} \ge4 \cdot10^{-5}). Inside the feasible region, the optimal psp_s is near 0.5, as Table 5 shows. For each psp_s we have chosen the budget split vv that minimizes the calibrated σ\sigma. The v={5,5,4,4,3}v = \{5, 5, 4, 4, 3\} used for the main experiments is not that choice: at ε=8\varepsilon= 8, v=2v = 2 raises F1 from 0.36 to 0.42 on Instructions-2M and from 0.64 to 0.71 on LMSYS Chat. We advise to choose psp_s as large as the ε\varepsilon budget allows and confirm that we did not specifically fine-tune the parameters of Fre-E2T to gain advantage over Aug-PE.

psp_s(v,σ)(v, \sigma)F1 Instructions-2MF1 LMSYS Chat
0.15(5, 0.914)0.350.45
0.20(4, 0.873)0.330.51
0.30(3, 0.886)0.370.61
0.50(2, 0.923)0.420.71
0.70(2, 1.067)0.350.74

Table 5. Subsampling rate psp_s at t=100t = 100 and ε=8\varepsilon= 8. Parameter vv is chosen to minimize the noise scale σ\sigma.

Bucket edge LL. We scale L=2r/kL = 2r/\sqrt{k} by m∈{0.5,…,2}m \in\{0.5, \ldots, 2\} with Δ=2.4rm\Delta= 2.4rm, which keeps the failure probability of sensitivity bound δsens=8.9⋅10−11\delta_{\mathrm{sens}} = 8.9 \cdot10^{-11} invariant. Accordingly, we re-calibrate σ\sigma, which is exactly proportional to mm. We list the values of σ\sigma in Table 12. The results are shown in Table 6. With differential privacy (ε<∞\varepsilon< \infty), smaller buckets win consistently: halving LL halves the noise, and still there are enough buckets that reach the threshold τ\tau. At ε=∞\varepsilon= \infty, F1 score first increases and then decreases as the LL increases. This is because without noise, coarser buckets improves the recall while reducing the precision in general. The default m=1m = 1 in our main

ε\varepsilonDatasetm=0.5m = 0.5m=0.75m = 0.75m=1m = 1m=1.5m = 1.5m=2m = 2
2Instructions-2M0.180.180.160.140.12
2LMSYS Chat0.340.290.240.240.25
8Instructions-2M0.410.370.350.290.28
8LMSYS Chat0.710.690.660.640.60
∞\inftyInstructions-2M0.500.500.500.760.72
∞\inftyLMSYS Chat0.780.790.830.860.86

Table 6. F1 score under different bucket-edge LL scaled by multiplier mm.

ϵ\epsilon0.50.7511.52
22.844.265.698.5311.4
80.5660.8481.131.702.26
∞\infty00000

Table 12. Noise scale σ\sigma under different bucket-edge LL scaled by multiplier mm.

Algorithm 6: User Procedure Aclient\mathcal{A}_{\mathrm{client}} for distributed discrete Gaussian mechanism [64]
Input: Vector xi∈Rdx_i \in\mathbb{R}^d.
Parameters: Dimension dd; L2\mathcal{L}_2 sensitivity Δdist\Delta_{\mathrm{dist}}; quantization granularity β>0\beta> 0; modulus m∈Nm \in\mathbb{N}; noise scale σ>0\sigma> 0; bias ϕ∈[0,1)\phi\in[0,1); a uniform random sign vector ξ∈{−1,+1}d\xi\in\{-1,+1\}^d and a Walsh–Hadamard matrix H∈{−1/d,+1/d}d×dH \in\{-1/\sqrt{d},+1/\sqrt{d}\}^{d \times d} that are shared among all parties.
Output: zi∈Zmdz_i \in\mathbb{Z}_m^d for the secure aggregation protocol.
1xi′←1β⋅xi∈Rdx_i' \leftarrow\frac{1}{\beta}\cdot x_i \in\mathbb{R}^d
2xi′′←HDξxi′∈Rdx_i'' \leftarrow HD_\xi x_i' \in\mathbb{R}^d.
3repeat
4Draw x~i∈Zd\widetilde{x}_i \in\mathbb{Z}^d from a product distribution such that E[x~i]=xi′\mathbb{E}[\widetilde{x}_i]=x_i' and ∣x~i−xi′′∣∞<1|\widetilde{x}_i-x_i''|_\infty<1.
5until
6∣x~i∣2≤min⁡{Δdistβ+d,Δdist2β2+14d+2log⁡(1/ϕ)⋅(Δdistβ+12d)}|\widetilde{x}_i|_2 \le\min\left\{\frac{\Delta_{\mathrm{dist}}}{\beta}+\sqrt{d},\sqrt{\frac{\Delta_{\mathrm{dist}}^2}{\beta^2}+\frac{1}{4}d+\sqrt{2\log(1/\phi)}\cdot\left(\frac{\Delta_{\mathrm{dist}}}{\beta}+\frac{1}{2}\sqrt{d}\right)}\right\}
7Sample ai∈Zda_i\in\mathbb{Z}^d with independent coordinates ai,j∼NZ(0,σ2/β2)a_{i,j}\sim\mathcal{N}_{\mathbb{Z}}(0,\sigma^2/\beta^2) for j=1,…,dj=1,\ldots,d.
8zi←(x~i+yi) mod mz_i\leftarrow(\widetilde{x}_i+y_i)\bmod m.

Table 6.

setup is not fine-tuned to optimize our Fre-E2T, ensuring a fair comparison with Aug-PE.

Embedding model. We repeat the pipeline with another open-sourced embedding model gte-modernbert-base [114]. Since embedding normal scales are not comparable across different embedding families—gte has median norms ≈38\approx38 while gtr has norms around 0.40.4–2.62.6, so we transfer the radius by quantile matching. We choose r′r' that matches the quantile of nearest-neighbour distance distribution that r=0.5r = 0.5 produces under the gtr embedding. This gives r′=14.86r' = 14.86 on Instructions-2M and r′=15.84r' = 15.84 on LMSYS Chat. Since no public vector-to-text inverter exists for this embedding family, the results are evaluated at the centroid level, shown in Table 7.

Datasetε\varepsilongtr-t5-base Precisiongtr-t5-base Recallgte-modernbert-base Precisiongte-modernbert-base Recall
Instructions-2M20.290.390.300.65
Instructions-2M81.000.471.000.81
Instructions-2M∞\infty1.000.481.000.82
LMSYS Chat20.030.820.090.40
LMSYS Chat80.990.951.000.66
LMSYS Chat∞\infty0.990.950.990.67

Table 7. Utility with different embedding models, measured at the centroid level.

Algorithm 7: Server Procedure Aserver\mathcal{A}_{\mathrm{server}} [64]
Input: Aggregated modulo sum zˉ∈Zmd\bar{z}\in\mathbb{Z}_m^d obtained via secure aggregation.
Parameters: Same as Algorithm 6.
Output: y∈Rdy\in\mathbb{R}^d
1Map Zm→{−⌊m/2⌋,…,0,…,⌊m/2⌋}\mathbb{Z}_m\to\{-\lfloor m/2\rfloor,\ldots,0,\ldots,\lfloor m/2\rfloor\} coordinate-wise so that zˉ′∈[−m/2,m/2]d∩Zd\bar{z}'\in[-m/2,m/2]^d\cap\mathbb{Z}^d and zˉ′ mod m=zˉ\bar{z}'\bmod m=\bar{z}.
2Compute y←βDξH⊤zˉ′y\leftarrow\beta D_\xi H^\top\bar{z}', where DξD_\xi is diagonal with ξ\xi on the diagonal.

Table 7.

Design Choices and Limitations

Fre-E2T essentially performs two tasks: identifying heavy hitting regions in the embedding space and inverting from the heavy hitters to synthetic texts. We first analyze the utility on the first task—identifying heavy hitting regions in the embedding space with DP. The first task is supported by two major technical components: random projection and partitioning and DP heavy hitter estimation, followed by the DP centroid computation.

Comparison with LDP mechanisms. For a clear reference, we evaluate two locally differentially private (LDP) baselines and a centralized-DP baseline. The first LDP baseline, named LDP (embedding), is to let each user release its text embedding vector with Gaussian noise injected [13]. Any post-processing on the noisy embeddings does not incur additional privacy cost [42]. The second LDP baseline, named LDP (OUE), is to replace the sample-and-threshold subroutine (lines 7–15 in Algorithm 1) with the OUE frequency estimation algorithm [107]. The rest follows: surviving buckets compute the noisy centroid with additive Gaussian noise with the remaining privacy budget. Here, we report the privacy budget split that maximizes utility.

The centralized DP baseline removes every distributed constraint while keeping the rest of the pipeline unchanged: a trusted curator observes all embeddings, releases each occupied bucket’s count with Gaussian noise and its embedding sum with Gaussian noise under the same probabilistic sensitivity bound Δdist\Delta_{\mathrm{dist}} as ours, then keeps the buckets whose noisy count exceeds τ=100\tau= 100. This baseline upper-bounds what any distributed realization of our pipeline can achieve.

Table 8 reports how well each mechanism identifies the heavy clusters in terms of precision and recall. The first LDP baseline identifies nothing at any ε≤16\varepsilon\le16: its local noise is O(d)O(\sqrt{d}), which is the same scale as the diameter of the whole embedding space, so no two users ever share a bucket and no cluster survives the threshold. The second fails for the same structural reason: the OUE count estimator’s noise is in O(n)O(\sqrt{n}), where nn is the number of users, which makes the heavy hitter histogram very noisy. As a result, the recall is only 3% and 14% for TaylorAI and Instructions-2M, respectively at ε=4\varepsilon= 4. It reaches to about half at ε=8\varepsilon= 8, and catches up with Fre-E2T only at ε=16\varepsilon= 16. Fre-E2T, in contrast, identifies the heavy clusters with precision and recall above 0.90 at every ε\varepsilon.

Methodε\varepsilonTaylorAI Prec.TaylorAI Rec.Instructions-2M Prec.Instructions-2M Rec.
LDP (Embedding)40.000.000.000.00
LDP (OUE)40.030.030.140.14
Fre-E2T40.930.910.920.92
Central-DP40.970.961.001.00
LDP (Embedding)80.000.000.000.00
LDP (OUE)80.510.520.560.57
Fre-E2T80.940.950.950.98
Central-DP80.980.981.001.00
LDP (Embedding)160.000.000.000.00
LDP (OUE)160.980.950.980.98
Fre-E2T160.980.960.990.99
Central-DP161.000.991.001.00

Table 8. Precision and recall measured at cluster level for heavy hitting clusters with τ≥100\tau\ge100.

These results justify our design. First, sample-and-threshold solves the identification task at almost no cost relative to a trusted curator. The LDP alternatives show the utility loss. Second, probabilistic sensitivity is what makes the centroid sums achieve high utility at all ε∈{4,8,16}\varepsilon\in\{4, 8, 16\}. A local randomizer must be indistinguishable over the entire input space, introducing large noises that are in the same scale of the space’s diameter, overwhelming useful information. Our release instead adds noise proportional to the probabilistic sensitivity.

Representativeness. Representativeness concerns which population the output speaks for. The released texts hold only 41% and 3.9% of the entire corpus, but 97% and 39% of the frequent subset of TaylorAI and 4.5% Instructions-2M, respectively, matching the numbers in Table 1. This is by our design, we filter out infrequent buckets to catch SPP while achieving high recall and precision for the frequent user texts.

Limitation and future work. We also identify a key limitation of our Fre-E2T. Table 9 scores the synthetic texts obtained after inversion for Fre-E2T. Comparing Tables 9 and 8, we can see that the embedding-to-text inversion, rather than the DP machinery, is the current bottleneck of Fre-E2T, as we observe a utility drop on the inverted text. In particular, for Instructions-2M dataset, when ε=8\varepsilon= 8, the precision and recall dropped from 0.95 and 0.98 to 0.38 and 0.34.

Methodε\varepsilonTaylorAI Prec.TaylorAI Rec.Instructions-2M Prec.Instructions-2M Rec.
Fre-E2T40.310.920.250.32
Central-DP40.720.970.480.37
Fre-E2T80.620.950.380.34
Central-DP80.830.970.620.38
Fre-E2T160.820.970.560.37
Central-DP160.860.970.620.38

Table 9. Precision and recall of the synthetic texts.

For the centralized DP method that uses the same inversion model, this drop is still substantial. At ε=16\varepsilon= 16, Fre-E2T achieves almost the same utility as its centralized-DP version. This confirms that the utility drop is from the inverter [88] that we used as a black box, not the distributed constraints. It was also noted in [89] that even inverting from noiseless embeddings may not recover the perfect text. Overall, domain-adapted inverters and designs that capture the objectives of diversity and downstream task utility (recall Section 7.2) are therefore promising directions for improving the end-to-end quality of Fre-E2T.

Conclusion

We propose a lightweight distributed algorithm for synthesizing texts from distributed users. Our algorithm design does not rely on trusted servers, gradient/parameter access to LMs, iterative and tight user synchronization, or publicly available labels, addressing major limitations of the existing literature. Our method can also be implemented efficiently based on existing distributed protocols. Compared with the state of the art, our method achieves comparable and sometimes better utility across real-world datasets, with an extra layer of privacy protection for infrequent user data and better practicality in distributed settings.

Acknowledgments

We would like to thanks the reviewers and editors for their constructive feedbacks during the reviewing process.

Ethical Considerations

We have read and adhered to the PoPETs ethics guidelines and the Menlo Report and believe the work was conducted ethically. The work does not involve human subjects, sensitive user data, or system vulnerability disclosure; all experiments use publicly available benchmark datasets and openly released language models.

Stakeholders. The primary stakeholders are:

  • End users. Our protocol is designed so that distributed users can collectively contribute to a synthetic text corpus without any party, including the server that runs the protocol, observing their raw texts. Users benefit from formal (ε,δ)(\varepsilon, \delta)-DP guarantees that protect individual records and additional protection for users whose texts are semantically infrequent.

  • Researchers. Our work enables the research community to collaboratively generate synthetic texts from distributed private corpora, facilitating research collaboration while preserving the privacy of the underlying data.

  • System developers. The algorithm can be deployed in privacy-preserving data collection and analysis pipelines, enabling service providers to improve models and user experience without ingesting raw user text.

Ethical principles. Following the Menlo Report, we adhere to four principles:

  • Beneficence. The purpose of this research is to improve the practicality and the theory of synthesizing texts from distributed users without degrading privacy or utility. Experiments are restricted to public benchmarks.

  • Respect for persons. No personal or private user data was used. All datasets and models were either synthetic or publicly available.

  • Justice. We highlight the scalability issue of existing DP text-synthesis methods and provide a more practical distributed solution. We hope our work can be used by system developers to facilitate privacy-preserving data collection and analysis.

  • Respect for law and public interest. All experiments comply with the applicable open-source software licenses.

Potential harms and mitigations.

  • Risk of over-interpretation. Our contribution is an algorithm for DP text synthesis; it is not intended to be used to generate fake content for misuse.

  • Controlled scope. Our work is restricted to the differential privacy framework under the semi-honest threat model. The algorithm should not be deployed in arbitrary environments outside this assumption set, as that may lead to data exploits not covered by the analysis.

Decision to conduct and publish. We believe that proposing a practical algorithm for distributed differentially private text synthesis is valuable to the community, since our algorithm enables researchers and system developers to share, collect, and analyse sensitive textual data without exposing individual records or violating user privacy.

External review. This work was not submitted to an external ethics panel (e.g., IRB or the Tor Research Safety Board) because the study uses only public benchmarks and does not involve human subjects or sensitive user data.

Open Science

All datasets used in this work are publicly available. Upon acceptance, the artifacts will be released, including: (1) implementations of the algorithm; (2) all dataset preprocessing scripts; and (3) any scripts essential to reproduce the results.

AI Use

We disclose all use of generative AI in the preparation of this manuscript and the underlying research. The authors used ChatGPT to revise the text to improve flow, correct typographical and grammatical issues, and improve the presentation of figures, based on experimental results. We verified that AI did not introduce new claims, and did not fabricate references. Generative AI was not used to design the algorithm or derive the privacy analysis. All references were collected from the original publications.

References

Algorithm 3: CalibrateNoise

Input: target $(\varepsilon,\delta)$; radius $r$; frequency threshold $t$; projection dimension $k$; subsampling rate $p_s$; budget factor $v \ge 1$; sensitivity ratio $u$ (so $\Delta_{\mathrm{dist}} = u r$)

Output: Gaussian noise scale $\sigma$ for the centroid sums

1. $\tau \leftarrow p_s t$ // threshold on sampled counts
2. $\varepsilon_{\mathrm{fre}} \leftarrow v \ln \frac{1}{1-p_s}$
3. $q \leftarrow 1-(1-p_s)^{v+1}$
4. $\delta_{\mathrm{fre}} \leftarrow \exp\left(-\frac{\tau}{d}D(q \mathbin{\|} p_s)\right)$ // Lemma 1
5. $\delta_{\mathrm{sens}} \leftarrow f(2/u)^k$ // Lemma 2
6. $\varepsilon_{\mathrm{agg}} \leftarrow \varepsilon-\varepsilon_{\mathrm{fre}}$
7. $\delta_{\mathrm{agg}} \leftarrow \delta-\delta_{\mathrm{fre}}-\delta_{\mathrm{sens}}$ // budget for Gaussian
8. if $\varepsilon_{\mathrm{agg}} \le 0$ or $\delta_{\mathrm{agg}} \le 0$ then
9. abort // lower $v$ (or $p_s$) if $\varepsilon_{\mathrm{agg}} \le 0$; raise $\tau$, $v$, or $u$ if $\delta_{\mathrm{agg}} \le 0$
10. $\rho_{\mathrm{agg}} \leftarrow \max\left\{\rho > 0:\inf_{\alpha \in (1,\infty)}\frac{\exp((\alpha-1)(\alpha\rho-\varepsilon_{\mathrm{agg}}))}{\alpha-1}\left(1-\frac{1}{\alpha}\right)^\alpha \le \delta_{\mathrm{agg}}\right\}$ // Thm. 3
11. return $\sigma \leftarrow \frac{u r}{\sqrt{2\rho_{\mathrm{agg}}}}$

Additional Experiment Details and Results

We have used the following datasets.

  1. TaylorAI [105] includes 1.5 million user queries.

  2. Instructions-2M [89] is a meta-dataset containing approximately 2.33 million instructions, including user and system prompts spanning different problem domains.

  3. LMSYS Chat-1M [118] contains one million real-world conversations with 25 state-of-the-art LLMs. The dataset includes interactions collected from 210K unique IP addresses. We consider each user query as an individual.

  4. Yelp [115] consists of reviews from Yelp. It is extracted from the Yelp Dataset Challenge 2015 data.

We apply a preprocessing step to filter out samples where the language is non-English, minimizing the potential impact of multilingual limitations in the embedding models. The resulting statistics are summarized in Table 10.

Dataset#samples#textsAverage length
TaylorAI1.29×1061.29 \times10^60.442×1060.442 \times10^688.1
Instructions-2M2.33×1062.33 \times10^60.229×1060.229 \times10^630.6
LMSYS-Chat-1M1.50×1061.50 \times10^60.446×1060.446 \times10^672.0
Yelp0.65×1060.65 \times10^60.518×1060.518 \times10^6192

Table 10. Dataset statistics for the overall number of samples and number of frequent items in millions and the average token length per sample.

Hyperparameters

Our algorithm rely on the following hyperparameters.

  • Overall privacy parameters. We fix δ=10−6\delta= 10^{-6} and vary ε∈{4,8,16}\varepsilon\in\{4, 8, 16\} and ∞\infty (i.e., non-DP setting).

  • Recall that for any two data points in the embedding space Rd\mathbb{R}^d, we see them as rr-neighbors if their L2L_2 distance is not larger than rr. We say a text is frequent if it has at least tt neighbors in its rr-neighborhood. We have taken r=0.5r = 0.5 and t=100t = 100 unless otherwise stated in our experiments (see Section 7).

  • Data pre-processing for embedding, projection, and partitioning. Each client calls the public, black-box embedding function to compute a dd-dimensional embedding vector for its text, with d=768d = 768. Next, the dd-dimensional vector is randomly projected onto the kk-dimensional space using a Gaussian projector Rd×k\mathbb{R}^{d \times k} whose entries are sampled independently from N(0,1)\mathcal{N}(0,1), scaled by 1/k1/\sqrt{k}. We fix k=20k = 20 in our experiments and provide ablation studies on the impact of kk in Section 7. The space Rk\mathbb{R}^k is then partitioned into buckets of edge length L=2r/kL = 2r/\sqrt{k} on each dimension, with an independent uniform random offset per dimension.

  • Component for identifying heavy hitters. Each client contributes its bucket index to the synthesis server with probability psp_s (the subsampling rate). The server keeps the bucket indices whose sampled count nhn_h reaches the threshold τ=ps⋅t\tau= p_s \cdot t, i.e. τ=30,50,60,100\tau= 30, 50, 60, 100 for ε=4,8,16,∞\varepsilon= 4, 8, 16, \infty with ps=0.3,0.5,0.6,1p_s = 0.3, 0.5, 0.6, 1. Following Lemma 1, we spend εfre=v⋅log⁡11−ps\varepsilon_{\mathrm{fre}} = v \cdot\log\frac{1}{1-p_s} on this release, with the budget factor v=4,4,3v = 4, 4, 3 for ε=4,8,16\varepsilon= 4, 8, 16; the corresponding δfre=exp⁡(−τdD(q∥ps))\delta_{\mathrm{fre}} = \exp\left(-\frac{\tau}{d}D(q \mathbin{\|} p_s)\right), q=1−(1−ps)v+1q = 1-(1-p_s)^{v+1}, is listed in Table 11. Here vv was chosen per target so that the remaining δ\delta budget suffices, see Algorithm 3.

  • Component for centroid computation. For each heavy bucket, the clients that submitted to it aggregate their dd-dimensional embedding vectors, and Gaussian noise N(0,σ2Id)\mathcal{N}(0,\sigma^2 I_d) is added to the sum. We set the target sensitivity to Δdist=u⋅r\Delta_{\mathrm{dist}} = u \cdot r; the ratio uu is fixed per projection dimension. We set u=2.4u = 2.4 at our default k=20k = 20, and its failure probability δsens=f(2/u)k\delta_{\mathrm{sens}} = f(2/u)^k is accounted in the final δ\delta (Theorem 4). For the split (εfre,δfre)(\varepsilon_{\mathrm{fre}}, \delta_{\mathrm{fre}}), the noise scale is calibrated with the Gaussian mechanism (Theorem 3) via procedure CalibrateNoise (Algorithm 3); for k=20k = 20 this gives σ=2.136,1.14,0.516\sigma= 2.136, 1.14, 0.516 for ε=4,8,16\varepsilon= 4, 8, 16 (noise multipliers m=σ/Δdistm = \sigma/\Delta_{\mathrm{dist}} of 1.78, 0.95, 0.43). When ε=∞\varepsilon= \infty (non-DP), σ=0\sigma= 0 and no subsampling is applied (ps=1p_s = 1).

ε\varepsilonδfre\delta_{\mathrm{fre}}δsens\delta_{\mathrm{sens}}δagg\delta_{\mathrm{agg}} budget
42.93×10−102.93 \times10^{-10}8.95×10−118.95 \times10^{-11}1.00×10−61.00 \times10^{-6}
83.80×10−133.80 \times10^{-13}8.95×10−118.95 \times10^{-11}1.00×10−61.00 \times10^{-6}
161.76×10−111.76 \times10^{-11}8.95×10−118.95 \times10^{-11}1.00×10−61.00 \times10^{-6}

Table 11. Split of the overall budget δ=10−6\delta= 10^{-6} at k=20k = 20.

Split of δ\delta. Table 11 shows the split of the overall δ=10−6\delta= 10^{-6} (at k=20k = 20) among the heavy-hitter release (δfre(\delta_{\mathrm{fre}}, sensitivity-bound failure δsens)\delta_{\mathrm{sens}}), and the remainder available to the centroid computation. We can see that δsens\delta_{\mathrm{sens}} consumes a negligible portion of the overall budget—only around 0.1%0.1\%.

Numerical procedure. One can use Algorithm 3 to obtain the Gaussian noise scale given target privacy parameters, radius r>0r > 0, frequency threshold t∈N∗t \in\mathbb{N}^{*}, projection dimension k∈N∗k \in\mathbb{N}^{*}, subsampling rate ps∈(0,1)p_s \in(0, 1), the budget factor v>0v > 0, and the sensitivity ratio/noise multiplier u>0u > 0. Note that we use the continuous Gaussian mechanism (Theorem 3) instead of the discrete distributed Gaussian mechanism (Theorem 9) for simulation purpose, since [64] have pointed out that when the quantization granularity is high enough, both mechanisms are indistinguishable in utility under the same privacy budget.

More Ablation Studies

For the ablation study on edge length LL shown in Section 7.3, the noise scale is listed in Table 12.

Embedding model. The comparison in Table 7 is about transferability of observations, not about which encoder is “better”. We can observe that the overall trend of utility-privacy trade-off is similar, precision and recall almost reach the non-DP baseline when ϵ≥8\epsilon\ge8. The concrete numbers differ, which is expected, since a different embedding model also changes which infrequent texts the mechanism protects and which frequent texts the mechanism reconstructs. More ablation studies and the details of hyperparameters are in Appendix A.1.

Projection dimension kk. Table 13 presents the F1 score for k={10,15,20,25,30}k = \{10, 15, 20, 25, 30\}. The best kk depends on ϵ\epsilon, while in general, larger kk is better for ϵ<∞\epsilon< \infty. This is because larger kk reduces the failure probability of the sensitivity bound (recall Lemma 2), allowing more freedom to choose the noise scale for centroid perturbation.

datasetϵ\epsilon1015202530
Instructions-2M20.110.150.170.170.18
40.130.220.280.310.30
80.260.340.360.440.41
160.490.470.450.400.47
∞\infty0.690.540.500.500.49
LMSYS Chat20.250.260.250.290.28
40.380.4190.430.500.52
80.540.6370.640.710.70
160.750.770.800.790.76
∞\infty0.850.840.830.830.79

Table 13. F1 score under varying projection dimension kk.

Frequency threshold tt. Together with rr, tt defines the frequent and infrequent texts from the input (recall Definition 2) and therefore the evaluation metrics. Hence, the results for different tt’s are not directly comparable. We also note that σfre\sigma_{\mathrm{fre}} decays exponentially in τ=pst\tau= p_s t, so at the desired overall δ=10−6\delta= 10^{-6}, our Fre-E2T is feasible only for t≳100t \gtrsim100 at our subsampling rates. From Table 14, as we increase tt from 100 to 200, the released number of buckets decreases since fewer buckets would satisfy the frequent-text requirement. On the other hand, there is not clear utility trend at different tt’s. Our main experiment setup selected t=100t = 100, which is a small number compared with the overall population.

Quantity100200400
F1 Instructions-2M0.330.430.52
F1 LMSYS Chat0.690.780.73
# Buc. Instructions-2M895739
# Buc. LMSYS Chat42417559

Table 14. Influence of threshold tt (τ=pst\tau= p_s t) on the resulting F1 score at ϵ=8\epsilon= 8. # Buc. is the number of released buckets.

More on Text Utility

Let pθp_\theta be an autoregressive language model and let a text ww tokenize into (w1,…,wT)(w_1, \ldots, w_T) under pθp_\theta’s tokenizer. The per-token negative log-likelihood (NLL) of ww is its average next-token surprisal in nats,

NLL⁡(w)=−1T−1∑t=2Tlog⁡pθ(wt∣w1,…,wt−1).(18)\operatorname{NLL}(w) = -\frac{1}{T-1}\sum_{t=2}^{T}\log p_\theta(w_t \mid w_1,\ldots,w_{t-1}). \tag*{(18)}

The perplexity score of ww is the exponential of the per-token NLL, PPL⁡(w)=exp⁡(NLL⁡(w))\operatorname{PPL}(w) = \exp(\operatorname{NLL}(w)). Lower NLL (equivalently, lower PPL) means the text is closer to natural language as modeled by pθp_\theta. We use GPT-2 as pθp_\theta.

Here, we report the median of the per-text NLL over each text set, together with the fraction of texts with NLL⁡(w)≤6\operatorname{NLL}(w) \le6, on TaylorAI. From Table 15 we can see that for the outputs from Fre-E2T, their NLL approaches that of the real corpus as the privacy budget increases, matching the results from Section 7.2.

Text setMedian NLL% texts NLL ≤6\le6
Fre-E2T (ϵ=4\epsilon= 4)5.2877.9%
Fre-E2T (ϵ=16\epsilon= 16)4.2995.4%
Real texts3.4399.5%

Table 15. NLL of Fre-E2T outputs vs. real text of TaylorAI evaluated using under GPT-2. The real texts are a random 1000-text sample of the frequent texts.

Evaluation on All Input Texts

Recall (15) to (17). We restrict the utility metrics to semantically frequent texts. This is a design consequence, not a favorable selection: semantic support protection (Definition 3) requires that infrequent texts remain far from the generated texts. Table 16 repeats every run of the main Table 1 and evaluate against the full input set VV. Precision is unchanged or higher, since a synthetic text now only has to be close to some input text. Recall falls by the infrequent mass. For example, at ε=∞\varepsilon= \infty it is 0.35 for frequent AOL texts (recall Table 1) and 0.03 over all of them, since in AOL 92% of the corpus is infrequent. On TaylorAI, the recall decreases from 0.97 to 0.41 with 66% infrequent input texts. The gap between the two tables exactly that proves that our protection for infrequent texts works.

TaylorAIInstructions-2MLMSYS ChatYelp
∣Vinfre∣/∣V∣|V_{\mathrm{infre}}|/|V|66%90%70%20%
ε\varepsilonPrec.Rec.F1Prec.Rec.F1Prec.Rec.F1Prec.Rec.F1
40.310.330.320.270.030.060.320.220.260.300.770.44
80.620.350.450.530.030.060.540.260.350.610.830.70
160.820.390.530.600.040.070.770.280.410.870.850.86
∞\infty0.830.410.550.710.040.070.850.280.420.970.860.91

Table 16. Utility measured against all input texts VV. Compared with Table 1 that reports the same runs against the frequent subset V∖VinfreV \setminus V_{\mathrm{infre}}, precision is unchanged or higher here (the nearest-text condition is evaluated over a larger set); recall falls by the infrequent mass, which our Fre-E2T mechanism deliberately does not support.

Details of Distributed Fre-E2T

We refer to Figure 5 for the distributed implementation of Fre-E2T and Figure 6 for the illustration of the partitioning procedure on the kk-dimensional projection space.

We refer to Algorithm 4 for the verifiable oblivious pseudorandom function for randomly permuting user indices. Truncated Shifted Laplace noise is introduced to enforce DP for non-frequent user texts during the heavy hitter identification process. We refer to Definition 5 and Algorithm 5 for the definition and the algorithmic process, respectively.

Definition 5 (Truncated Shifted Discrete Laplace (TSDLap)). The distribution of TSDLap on {0,…,2γ}\{0,\ldots,2\gamma\} is defined as

fTSDLap(λ,γ)(u)={exp⁡(−∣u−γ∣λ)A,if u∈{0,…,2γ},0,otherwise,f_{\mathrm{TSDLap}(\lambda,\gamma)}(u) = \begin{cases} \dfrac{\exp\left(-\dfrac{|u-\gamma|}{\lambda}\right)}{A}, & \text{if } u \in\{0,\ldots,2\gamma\},\\ 0, & \text{otherwise}, \end{cases}

where λ∈(0,1)\lambda\in(0,1) is the scale, γ\gamma is the shift from 0, and

A=∑u=02γexp⁡(−∣u−γ∣λ)=1+2∑u=1γexp⁡(−uλ).A = \sum_{u=0}^{2\gamma}\exp\left(-\dfrac{|u-\gamma|}{\lambda}\right) = 1 + 2\sum_{u=1}^{\gamma}\exp\left(-\dfrac{u}{\lambda}\right).

We note that SsynS_{\mathrm{syn}} sees the multiset of sub-threshold tags with their exact multiplicities; the tags themselves are pseudorandom to any party without the OPRF key, and it is the resulting count-of-counts—how many tags were seen with each multiplicity—that Algorithm 5’s TSDLap padding makes differentially private [98].

We also provide the full description of the distributed discrete Gaussian mechanism to obtain the aggregated vector sum of distributed users [64] (other mechanisms such as [4, 28] lead to similar results). See Algorithm 6 and Algorithm 7. In short, each user locally quantizes its vector, perturbs it with discrete Gaussian noise, and then takes the modulo in order to prepare for secure aggregation [21, 87, 103]. After secure aggregation, the untrusted reconstructs an estimate for the sum by unwinding the modulo operation and the quantization. When the quantization granularity is fine, e.g., β=2−16\beta= 2^{-16}, the resulting data utility (error compared with the original, non-quantized, non-DP vector sum) is almost the same as perturbing the sum directly with continuous Gaussian noise in the centralized setting [1, 64]. In our simulation of Fre-E2T, we adopt the continuous Gaussian without loss of generality.

Theorem 9 (Distributed discrete Gaussian (complete version) [64]). Let ϕ\phi be the parameter controlling the rounding bias, β>0\beta> 0 be the quantization parameter, σ\sigma be the parameter of the local discrete Gaussian noise. Under the same assumption as Theorem 3, define

Δ22:=min⁡((Δdist+βd)2, β2d4+2log⁡(1ϕ)⋅β⋅(Δdist+β2d)),(19)\Delta_2^2 := \min\left((\Delta_{\mathrm{dist}}+\beta\sqrt{d})^2,\, \frac{\beta^2 d}{4}+\sqrt{2\log\left(\frac{1}{\phi}\right)}\cdot\beta\cdot\left(\Delta_{\mathrm{dist}}+\frac{\beta}{2}\sqrt{d}\right)\right), \tag*{(19)}
κ=10⋅∑j=1τ−1exp⁡(−2π2σ2β2⋅jj+1),(20)\kappa= 10\cdot\sum_{j=1}^{\tau-1}\exp\left(-\frac{2\pi^2\sigma^2}{\beta^2}\cdot\frac{j}{j+1}\right), \tag*{(20)}
ρagg:=min⁡(Δ222σ2+κd,12(Δ2τσ+κd)2).(21)\rho_{\mathrm{agg}} := \min\left(\frac{\Delta_2^2}{2\sigma^2}+\kappa d,\frac{1}{2}\left(\frac{\Delta_2}{\sqrt{\tau\sigma}}+\kappa\sqrt{d}\right)^2\right). \tag*{(21)}

The outcome of the perturbed sum of embedding vectors from Alg. 2 satisfies ρagg\rho_{\mathrm{agg}}-CDP, and (εagg,δagg)(\varepsilon_{\mathrm{agg}},\delta_{\mathrm{agg}})-DP with

δagg=inf⁡α∈(1,∞)exp⁡((α−1)(αρagg−εagg))α−1⋅(1−1α)α.(22)\delta_{\mathrm{agg}} = \inf_{\alpha\in(1,\infty)}\frac{\exp((\alpha-1)(\alpha\rho_{\mathrm{agg}}-\varepsilon_{\mathrm{agg}}))}{\alpha-1}\cdot\left(1-\frac{1}{\alpha}\right)^\alpha. \tag*{(22)}

Connection with [27]. Our clustering process of projecting data into a lower-dimension space and then partitioning the data into buckets is in spirit similar to the DP clustering work [27]. Our difference is in the design of the distributed algorithm. While Chang et al. [27] focuses on the local DP model, we employ the more recent sample-and-threshold privacy framework [15] which has an efficient distributed implementation [98] with the help of an untrusted randomness server. In addition, we also exploit the structure of L2L_2 distance-based clustering to reduce the sensitivity when computing the cluster centroid.

On Sample-and-threshold Histogram. Algorithm 1 releases two things for each heavy bucket hh: the pair (h,nh)(h,n_h) in the heavy-hitter step (line 15) and the noisy centroid μ^h\hat{\mu}_h in the aggregation step (line 19). Here nhn_h is not the number of users in bucket hh: it is the number of users that sampled themselves into the release, i.e. nh∼Bin⁡(Nh,ps)n_h \sim\operatorname{Bin}(N_h,p_s) where NhN_h is the true bucket size. The pair (h,nh)(h,n_h)

Algorithm 4: Client-TaggingServer

Input: user $i$ holding $b_i \in \mathbb{Z}_q^*$; tagging server; VOPRF secret key msk; hash function $g(\cdot)$.
Output: Random string $h_i$

1 user $i$: Hash the index $u \leftarrow g(b_i)$
2 user $i$: Sample blinding $r' \xleftarrow{R} \mathbb{Z}_q^*$
3 user $i$: Compute blind $\leftarrow u^{r'}$
4 user $i$: Send blinded hash blind to the server
5 Tagging server: Compute $z \leftarrow \mathrm{blind}^{\mathrm{msk}}$
6 user $i$: Unblind the response $w \leftarrow z^{1/r'}$
7 user $i$: Obtain $h_i \leftarrow g(w,b_i)$
8 Return $h_i$
Algorithm 5: Dummy-Data-Creation

Input: A public thresholding value $\tau$; Truncated Shifted Discrete Laplace distribution $\operatorname{TSDLap}(\cdot)$ with scale $\lambda$ and shift $\gamma$.
Output: A list of dummy indices

1 Dummy $\leftarrow \{\}$
2 for $n = 1,\ldots,\tau-1$ do
3   Sample $Q \leftarrow \operatorname{TSDLap}(\lambda,\gamma)$
4   $\{\operatorname{tag}_j\}_{j=1}^{Q} \leftarrow \operatorname{UniqueIndexGenerator}(\alpha)$
5   for $j = 1,\ldots,Q$ do
6     Append $n$ copies of $\operatorname{tag}_j$ to Dummy
7   end
8 end
9 return Dummy

is precisely the output that the sample-and-threshold guarantee of Lemma 1 certifies with (εfre,δfre)(\varepsilon_{fre},\delta_{fre}). The raw count NhN_h itself is never released. The centroid step then divides the noise-perturbed sum by the already released nhn_h (line 18); since both the numerator’s DP guarantee (Theorem 3) and the divisor’s (Lemma 1) are already accounted in Theorem 4 by linear composition, this division is post-processing and incurs no additional privacy cost [42].

Deployment Costs

We complement the cost analysis in Section 6.2 with concrete numbers. The costs are measured on an AMD EPYC 9554 (124 cores) with one NVIDIA H100 80 GB without real test on distributed environments. Parameters are ε=2\varepsilon= 2, k=20k = 20, δ=10−6\delta= 10^{-6}, d=768d = 768, d′=1024=O(d)d' = 1024 = O(d), and the reported dataset is TaylorAI.

The per-operation costs in the distributed Fre-E2T are: one VOPRF evaluation 89.5 μ\mus; tag counting 1.05 μ\mus per tag; share accumulation 10.7 μ\mus per share; bucket reconstruction 60.5 μ\mus per bucket; and text embedding 0.29 ms per text on the GPU amortized at batch size 256. A user spends around 0.4 ms online in total, uploads 8.3 kB and downloads 6.1 kB. Both servers finish in a couple of minutes for NN VOPRF evaluations and the computation for the centroids. There is no need for GPU for the online phases. The offline vec2text inversion takes 133ms per text. The dummy traffic that protects sub-threshold buckets is around 1710 messages and 113 kB for the entire run.

Comparison with Aug-PE. Aug-PE [110] keeps a population of NsynN_{syn} synthetic texts and, in each of TT iterations, generates L−1L-1 rephrasings of every kept sample, embeds the resulting pool of Ncand=LNsynN_{cand} = LN_{syn} candidates, has every private record vote for its nearest candidate, perturbs that histogram and keeps the top NsynN_{syn}. Its per-iteration cost is thus (L−1)Nsyn(L-1)N_{syn} generations, NcandN_{cand} embeddings and Θ(NpriNcandd)\Theta(N_{pri}N_{cand}d) for computing the embedding distance, repeated TT times. In addition, because the vote is over private data, the distance computation must be done on the users’ devices, which must download all candidate text embeddings first. With Nsyn=3000N_{syn} = 3000, L=7L = 7, T=20T = 20 (i.e. 21,000 candidates scored per iteration), one iteration of Aug-PE takes 64.6 s on an H100 GPU. A full run takes 21.7 minutes that require users’ synchronous updates and continuous participation, much longer than Fre-E2T.

On the server side, neither method is expensive in computation or communication. The difference is on the user side: Fre-E2T’s user cost is paid once and is independent of TT and of NcandN_{cand}, whereas Aug-PE’s recurs every iteration and scales with the candidate pool. We highlight this difference in Table 17.

Per userFre-E2TAug-PEratio
Computation0.40 ms (once)55.9 ms (20 rounds)140×
Upload8.3 kB1.68 MB2.0×1022.0 \times10^2
Download6.1 kB1.29 GB2.1×1052.1 \times10^5

Table 17. Per-user cost of distributed Fre-E2T versus a distributed Aug-PE.

C Proof for Semantic Support Protection

We prove Theorem 5 in three steps. First, we argue that for any infrequent text x∗x^* that has at most n∗n^* data points that is rr-close to itself, after subsampling, not too many of its close neighbors in XX will end up in the same cluster, using the classic concentration inequality, and that the cluster will have a small diameter (using the results established in Sec. 6.3). Next, we focus on a single cluster, and argue that conditioned on there are not too many close neighbors to x∗x^* in it, the cluster centroid will be far from x∗x^*. Finally, we show that the DP noise will push the released centroid further away x∗x^*, with a high probability.

Good event B\mathcal{B}. We focus on any cluster BB with index bb in the kk-dimensional space that has accumulated at least hh data points. Note that hh was released in the heavy hitter estimation step with DP. So here, using hh incur no additional privacy cost.

We denote the corresponding dd-dimensional embedding vectors as XB={xi∣hi=b}X_B = \{x_i \mid h_i = b\}. We define event B\mathcal{B} as “Within bucket BB, there are at most 2psn∗2p_sn^* data points that are rr close to x∗x^* and every two data points have distance at most rr”. Lemma 10 follows from the multiplicative Chernoff bound [86] and Lemma 2.

Lemma 10 (Event B\mathcal{B} almost always happens). Within bucket BB of count hh, there are at most 2psn∗2p_sn^* data points that are rr close to x∗x^* and every pair of data points are within distance at most rr. This happens with probability at least

1−exp⁡(−0.38psn∗)−(h2)(f(kLr))k(23)1 - \exp(-0.38p_sn^*) - \binom{h}{2}\left(f\left(\frac{\sqrt{k}L}{r}\right)\right)^k \tag*{(23)}

with ff defined as in (7).

Distance between a centroid and x∗x^*. Conditioned event B\mathcal{B}, we show that no bucket centroid is close to x∗x^*, without DP noise. Recall that each bucket contains hh data points (with h≥τh\ge\tau), so at least h−2psn∗h-2p_sn^* data points in the bucket is at least rr-away from x∗x^*. We take any such xfarx_{\mathrm{far}}, then ∥xfar−x∗∥2≥r\|x_{\mathrm{far}}-x^*\|_2\ge r. We define unit vector u:=xfar−x∗∥xfar−x∗∥2u:=\frac{x_{\mathrm{far}}-x^*}{\|x_{\mathrm{far}}-x^*\|_2}. Now consider any other data point that is far from x∗x^*, written as xfar′x'_{\mathrm{far}}. Let θ\theta be the angle between xfar−x∗x_{\mathrm{far}}-x^* and xfar′−x∗x'_{\mathrm{far}}-x^*. Then we can obtain

cos⁡θ=∥xfar−x∗∥22+∥xfar′−x∗∥22−∥xfar−xfar′∥222∥xfar−x∗∥2∥xfar′−x∗∥2≥12.\cos\theta=\frac{\|x_{\mathrm{far}}-x^*\|_2^2+\|x'_{\mathrm{far}}-x^*\|_2^2-\|x_{\mathrm{far}}-x'_{\mathrm{far}}\|_2^2}{2\|x_{\mathrm{far}}-x^*\|_2\|x'_{\mathrm{far}}-x^*\|_2}\ge\frac{1}{2}.

since and ∥xfar−xfar∗∥2≤r≤min⁡{∥xfar−x∗∥2,∥xfar′−x∗∥2}\lVert x_{\mathrm{far}}-x^{*}_{\mathrm{far}}\rVert_{2}\le r\le\min\{\lVert x_{\mathrm{far}}-x^{*}\rVert_{2},\lVert x'_{\mathrm{far}}-x^{*}\rVert_{2}\} by construction. Therefore for any xfar′x'_{\mathrm{far}}, uT(xfar′−x∗)=rcos⁡θ≥r2u^{T}(x'_{\mathrm{far}}-x^{*})=r\cos\theta\ge\frac{r}{2}. For any xnearx_{\mathrm{near}} such that ∥xnear−x∗∥≤r\lVert x_{\mathrm{near}}-x^{*}\rVert\le r, uT(xnear−x∗)≥−ru^{T}(x_{\mathrm{near}}-x^{*})\ge-r holds automatically. Since there are at least h−2psn∗h-2p_{s}n^{*} far data points, the centroid of BB, written as μ(B)\mu(B), must satisfy

uT(μ(B)−x∗)≥h−6psn∗2hr.(24)u^{T}(\mu(B)-x^{*})\ge\frac{h-6p_{s}n^{*}}{2h}r. \tag*{(24)}

Since h≥τh\ge\tau, ∥μ(B)−x∗∥2≥τ−6psn∗2τr\lVert\mu(B)-x^{*}\rVert_{2}\ge\frac{\tau-6p_{s}n^{*}}{2\tau}r. This means that the distance from x∗x^{*} to μ(B)\mu(B) is dominated by the majority far points.

Effect of DP noise. We consider injecting G∼N(0,(σ∗)2)G\sim\mathcal{N}(0,(\sigma^{*})^{2}) into the centroid μ(B)\mu(B). We define x~=μ(B)+G\tilde{x}=\mu(B)+G, and R=x~−x∗R=\tilde{x}-x^{*}.

Pr⁡[∥x~−x∗∥2≤r]=(2π(σ∗)2)−d/2∫∥R∥2≤rexp⁡(−∥R−(μ(B)−x∗)∥22σ2)dR(25)\Pr[\lVert\tilde{x}-x^{*}\rVert_{2}\le r]=(2\pi(\sigma^{*})^{2})^{-d/2} \int_{\lVert R\rVert_{2}\le r}\exp\left(-\frac{\lVert R-(\mu(B)-x^{*})\rVert_{2}^{2}}{\sigma^{2}}\right)dR \tag*{(25)}

Let R′R' follow the distributed Gaussian distribution of mean ∥μ(B)−x∗∥2e1\lVert\mu(B)-x^{*}\rVert_{2}e_{1} with covariance (σ∗)2Id(\sigma^{*})^{2}I_{d}. By rotation invariance, equation 25 can be computed as

Pr⁡[∥R′∥2≤r]=Pr⁡[∥R′σ∗∥2≤rσ∗]=Fχd2(Λ)(r2(σ∗)2),(26)\Pr[\lVert R'\rVert_{2}\le r]=\Pr\left[\left\lVert\frac{R'}{\sigma^{*}}\right\rVert_{2}\le\frac{r}{\sigma^{*}}\right]=F_{\chi^{2}_{d}(\Lambda)}\left(\frac{r^{2}}{(\sigma^{*})^{2}}\right), \tag*{(26)}

where FF is the cumulative distribution function of non-central chi-squared distribution and Λ=τ−6psn∗2τr\Lambda=\frac{\tau-6p_{s}n^{*}}{2\tau}r. (26) is decreasing in Λ\Lambda; hence, it is decreasing in ∥μ(B)−x∗∥2\lVert\mu(B)-x^{*}\rVert_{2}. This in turn motivates Lemma 10, where have we bounded ∥μ(B)−x∗∥2\lVert\mu(B)-x^{*}\rVert_{2} from below.

The overall failure probability follows from a union bound over (23) and (26). Plugging in σ∗=σh\sigma^{*}=\frac{\sigma}{h}, where hh is the subsampled count of items landed in the heavy hitter cluster of x∗x^{*} (namely, the denominator for the centroid computation), we obtain Theorem 5. We note that hh is already released through the differentially private heavy hitter histogram perturbed with the random subsampling noises; hence, using hh incurs no additional privacy cost.

To convert Theorem 5 to a meaningful bound on the text-level semantic protection, one also needs to quantify the error during inverting the vector to a text, namely, the L2L_{2} distance ∥μ(B)−E(v~)∥\lVert\mu(B)-E(\tilde{v})\rVert, where v~\tilde{v} is the text inverted from centroid μ(B)\mu(B). This can be difficult in general. However, based on our empirical observations from Figure 4, the error is not large and text-level SSP is preserved.

Remark on distributed implementation. Real-world distributed implementation of securely aggregating DP noises relies on integer-valued implementations, such as discrete Gaussian [24, 64] (used in this paper), or symmetric Skellam [4] (difference of two Poisson variables). In both cases, for moderate noise levels or in moderately high dimension, as is the case in our problem, the distribution of the squared distance ∥μ^+discrete noise−x∗∥22\lVert\hat{\mu}+\text{discrete noise}-x^{*}\rVert_{2}^{2} can still be approximated by a noncentral chi-squared distribution with the same degrees of freedom dd and the almost the same noncentrality λ=r2/v\lambda=r^{2}/v, where vv is the per-coordinate variance of the mechanism.

Now, we consider Algorithm 2, where each user independently contributes discrete Gaussian noise NZ(0,σdisc2)\mathcal{N}_{\mathbb{Z}}(0,\sigma_{\mathrm{disc}}^{2}) to the discretized local vector. The sum of hh independent discrete Gaussian noises of variance σdisc2\sigma_{\mathrm{disc}}^{2} is close to a single discrete Gaussian noise of variance hσdisc2h\sigma_{\mathrm{disc}}^{2}. Normalizing by β/h\beta/h (here β≪1\beta\ll1), the overall variance in the resulting centroid is β2σdisc2h\frac{\beta^{2}\sigma_{\mathrm{disc}}^{2}}{h}. Hence, the conclusion of semantic support protection for the distributed implementation of Fre-E2T, Algorithm 2, is similar to what we have derived above for a continuous Gaussian, with an algebraic substitution, presented as follows.

For any x∗∈Xx^{*}\in X such that there are at most tt data points from XX that has distance at most rr to x∗x^{*} in XX and any DP centroid μ^\hat{\mu} with hh items sampled into the cluster, Algorithm 2 outputs the centroid μ^\hat{\mu} such that ∥μ^−x∗∥2<ψr\lVert\hat{\mu}-x^{*}\rVert_{2}<\psi r with probability

δ∗≲(h2)(f(kLr))k+e−0.38pst+Fχd2(Λ)(ψ2r2hβ2σdisc2).(27)\delta^{*}\lesssim\binom{h}{2}\left(f\left(\frac{\sqrt{k}L}{r}\right)\right)^{k}+e^{-0.38p_{s}t}+F_{\chi^{2}_{d}(\Lambda)}\left(\frac{\psi^{2}r^{2}h}{\beta^{2}\sigma_{\mathrm{disc}}^{2}}\right). \tag*{(27)}

Extensions

Each user has multiple data points.

Previously, we have considered the setting in which each user has exactly 1 data point. Now we discuss the extension when each user has more than 1 data points.

Naive solution via composition. During the heavy-hitter estimation, we can introduce a public threshold to restrict the number of buckets that each user can contribute to, say cc. For each bucket, we make each user contribute at most one of its embedding vectors. The overall privacy guarantee then follows from the composition argument, we can directly multiply the overall ϵ\epsilon and δ\delta by cc. Finding the optimal threshold cc could be an interesting future work direction [39, 58]

Naive solution via black-box group DP. The above naive solution forbids one user to submit to the same bucket index multiple times. This may hurt utility considering that some queries (associated with certain bucket indices are more common). Let’s say each user has at most mm data points. A straight-forward group DP argument gives (m⋅emϵ−1eϵ−1,δ)(m\cdot\frac{e^{m\epsilon}-1}{e^{\epsilon}-1},\delta)-DP, where ϵ\epsilon and δ\delta are the original privacy parameters of the algorithm when each user has exactly one data point. When ϵ\epsilon is not close to 0, the factor of emϵ−1eϵ−1\frac{e^{m\epsilon}-1}{e^{\epsilon}-1} can be very large.

A bespoke analysis. Next, we discuss a more bespoke analysis. Let the group size be ll (originally, we have considered l=1l=1). We first focus on the heavy hitter estimation phase. For now, we consider two databases consisting of copies of the same index. Dataset XX has mm copies while dataset X′X' has m−lm-l copies. The sampled count VV and V′V' for XX and X′X' then follows the binomial distribution Bin(m,ps)Bin(m,p_{s}) and Bin(m−l,ps)Bin(m-l,p_{s}), respectively.

Pr⁡[V′=v]Pr⁡[V=v]=(m−lv)psv(1−ps)m−v−l(mv)psv(1−ps)m−v,(28)\frac{\Pr[V'=v]}{\Pr[V=v]}=\frac{\binom{m-l}{v}p_{s}^{v}(1-p_{s})^{m-v-l}}{\binom{m}{v}p_{s}^{v}(1-p_{s})^{m-v}}, \tag*{(28)}

for any v∈Nv\in\mathbb{N}, v≤m−lv\le m-l. We can obtain

Pr⁡[V′=v]Pr⁡[V=v]=(1−ps)l∏j=0l−1m−jm−v−j,(29)\frac{\Pr[V'=v]}{\Pr[V=v]}=(1-p_{s})^{l}\prod_{j=0}^{l-1}\frac{m-j}{m-v-j}, \tag*{(29)}

which collapses to (1−ps)lmm−v(1-p_{s})^{l}\frac{m}{m-v} when l=1l=1, i.e., the expression that appears in the original [15]. We want (29) to be bounded within [e−lϵHH,elϵHH][e^{-l\epsilon_{HH}},e^{l\epsilon_{HH}}], with a high probability. The lower bound is easy, it suffices to make 1−ps≥e−ϵHH1-p_{s}\ge e^{-\epsilon_{HH}}. For the upper bound, it suffices to make sure that

(1−ps)m−jm−v−j≤eϵHH,(30)(1-p_{s})\frac{m-j}{m-v-j}\le e^{\epsilon_{HH}}, \tag*{(30)}

for each j=0,1,…,l−1j=0,1,\ldots,l-1. It suffices to ensure that

(1−ps)m−l+1m−v−l+1≤eϵHH(31)(1-p_{s})\frac{m-l+1}{m-v-l+1}\le e^{\epsilon_{HH}} \tag*{(31)}

holds, which is equivalent to

v≤q(m−l+1),(32)v \le q(m-l+1), \tag*{(32)}

where we have set q:=1−(1−ps)e−εHHq := 1 - (1-p_s)e^{-\varepsilon_{HH}}. Since vv could take value in 0,1,…,m0,1,\ldots,m, the δl\delta_l can be written as

δl=Pr⁡[Bin⁡(m,ps)≥max⁡(τ,q(m−l+1))](33)\delta_l = \Pr\left[\operatorname{Bin}(m,p_s) \ge\max\left(\tau,q(m-l+1)\right)\right] \tag*{(33)}

When l=1l=1, δ1=Pr⁡[Bin⁡(m,ps)≥max⁡(τ,qm)]\delta_1=\Pr[\operatorname{Bin}(m,p_s)\ge\max(\tau,qm)], which is the same as in [15]. As a sanity check, we note that δl\delta_l is increasing in ll—i.e., it is more likely for the binomial variable to be lower bounded by a smaller value.

There are two cases to consider. q(m−l+1)≤τq(m-l+1)\le\tau or q(m−l+1)≥τq(m-l+1)\ge\tau; equivalently, m≤τq+l−1m\le\frac{\tau}{q}+l-1 or m≥τq+l−1m\ge\frac{\tau}{q}+l-1

Case I: m≤τq+l−1m\le\frac{\tau}{q}+l-1. We can upper bound Pr⁡[Bin⁡(m,ps)≥τ]\Pr[\operatorname{Bin}(m,p_s)\ge\tau] by Pr⁡[Bin⁡(τq+l−1,ps)≥τ]\Pr[\operatorname{Bin}(\frac{\tau}{q}+l-1,p_s)\ge\tau].

Case II: m≥τq+l−1m\ge\frac{\tau}{q}+l-1. In this case, we upper bound Pr⁡[Bin⁡(m,ps)≥qm]\Pr[\operatorname{Bin}(m,p_s)\ge qm]. We upper bound this probability by the Chernoff bound, that is, the probability that at least qmqm out of mm independent trials are successful, where each trial succeeds with probability ps<qp_s<q. In expectation, the number of success is psm<qmp_sm<qm, therefore, the Chernoff bound error decreases as mm increases—when mm is larger, it becomes more difficult for the off-mean event to happen. Therefore, it suffices to consider the boundary case m=τq+l−1m=\frac{\tau}{q}+l-1, which also happens to be the worst case above. We obtain

δl=Pr⁡[Bin⁡(τq+l−1,ps)≥q⋅(τq+l−1)](34)\delta_l=\Pr\left[\operatorname{Bin}\left(\frac{\tau}{q}+l-1,p_s\right)\ge q\cdot\left(\frac{\tau}{q}+l-1\right)\right] \tag*{(34)}
≤Pr⁡[Bin⁡(τq+l−1,ps)≥τ](35)\le\Pr\left[\operatorname{Bin}\left(\frac{\tau}{q}+l-1,p_s\right)\ge\tau\right] \tag*{(35)}
≤exp⁡(−mlD(τqml∥ps)),(36)\le\exp\left(-m_lD\left(\frac{\tau}{qm_l}\middle\|p_s\right)\right), \tag*{(36)}

with ml=τq+l−1m_l=\frac{\tau}{q}+l-1, and DD stands for the KL divergence between two Bernoulli trials. The first inequality holds since q(l−1)≥0q(l-1)\ge0 (this formalization unifies Case II and Case I); the second inequality is obtained from the Markov’s inequality and then solving for the optimal order, similar to [15].

In summary, when two datasets differ by ll copies of the same index, the overall εHH\varepsilon_{HH} for heavy hitter estimation multiplies by ll while the overall δHH\delta_{HH} can be computed via the union bound:

δHH=max⁡{Δj}j=1l∑j=1lδj,(37)\delta_{HH}=\max_{\{\Delta_j\}_{j=1}^{l}}\sum_{j=1}^{l}\delta_j, \tag*{(37)}

where δj\delta_j is computed via (36), and the maximum is taken over all possible sets of {Δj}j=1l\{\Delta_j\}_{j=1}^{l} such that each Δj∈N\Delta_j\in\mathbb{N} and that ∑j=1lΔj=l\sum_{j=1}^{l}\Delta_j=l. In particular, if all data points of a user are the same, then exactly one Δj=l\Delta_j=l, and the rest are 0.

Next, we discuss the privacy guarantee for the DP centroid computation. When all ll data points are in one cluster, the sensitivity multiplies by ll, so does the failure probability (since each data in the bucket point may fail to stay close to the different data point in the same bucket). We can apply Lemma 2 and Theorem 3 with the sensitivity multiplied by ll to obtain εagg,l\varepsilon_{agg,l} and δagg,l\delta_{agg,l} for any group size ll.

The overall parameters are expressed as

εagg=max⁡{Δj}j=1l∑j=1lεagg,j,(38)\varepsilon_{agg}=\max_{\{\Delta_j\}_{j=1}^{l}}\sum_{j=1}^{l}\varepsilon_{agg,j}, \tag*{(38)}
δagg=max⁡{Δj}j=1l∑j=1lδagg,j.(39)\delta_{agg}=\max_{\{\Delta_j\}_{j=1}^{l}}\sum_{j=1}^{l}\delta_{agg,j}. \tag*{(39)}

where the maximum is taken over all possible sets of {Δj}j=1l\{\Delta_j\}_{j=1}^{l} such that each Δj∈N\Delta_j\in\mathbb{N} and that ∑j=1lΔj=l\sum_{j=1}^{l}\Delta_j=l. In particular, if all data points of a user are the same, then exactly one Δj=l\Delta_j=l, and the rest are 0.

Bounded Differential Privacy

Our analysis in Section 5 focuses on the unbounded DP model [40], where two datasets are called neighboring if one can be obtained from the other by adding or removing exactly one record in the dataset. Now we discuss the privacy guarantee under the bounded DP model [41], where the two datasets are called neighboring if one can be obtained from the other by altering exactly one record in the dataset (this also captures the scenario when one user’s record is zeroed out). We provide the full argument for completeness.

We say two datasets D,D′∈DD,D'\in\mathcal{D} are unbounded-adjacent, denoted D∼uD′D\sim_u D', if D′D' can be obtained from DD by adding or removing exactly one record; i.e., there exists x∈Xx\in\mathcal{X} such that either D′=D∪{x}D'=D\cup\{x\} or D=D′∪{x}D=D'\cup\{x\}. Accordingly, we say two datasets D,D′∈DD,D'\in\mathcal{D} are bounded-adjacent, denoted D∼bD′D\sim_bD', if they have the same size and differ in exactly one record. Equivalently, there exist a dataset CC and records x,x′∈Xx,x'\in\mathcal{X} such that D=C∪{x},D′=C∪{x′}D=C\cup\{x\},D'=C\cup\{x'\}.

Lemma 11 (Unbounded DP to bounded DP parameter conversion [42]). If a mechanism MM is (ε,δ)(\varepsilon,\delta)-DP with respect to unbounded adjacency ∼u\sim_u, then MM is (2ε,(1+eε)δ)(2\varepsilon,(1+e^\varepsilon)\delta)-DP with respect to bounded adjacency ∼b\sim_b.

Proof. Assume MM is (ε,δ)(\varepsilon,\delta)-DP w.r.t. ∼u\sim_u. Fix any pair D∼bD′D\sim_bD'. By the definition of bounded adjacency, there exist a dataset CC and records x,x′∈Xx,x'\in\mathcal{X} such that D=C∪{x}D=C\cup\{x\} and D′=C∪{x′}D'=C\cup\{x'\}. Note that D∼uCD\sim_u C (remove xx) and C∼uD′C\sim_u D' (add x′x'). Let S⊆YS\subseteq\mathcal{Y} be any measurable set. Applying (ε,δ)(\varepsilon,\delta)-DP w.r.t. ∼u\sim_u to the pair (D,C)(D,C) gives

Pr⁡[M(D)∈S]≤eεPr⁡[M(C)∈S]+δ.(40)\Pr[M(D)\in S]\le e^\varepsilon\Pr[M(C)\in S]+\delta. \tag*{(40)}

Applying (ε,δ)(\varepsilon,\delta)-DP w.r.t. ∼u\sim_u to the pair (C,D′)(C,D') gives

Pr⁡[M(C)∈S]≤eεPr⁡[M(D′)∈S]+δ.(41)\Pr[M(C)\in S]\le e^\varepsilon\Pr[M(D')\in S]+\delta. \tag*{(41)}

Substituting (41) into (40) yields

Pr⁡[M(D)∈S]≤eε(eεPr⁡[M(D′)∈S]+δ)+δ(42)\Pr[M(D)\in S]\le e^\varepsilon\left(e^\varepsilon\Pr[M(D')\in S]+\delta\right)+\delta \tag*{(42)}
=e2εPr⁡[M(D′)∈S]+(eε+1)δ.(43)= e^{2\varepsilon}\Pr[M(D')\in S]+(e^\varepsilon+1)\delta. \tag*{(43)}

This is exactly (2ε,(1+eε)δ)(2\varepsilon,(1+e^\varepsilon)\delta)-DP w.r.t. bounded adjacency. □\square

Note that the above conversion is completely black box. As a result, we can also plug in the privacy parameters obtained from Section D.0.1 and obtain the corresponding DP guarantees under bounded adjacency.

Other Threat Models

When the two servers are malicious during heavy hitter estimation, the tagging server needs to provide a zero-knowledge proof on not altering the protocol, as is done in [98]. When users who submit the vectors are malicious in the aggregation phase [21], or equivalently, malicious users (say, there are nmaln_{\mathrm{mal}} of them) may submit indices computed from certain embedding vectors of interest, attempting to learn whether there exist other users with similar text embeddings (even such embeddings may not be frequent among the user population), we can make a similar argument. From the perspective of the targeted users, this act weakens their privacy protection by enforcing a smaller cut-off threshold of heavy-hitter identification—decreasing from τ\tau to τ−nmal\tau-n_{\mathrm{mal}} (see equation 5). This can be resolved by using a MPC protocol to ensure that the random submission (determined by a random coin) is strictly executed. In this case, the malicious users’ data serve as dummies to enhance the privacy protection. We leave further measures to defend against such malicious acts to future work. MPC protocols specifically designed for DP [48, 50, 67, 97] or relaxed privacy frameworks [102] may also be useful.

Simulation-Based Security Sketch

We provide a simulation-based security sketch for the distributed implementation in Algorithm 2. This argument is not intended as a new cryptographic primitive; rather, it shows that, under the same assumptions as Section 2 and using the cited primitives as black boxes, the distributed protocol reveals no information beyond the explicitly released differentially private summary and the unavoidable metadata described below.

Adversarial model. Let SsynS_{\mathrm{syn}} denote the synthesis server and StagS_{\mathrm{tag}} denote the tagging server. We consider static probabilistic polynomial-time semi-honest adversaries: corrupted parties follow the protocol but may try to infer additional information from their views. We assume SsynS_{\mathrm{syn}} and StagS_{\mathrm{tag}} do not collude. User-to-server submissions are sent through an anonymous channel, modeled as an ideal shuffler that reveals only the multiset of messages delivered to the recipient and not the sender identities or links between a user’s messages in different phases. We consider corruption of SsynS_{\mathrm{syn}}, corruption of StagS_{\mathrm{tag}}, or corruption of a subset of users. If one also allows corrupted users to collude with SsynS_{\mathrm{syn}}, then the ideal leakage must include the multiplicity of the VOPRF tags known to those corrupted users; our main statement below excludes such user-server collusion.

Ideal functionality. Define an ideal functionality FD−Fre2T\mathcal{F}_{\mathrm{D-Fre2T}} parameterized by the public parameters

(E,Z,L,{oj}j=1k,ps,τ,λ,γ,σ,β).(E,Z,L,\{o_j\}_{j=1}^{k},p_s,\tau,\lambda,\gamma,\sigma,\beta).

On inputs v1,…,vNv_1,\ldots,v_N, the functionality computes xi=E(vi)x_i=E(v_i), the projected bucket index bib_i, the sampled participation coin coin⁡i∼Bernoulli⁡(ps)\operatorname{coin}_i\sim\operatorname{Bernoulli}(p_s), and an opaque tag hih_i for each bucket. Equal buckets receive equal tags, and distinct buckets receive computationally independent tags. The functionality then runs the same sample-and-threshold heavy-hitter step, including the dummy submissions drawn from TSDLap⁡(λ,γ)\operatorname{TSDLap}(\lambda,\gamma), and outputs the heavy-hitter tag set HH and counts C={ch}h∈HC=\{c_h\}_{h\in H}. For each h∈Hh\in H, it computes the quantized, locally discrete-Gaussian-perturbed sum

Th=∑i:hi=h, coin⁡i=1(Qβ(xi)+ξi),T_h=\sum_{i:h_i=h,\ \operatorname{coin}_i=1}(Q_\beta(x_i)+\xi_i),

where the coordinates of ξi\xi_i are sampled independently from the discrete Gaussian distribution used in Algorithm 2. It outputs the released centroid

μ^h=βchTh.\hat{\mu}_h=\frac{\beta}{c_h}T_h.

The public output is

Out⁡=(H,C,{μ^h}h∈H).\operatorname{Out}=(H,C,\{\hat{\mu}_h\}_{h\in H}).

The synthesis server’s ideal leakage additionally contains the sub-threshold count-of-counts

LA<τ={mq}q=1τ−1,\mathcal{L}^{<\tau}_A=\{m_q\}_{q=1}^{\tau-1},

where mqm_q is the number of received non-heavy opaque tags with multiplicity qq, after dummy insertion. This captures exactly the information observed by SsynS_{\mathrm{syn}} from non-released pseudonymous tags; the individual tag names themselves carry no semantic information. The tagging server’s ideal leakage consists of the number of VOPRF invocations, the public output, and the public heavy-tag oracle induced by its VOPRF key. This oracle captures the fact that a tagging server holding the VOPRF key can test guessed bucket indices against the public released heavy tags, but it still does not learn which users produced those tags.

Security statement. Assume that (i) the VOPRF realizes its standard oblivious and verifiable PRF functionality, (ii) the anonymous channel realizes an ideal shuffler, and (iii) the secure aggregation protocol realizes an ideal tagged-sum functionality that reveals only the aggregate sum for each released tag. Then, for every PPT semi-honest adversary A\mathcal{A} corrupting either SsynS_{\mathrm{syn}}, StagS_{\mathrm{tag}}, or an arbitrary subset of users, there exists a PPT simulator Sim⁡\operatorname{Sim} such that

View⁡AΠ(v1,…,vN)≈cSim⁡(aux⁡A,Out⁡,LA),\operatorname{View}^{\Pi}_{\mathcal{A}}(v_1,\ldots,v_N)\approx_c\operatorname{Sim}(\operatorname{aux}_{\mathcal{A}},\operatorname{Out},\mathcal{L}_{\mathcal{A}}),

where Π\Pi is Algorithm 2, aux⁡A\operatorname{aux}_{\mathcal{A}} contains the inputs and randomness of corrupted users, and LA\mathcal{L}_{\mathcal{A}} is the ideal leakage defined above for the corrupted party type. The indistinguishability is computational, with negligible distinguishing advantage in the cryptographic security parameter.

Proof sketch. We prove the statement by a sequence of standard hybrids.

Hybrid 0: the real execution. This is the execution of Algorithm 2. Each user locally computes xi=E(vi)x_i=E(v_i), projects and buckets it to obtain bib_i, obtains a VOPRF tag hih_i, submits hih_i with probability psp_s, and, if hi∈Hh_i\in H, secret-shares a locally perturbed vector tagged by hih_i.

Hybrid 1: replace VOPRF by its ideal functionality. Replace the real VOPRF interface between each user and server with an ideal VOPRF call. By the VOPRF security guarantee, StagS_{\mathrm{tag}}’s view of each call can be simulated from the number of invocations: the blinded inputs are indistinguishable from random protocol messages and reveal neither bib_i nor the output hih_i. Users with the same bucket obtain the same PRF tag, whereas the tags for distinct buckets are computationally indistinguishable from independent random strings to any party not holding the VOPRF key. Verifiability guarantees that honest users accept only tags generated under the committed VOPRF key. Therefore, this replacement changes the adversary’s view only negligibly.

Hybrid 2: replace user submissions by an ideal shuffler. Replace each user-to-server communication channel by an ideal anonymous channel. The recipient learns only the multiset of submitted tags or tagged shares, not the identities of the senders and not whether two messages in different phases came from the same user. Thus, the synthesis server’s heavy-hitter-phase view is completely determined by the multiset

MHH={hi:coin⁡i=1}∪Dummy,M_{\mathrm{HH}} = \{h_i : \operatorname{coin}_i = 1\} \cup\mathrm{Dummy},

and the centroid-phase view is determined by the multiset of tagged shares for tags in HH. This is exactly the metadata included in LA<τ\mathcal{L}_{A}^{<\tau}, together with the released heavy tags HH and counts CC.

Hybrid 3: simulate non-heavy pseudonymous tags. For tags whose multiplicity is below τ\tau, SsynS_{\mathrm{syn}} sees only opaque pseudorandom strings and their multiplicities. Since the VOPRF tags for unknown bucket indices are pseudorandom, the simulator samples fresh random strings and assigns exactly mqm_q of them multiplicity qq, for each q∈{1,…,τ−1}q \in\{1,\ldots,\tau-1\}. This produces the same distribution as the real view up to the PRF distinguishing advantage. The dummy submissions are accounted for in the same count-of-counts leakage. The DP analysis in Section 6.3 then bounds the information contained in LA<τ\mathcal{L}_{A}^{<\tau}.

Hybrid 4: replace secure aggregation by ideal tagged sums. For each heavy tag h∈Hh \in H, let GhG_h be the set of sampled users with tag hh. Each such user contributes an integer vector

x~i=Qβ(xi)+ξi\widetilde{x}_i = Q_{\beta}(x_i) + \xi_i

and sends additive secret shares of x~i\widetilde{x}_i to the two non-colluding servers. Consider a corrupted SsynS_{\mathrm{syn}}. The share of every honest user’s vector received by SsynS_{\mathrm{syn}} is uniformly random over the aggregation group, independent of x~i\widetilde{x}_i. Given the ideal output Th=∑i∈Ghx~iT_h = \sum_{i \in G_h} \widetilde{x}_i, the simulator samples all shares received by SsynS_{\mathrm{syn}} uniformly at random and programs the aggregate share sent from StagS_{\mathrm{tag}} to make the reconstructed sum equal ThT_h. This is identically distributed to the real execution because additive secret sharing is perfectly private against either single server. The case of a corrupted StagS_{\mathrm{tag}} is symmetric. If an off-the-shelf SecAgg protocol is used instead of two-server additive sharing, the same step follows from the simulation security of the SecAgg functionality.

Hybrid 5: simulate users’ views. A corrupted user sees only its own input, local randomness, VOPRF response, participation coin, local noise, generated shares, the broadcast (H,C)(H,C), and the public output. The simulator can reproduce this view directly from the corrupted user’s input and randomness plus Out\mathrm{Out}. Because users receive no other users’ messages, no additional simulation is required.

After these replacements, the transcript is generated entirely from the corrupted parties’ inputs and randomness, the public output Out\mathrm{Out}, and the leakage LA\mathcal{L}_{A}. Hence the real and ideal executions are computationally indistinguishable.

The simulation argument shows that the cryptographic implementation does not leak raw texts, bucket indices, or individual embeddings beyond the ideal released objects above. Therefore the end-to-end privacy of the distributed protocol reduces to the privacy of the ideal release. By Lemma 6 and Theorem 7, the distributed heavy-hitter step and the distributed discrete Gaussian centroid step satisfy the DP parameters analyzed in Section 6.3. Composing these components and adding the high-probability sensitivity term yields Theorem 8.

References

  1. [1]Martin Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. 2016. Deep Learning with Differential Privacy. In CCS.
  2. [2]John M. Abowd and Ian M. Schmutte. 2019. An Economic Analysis of Privacy Protection and Statistical Accuracy as Social Choices. AER (2019).DOI
  3. [3]Alessandro Acquisti, Laura Brandimarte, and George Loewenstein. 2015. Privacy and human behavior in the age of information. Science 347, 6221 (2015), 509–514. doi:10.1126/science.aaa1465DOI
  4. [4]Naman Agarwal, Peter Kairouz, and Ziyu Liu. 2021. The skellam mechanism for differentially private federated learning. In NeurIPS.
  5. [5]Jōel Blumberg, Anil Shelat, and Ivan V. Lëk? 2008. Collision-Free Protocols in the Mediated Model. In CRYPTO.
  6. [6]Miguel E. Andrés, Nicolás E. Bordenabe, Konstantinos Chatzikokolakis, and Catuscia Palamidessi. 2013. Geo-indistinguishability: Differential Privacy for Location-Based Systems. In CCS.DOI
  7. [7]Meenatchi Sundaram Muthu Selva Annamalai, Emiliano De Cristofaro, and Peter Kairouz. 2026. CLOWPTRA: Extracting Private Information from LLM Insights. arXiv:2603.09781 [cs.CR] https://arxiv.org/abs/2603.09781
  8. [8]Anthropic. 2025. Claude 3.7 Sonnet System Card. https://www-cdn.anthropic.com/9ff93df8af45c932415d335c888528ef47f1210e.pdf. Accessed 2026-02-04.
  9. [9]Apple. 2025. Understanding Aggregate Trends for Apple Intelligence Using Differential Privacy. Apple ML Research (2025).
  10. [10]Apple Differential Privacy Team. 2017. Learning with Privacy at Scale. White Paper. Apple.
  11. [11]Ionut Arghire. 2022. Samsung Sued Over Recent Data Breaches. https://www.securityweek.com/samsung-sued-over-recent-data-breaches/.
  12. [12]Borja Balle, James Bell-Clark, Albert Cheu, Adria Gascon, Jonathan Katz, Mariana Raykova, Philippe Schoppmann, and Thomas Steinke. 2025. Hash-Prune-Invert: Improved DP Heavy-Hitter Detection in the Two-Server Model. In SP.
  13. [13]Borja Balle and Yu-Xiang Wang. 2018. Improving the Gaussian Mechanism for Differential Privacy. In ICML.
  14. [14]James Bell, Adrià Gascón, Balih Ghazi, Ravi Kumar, Pasin Manurangsi, Mariana Raykova, and Phillip Schoppmann. 2022. Distributed, Private, Sparse Histograms in the Two-Server Model. In CCS.DOI
  15. [15]Akash Bharadwaj and Graham Cormode. 2022. Sample and Threshold Differential Privacy: Histograms and Applications. AISTATS (2022).arxiv.org/abs/2112.05693
  16. [16]Andrea Bittau, Úlfar Erlingsson, Petros Maniatis, Ilya Mironov, Ananth Raghunathan, David Lie, Mitch Rudominer, Udi? Y? 2017. Prochlo: Strong Privacy for Analytics in the Crowd. In SOSP.DOI
  17. [17]Avrim Blum, Cynthia Dwork, Frank McSherry, and Kobbi Nissim. 2005. Practical Privacy: The SuLQ Framework. In PODS.
  18. [18]Jonas Böhler and Florian Kerschbaum. 2020. Secure Multi-party Computation of Differentially Private Median. In USENIX Security.
  19. [19]Rishi Bommasani, Sitao Wu, and Xavier S. Schoenfeld. 2019. Towards Private Synthetic Text Generation. In NeurIPS Workshop on Machine Learning with Guarantees.
  20. [20]Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H. Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. 2017. Practical Secure Aggregation for Privacy-Preserving ML. In CCS.arxiv.org/abs/1902.01046
  21. [21]Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H. Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. 2017. Practical Secure Aggregation for Privacy-Preserving ML. In CCS.
  22. [22]Brave Software, Inc. 2025. How do I use Brave Leo? https://support.brave.app/hc/en-us/articles/20958609786637-How-do-I-use-Brave-Leo. Updated 2025-07-29. Accessed: 2026-02-04.
  23. [23]U.S. Census. Bureau. 2012. 2010 Census of Population and Housing, Technical Documentation. https://usa.ipums.org/usa/resources/voliii/pubdocs/2010/Technical%20Documentation.pdf.
  24. [24]Clément L. Canonne, Gautam Kamath, and Thomas Steinke. 2020. The discrete Gaussian for differential privacy. In NeurIPS.
  25. [25]Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagielski, Ariel Herbert-Voss, Katherine Lee, Adam Roberts, Tom Brown, Nicholas Roy, Dawn Song, et al. 2021. Extracting Training Data from Large Language Models. In USENIX Security 21.
  26. [26]S. Casper, J. Lin, D. Hadfield-Menell, and D. Krueger. 2023. Open Problems and Fundamental Limitations of Reinforcement Learning from Human Feedback. In TMLR.arxiv.org/abs/2307.15217
  27. [27]Alisa Chang, Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. 2021. Locally Private k-Means in One Round. In ICML. 1441–1451.arxiv.org/abs/2104.09734
  28. [28]Wei-Ning Chen, Ayfer Ozgur, and Peter Kairouz. 2022. The Poisson Binomial Mechanism for Unbiased Federated Learning with Secure Aggregation. In icml.arxiv.org/abs/2207.09916
  29. [29]Albert Cheu, Artem Lagzdin, Brett McLarnon, Daniel Ramage, Katharine Daly, Marco Gruteser, Peter Kairouz, Rakshita Tandon, Stanislav Chiknavaryan, Timon Van Overveldt, and Zoe Gong. 2025. Toward provably private analytics and insights into GenAI use. arXiv:2510.21684 [cs.CR] https://arxiv.org/abs/2510.21684
  30. [30]Albert Cheu, Adam Smith, Jonathan Ullman, David Zeber, and Maxim Zhilyaev. 2019. Distributed Differential Privacy via Shuffling. In EUROCRYPT.DOI
  31. [31]Eli Chien, Yuzheng Hu, Ryan McKenna, Shanshan Wu, Zheng Xu, and Peter Kairouz. 2026. MAPLE: Metadata Augmented Private Language Evolution. arXiv:2603.19258 [cs.CL] https://arxiv.org/abs/2603.19258
  32. [32]Henry Corrigan-Gibbs and Dan Boneh. 2017. Prio: Private, robust, and scalable computation of aggregate statistics. In NSDI.
  33. [33]Sanjoy Dasgupta and Anupam Gupta. 2003. An Elementary Proof of a Theorem of Johnson and Lindenstrauss. Random Struct. Algorithms (2003).
  34. [34]Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S. Mirrokni. 2004. Locality-Sensitive Hashing Scheme Based on p-Stable Distributions. In SoCG.DOI
  35. [35]Alex Davidson, Peter Snyder, E. B. Quirk, Joseph Genereux, Benjamin Livshits, and Hamed Haddadi. 2022. STAR: Secret Sharing for Private Threshold Aggregation. In CCS.DOI
  36. [36]Soham De, Leonard Berrada, Jamie Hayes, Samuel L Smith, and Borja Balle. 2022. Unlocking High-Accuracy Differentially Private Image Classification through Scale. arXiv preprint arXiv:2204.13650 (2022).arxiv.org/abs/2204.13650
  37. [37]Adrien Desfontaines, James Voss, Bryant Gipson, and Chinmoy Mandayam. 2022. Differentially Private Partition Selection. PoPETS (2022).
  38. [38]Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. 2017. Collecting telemetry data privately. Neu rIPS (2017).
  39. [39]Wei Dong, Juanyu Fang, Ke Yi, Yuqiao Tao, and Ashwin Machanavajjhala. 2022. R2T: Instance-optimal Truncation for Differentially Private Query Evaluation with Foreign Keys. In Proceedings of the 2022 International Conference on Management of Data. 759–772.
  40. [40]Cynthia Dwork. 2006. Differential privacy. In ICALP. 1–12.
  41. [41]Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. 2006. Calibrating Noise to Sensitivity in Private Data Analysis. In TCC.
  42. [42]Cynthia Dwork and Aaron Roth. 2014. The Algorithmic Foundations of Differential Privacy. FTCS (2014).
  43. [43]Úlfar Erlingsson, Vasisai Pihur, and Aleksandra Korolova. 2014. RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response. In CCS.
  44. [44]Alexandre Evfimievski, Ramakrishnan Srikant, Rakesh Agrawal, and Johannes Gehrke. 2002. Privacy preserving mining of association rules. In KDD. 217–228.
  45. [45]Oluwaseyi Feyisetan, Borja Balle, Thomas Drake, and Tom Diethe. 2020. Privacy- and Utility-Preserving Textual Analysis via Calibrated Multivariate Perturbations. In WSDM.
  46. [46]James Flemings and Murali Annavaram. 2024. Differentially Private Knowledge Distillation via Synthetic Text Generation. In ACL Findings.arxiv.org/abs/2403.00932
  47. [47]James Flemings, Meisam Razaviyayn, and Murali Annavaram. 2024. Differentially Private Next-Token Prediction of Large Language Models. In ACL.
  48. [48]Olive Franzese, Congyu Fang, Radhika Garg, Somesh Jha, Nicolas Papernot, Xiao Wang, and Adam Dziedzic. 2025. Secure Noise Sampling for Differentially Private Collaborative Learning. In CCS.DOI
  49. [49]Michael H. Freiman, Amy D. Lauger, and Jerome P. Reiter. 2021. Formal Privacy and Synthetic Data for the American Community Survey. Working Paper. U.S. Census Bureau. https://www.census.gov/library/working-papers/2018/adm/formal-privacy-synthetic-data-acs.html Pre-publication research report.
  50. [50]Yucheng Fu and Tianhao Wang. 2024. Benchmarking Secure Sampling Protocols for Differential Privacy. In CCS.DOI
  51. [51]Arun Ganesh, Brendan McMahan, Milad Nasr, Thomas Steinke, and Abhradeep Thakurta. 2025. Hush! Protecting Secrets During Model Training: An Indistinguishability Approach.arxiv.org/abs/2506.00201
  52. [52]Gemini Team. 2023. Gemini: A Family of Highly Capable Multimodal Models. arXiv preprint arXiv:2312.11805 (2023). https://arxiv.org/abs/2312.11805
  53. [53]Aristides Gionis, Piotr Indyk, and Rajeev Motwani. 1999. Similarity Search in High Dimensions via Hashing. In VLDB.
  54. [54]Briland Hitaj, Giuseppe Ateniese, and Fernando Perez-Cruz. 2017. Deep Models Under the GAN: Information Leakage from Collaborative Deep Learning. In CCS.
  55. [55]Charlie Hou, Akshat Shrivastava, Hongyuan Zhan, Rylan Conway, Trang Le, Adithya Sagar, Giulia Fanti, and Daniel Lazar. 2024. Pre-Text: training language models on private federated data in the age of LLMs. In ICML.arxiv.org/abs/2406.02958
  56. [56]Charlie Hou, Mei-Yu Wang, Yige Zhu, Daniel Lazar, and Giulia Fanti. 2025. Private Federated Learning using Preference-Optimized Synthetic Data. In ICML.arxiv.org/abs/2504.16438
  57. [57]Edward J. Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. 2022. LoRA: Low-Rank Adaptation of LLMs. In ICLR.
  58. [58]Yihua Hu, Hao Ding, and Wei Dong. 2025. N2E: A General Framework to Reduce Node-Differential Privacy to Edge-Differential Privacy for Graph Analytics. Proc. ACM Manag. Data 3, 6 (Dec. 2025).
  59. [59]Piotr Indyk and Rajeev Motwani. 1998. Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. In STOC.
  60. [60]Yuval Ishai, Arpita Patra, Sikhar Patranabis, Divya Ravi, and Akshayaram Srinivasan. 2022. Fully-Secure MPC with Minimal Trust. In TCC.
  61. [61]Zhu JianHao, Changze Lv, Xiaohua Wang, Muling Wu, Wenhao Liu, Tianlong Li, Zixuan Ling, Cenyuan Zhang, Xiaoqing Zheng, and Xuanjing Huang. 2024. Promoting Data and Model Privacy in Federated Learning through Quantized LoRA. In EMNLP.arxiv.org/abs/2406.10976
  62. [62]Thorsten Joachims. 2002. Optimizing Search Engines using Clickthrough Data. In KDD.
  63. [63]William B. Johnson and Joram Lindenstrauss. 1984. Extensions of Lipschitz Mappings into a Hilbert Space. Contemp. Math. (1984).
  64. [64]Peter Kairouz, Ziyu Liu, and Thomas Steinke. 2021. The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation. In ICML.arxiv.org/abs/2102.06387
  65. [65]Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. 2021. Practical and Private (Deep) Learning Without Sampling or Shuffling. In ICML.
  66. [66]Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. 2008. What Can We Learn Privately? In FOCS. 531–540.arxiv.org/abs/0803.0924
  67. [67]Hannah Keller, Helen Möllering, Thomas Schneider, Oleksandr Tkachenko, and Liang Zhao. 2024. Secure Noise Sampling for DP in MPC with Finite Precision. In ARES.DOI
  68. [68]Christopher T. Kenny, Shiro Kuriki, Cory McCartan, Evan T. R. Rosenman, Tyler Simko, and Kosuke Imai. 2021. The use of differential privacy for census data and its impact on redistricting: The case of the 2020 U.S. Census. Science Advances 7, 41 (2021).DOI
  69. [69]Oleksandra Klymenko, Stephen Meisenbacher, and Florian Matthes. 2022. Differential Privacy in Natural Language Processing: The Story So Far. In PrivateNLP Workshop.DOI
  70. [70]Jakub Konečný, Brendan McMahan, and Daniel Ramage. 2015. Federated Optimization: Distributed Optimization Beyond the Datacenter. CoRR abs/1511.03575 (2015). http://arxiv.org/abs/1511.03575
  71. [71]Yu-Hsuan Kuo, Cho-Chun Chiu, Daniel Kifer, Michael Hay, and Ashwin Machanavajjhala. 2018. Differentially private hierarchical count-of-counts histograms. PVLDB (2018).
  72. [72]Matt Lepinski, Silvio Micali, and abhi shelat. 2005. Collision-free protocols. In STOC.
  73. [73]Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. 2020. Federated Learning: Challenges, Methods, and Future Directions. IEEE Signal Processing Magazine 37, 3 (2020), 50–60. doi:10.1109/MSP.2020.2975749DOI
  74. [74]Xuechen Li, Florian Tramèr, Percy Liang, and Tatsunori B. Hashimoto. 2022. Large Language Models Can Be Strong Differentially Private Learners. ICLR (2022).arxiv.org/abs/2110.05679
  75. [75]Xiang Lisa Li and Percy Liang. 2021. Prefix-Tuning: Optimizing Continuous Prompts for Generation. In ACL.arxiv.org/abs/2101.00190
  76. [76]Yuting Liang and Ke Yi. 2023. Concentrated Geo-Privacy. In CCS. Zinan Lin, Sivakanth Gopi, Janardhan Kulkarni, Harsha Nori, and Sergey Yekhanin. 2024. Differentially Private Synthetic Data via Foundation Model APIs I: Images. In ICLR.
  77. [78]Daoyao Liu, Edith Cohen, Badih Ghazi, Peter Kairouz, Pritish Kamath, Alexander Knop, Ravi Kumar, Pasin Manurangsi, Adam Sealfon, Da Yu, and Chiyuan Zhang. 2025. Urania: Differentially Private Insights into AI Use. In COLM.
  78. [79]S. Lloyd. 1982. Least Squares Quantization in PCM. IEEE TIT (1982).
  79. [80]Xinjiang Luo, Ting Yu, and Xiaokui Xiao. 2025. Prompt Inference Attack on Distributed Large Language Model Inference Frameworks. CCS (2025).
  80. [81]J. B. MacQueen. 1967. Some Methods for Classification and Analysis of Multivariate Observations. In Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, Vol. 1. University of California Press, 281–297.
  81. [82]Justus Mattern, Zhijing Jin, Benjamin Weggenmann, Bernhard Schölkopf, and Mrinmaya Sachan. 2022. Differentially Private Language Models for Secure Data Sharing. In EMNLP.arxiv.org/abs/2210.13918
  82. [83]Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. 2017. Communication-Efficient Learning of Deep Networks from Decentralized Data. In AISTATS.
  83. [84]Stephen Meisenbacher, Alexandra Klymenko, Andreea-Elena Bodea, and Florian Matthes. 2025. The Double-edged Sword of LLM-based Data Reconstruction. WPES @ CCS (2025).DOI
  84. [85]Ilya Mironov, Omkant Pandey, Omer Reingold, and Salil Vadhan. 2009. Computational Differential Privacy. In CRYPTO.
  85. [86]Michael Mitzenmacher and Eli Upfal. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, Cambridge, UK. doi:10.1017/CBO9780511813603DOI
  86. [87]Payman Mohassel and Peter Rindal. 2017. SecureML: A System for Scalable Privacy-Preserving Machine Learning. In SP.
  87. [88]John X. Morris, Volodymyr Kuleshov, Vitaly Shmatikov, and Alexander M. Rush. 2023. Text Embeddings Reveal (Almost) As Much As Text. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing. Association for Computational Linguistics, Singapore, 12448–12460. doi:10.18653/v1/2023.emnlp-main.765DOI
  88. [89]John X. Morris, Wenting Zhao, Justin T. Chiu, Vitaly Shmatikov, and Alexander M. Rush. 2024. Language Model Inversion. In ICLR.
  89. [90]Huy Nguyen, Anamay Chaturvedi, and Eric Xu. 2021. Differentially Private k-Means via Exponential Mechanism and Max Cover. AAAI (2021).
  90. [91]Jianmo Ni, Chen Qu, Jing Lu, Zhuoyun Dai, Gustavo Hernández Ábrego, Ji Ma, Vincent Zhao, Yi Luan, Keith Hall, Ming-Wei Chang, et al. 2022. Large Dual Encoders Are Generalizable Retrievers. In EMNLP.
  91. [92]OpenAI. 2023. GPT-4 System Card. https://cdn.openai.com/papers/gpt-4-system-card.pdf.
  92. [93]OpenAI. 2023. March 20 ChatGPT Outage: Here’s What Happened. https://openai.com/index/march-20-chatgpt-outage/.
  93. [94]Mijung Park, James Foulds, Kamalika Chaudhary, and Max Welling. 2017. DP-EM: Differentially Private Expectation Maximization. In AISTATS.arxiv.org/abs/1605.06995
  94. [95]Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. 2019. Language Models are Unsupervised Multitask Learners. OpenAI technical report (2019).
  95. [96]D. Ridgeway, M. Theofanos, T. Manley, and C. Task. 2021. Challenge Design and Lessons Learned from the 2018 Differential Privacy Challenges. NIST Technical Note 2151. National Institute of Standards and Technology. doi:10.6028/NIST.TN.2151DOI
  96. [97]Guy N. Rothblum, Eran Omri, Junye Chen, and Kunal Talwar. 2024. PINE: efficient verification of a euclidean norm bound of a secret-shared vector. In USENIX Security.
  97. [98]Ali S. Shamsabadi, Peter Snyder, Ralph Giles, Aurélien Bellet, and Hamed Haddadi. 2025. Efficient, Private and Accurate Histogram Estimation. CCS (2025).DOI
  98. [99]Tom Simonite. 2016. Apple’s New Privacy Technology May Pressure Competitors to Better Protect Our Data. https://www.technologyreview.com/2016/08/03/158510/
  99. [100]Dong Su, Jianneng Cao, Ninghui Li, Elisa Bertino, and Hongxia Jin. 2016. Differentially Private K-Means Clustering. In CODASPY.
  100. [101]Ziteng Sun, Peter Kairouz, Haicheng Sun, Adria Gascon, and Ananda T. Suresh. 2024. Private Federated Discovery of Out-of-Vocabulary Words for Gboard.arxiv.org/abs/2404.11607
  101. [102]Kunal Talwar. 2022. Differential Secrecy for Distributed Data and Applications to Robust Differentially Secure Vector Summation. In FOC.
  102. [103]Kunal Talwar, Shan Wang, Audra McMillan, Vitaly Feldman, et al. 2024. Sample Anonymous Aggregation for Private Federated Data Analysis. In CCS.
  103. [104]Alex Tamkin, Miles McCain, Kunal Handa, Esin Durmus, Liane Lovitt, Ankur Rathi, Saffron Huang, Alfred Mountfield, Jerry Hong, Stuart Ritchie, et al. 2024. Clio: Privacy-Preserving Insights into Real-World AI Use. arXiv:2412.13678 [cs.CL] https://arxiv.org/abs/2412.13678
  104. [105]TaylorAI. 2023. User Queries Dataset. https://huggingface.co/datasets/TaylorAI/user_queries_dataset. Hugging Face dataset.
  105. [106]Vishnu Vinod, Krishna Pillutla, and Abhradeep Guha Thakurta. 2025. InvisibleLink: High-Utility and Low-Cost Text Generation with Differential Privacy. arXiv:2507.02974 [cs.LG] https://arxiv.org/abs/2507.02974
  106. [107]Tianhao Wang, Jeremiah Blocki, Ninghui Li, and Somesh Jha. 2017. Locally Differentially Private Protocols for Frequency Estimation. In 26th USENIX Security Symposium (USENIX Security 17), 729–745.
  107. [108]Tianze Wang, Zhaoyou Chen, Jian Du, Yingqi Xiao, Linjun Zhang, and Qiang Yan. 2025. Secret-Protected Evolution for Differentially Private Synthetic Text Generation. arXiv:2510.10990 [cs.CR] https://arxiv.org/abs/2510.10990
  108. [109]Alexandra Wood, Micah Altman, Aaron Bembenek, Mark Bun, Marco Gaboardi, James Honaker, Kobbi Nissim, David O’Brien, Thomas Steinke, and Salil Vadhan. 2018. Differential Privacy: A Primer for a Non-Technical Audience. Vanderbilt Journal of Entertainment & Technology Law 21, 1 (2018), 209–276. doi:10.2139/ssrn.3338027 Available at SSRN: https://ssrn.com/abstract=3338027.DOI
  109. [110]Chulin Xie, Zinan Lin, Arturs Backurs, Sivakanth Gopi, Da Yu, Huseyin A. Inan, Huishui Zhang, Yin Tat Lee, Sergey Yekhanin, and Bo Li. 2024. Differentially Private Synthetic Data via Foundation Model APIs 2: Text. In ICML.
  110. [111]Rui Xu and Donald Wunsch. 2005. Survey of Clustering Algorithms. TNN 16, 3 (2005), 645–678.
  111. [112]Da Yu, Saurabh Naik, Arturs Backurs, Sivakanth Gopi, Huseyin A. Inan, Gautam Kamath, Janardhan Kulkarni, Yin Tat Lee, Andre Manoel, Lukas Wutschitz, Sergey Yekhanin, and Huishui Zhang. 2022. Differentially Private Fine-tuning of Language Models. In ICLR.
  112. [113]Xiang Yue, Huseyin Inan, Xuechen Li, Girish Kumar, Julia McAnallen, Hoda Shajari, Huan Sun, David Levitan, and Robert Sim. 2023. Synthetic Text Generation with Differential Privacy: A Simple and Practical Recipe. In ACL.
  113. [114]Xin Zhang, Yanzhao Zhang, Dingkun Long, Wen Xie, Ziqi Dai, Jialong Tang, Huan Lin, Baosong Yang, Pengjun Xie, Fei Huang, et al. 2024. mGTE: Generalized Long-Context Text Representation and Reranking Models for Multilingual Text Retrieval. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing: Industry Track. 1393–1412.
  114. [115]Xiang Zhang, Junbo Zhao, and Yann LeCun. 2015. Character-level Convolutional Networks for Text Classification. NeurIPS (2015).
  115. [116]Yonghui Zhang, Yang Liu, Xiaofeng Li, and Zhiyong Xu. 2020. Towards Privacy-Preserving Search Systems. IEEE TDSC (2020).
  116. [117]Zhao Zhao and Anjalie Field. 2025. Controlled Generation for Private Synthetic Text. arXiv:2509.25729 [cs.CL] https://arxiv.org/abs/2509.25729
  117. [118]Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Tianle Li, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zhuohan Li, Zi Lin, et al. 2023. LMSYS-Chat-1M: A Large-Scale Real-World LLM Conversation Dataset.

Paper details

vlnc:W_3dj9n8aw
Published
Added
License
CC BY 4.0
Usage

views · 0

downloads · 2

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

ChatGPT

View statement
Looking for related papers…
Contents