Phantoms and Disclosures: a Causal Framework for Auditing Synthetic Data Kareem Amin1 , Rudrajit Das1 , Alessandro Epasto1 , Adel Javanmard1,2 , Dennis Kraft1 , Mónica Ribero1 , and Sergei Vassilvitskii∗1
arXiv:2606.16952v1 [cs.LG] 15 Jun 2026
1
2
Google University of Southern California
Abstract The rapid adoption of generative AI and Large Language Models (LLMs) has spurred interest in synthetic data as a privacy-preserving alternative to sensitive real-world datasets. However, generating high-utility synthetic data often carries the risk of memorizing and regurgitating private information from the training corpus. In this work, we present a customizable empirical auditing framework designed to detect and explain such data disclosures. Our framework introduces a mechanism to distinguish between true disclosures—where the system directly reproduces a user’s information—and phantom disclosures—where the system incidentally generates a user’s data. By partitioning input data into training and holdout sets and applying rigorous statistical hypothesis testing, we determine if observed disclosures are consistent with strict privacy baselines, such as zero-learning or specific Differential Privacy (DP) bounds. Crucially, this approach requires no model access, no canary insertion, and no reference model training — only the synthetic output and a held-out control set. We demonstrate that this framework effectively functions as a membership inference attack, providing empirical lower bounds on privacy leakage that are tighter than prior data-based auditing methods. Our approach is model-agnostic, applies to any synthetic data generation mechanism, and requires orders of magnitude fewer computational resources than shadow-model or canary-based alternatives.
1
Introduction
The rise of generative AI has created a great deal of interest in the study of synthetic, machinegenerated, data. Large language models (LLMs) can be prompted to create synthetic documents resembling real data from multiple, often sensitive, domains such as emails, court documents, health records, or search queries. As the capabilities of these models continue to increase, AI-generated datasets are becoming a promising alternative to real human data, specifically, as a privacy-preserving measure [22]. Consider a hospital service that wishes to study treatment outcomes by sharing its data with external researchers. Rather than contend with the privacy and compliance risks associated with releasing its raw patient records, the hospital might release a synthetic data analog, produced with the assistance of an AI model. The details behind synthetic data generation can vary greatly across deployments due to the technical capabilities of the data-owner and the requirements of the users of the data. For example, ∗
The authors’ names are listed in alphabetical order.
1
prompting an LLM to produce synthetic data that matches the schema of hospital records may be good-enough to stress test a data ingestion pipeline. However, the same data is less useful to a researcher interested in the relationship between treatments and outcomes. For this application, the researcher requires that the synthetic data capture the statistical relationships within the private dataset. As a consequence, there are many techniques for generating synthetic data, many of which make use of signal in the sensitive private dataset in some way. From the viewpoint of data privacy, this creates a dilemma. On the one hand, synthetic data can be viewed as a safer alternative to real data in almost any context where real data is used. On the other hand, generating high-quality synthetic data often requires capturing precisely the signals that make private data sensitive. As a result, good synthetic data can appear as sensitive as the corpus used to generate it. A non-exhaustive list of synthetic data generation techniques includes: prompting an LLM to produce data in some desired format, prompting an LLM to rewrite private data records that have been placed in-context, or fine-tuning an LLM to produce responses similar to the private corpus. There are also several analogs to these approaches that provide formal differential privacy (DP) guarantees [11] such as DP inference, DP fine-tuning, DP tabular data generation, and private evolution (see [34] for a review). To complicate matters further, the privacy properties of the system may depend on a variety of implementation decisions that are not captured in any formal guarantees. For example, scrubbing personally identifiable information (PII) from the source data can be materially beneficial to privacy. Similarly, the choice of privacy parameters in a DP system can often be so large as to render the formal guarantees vaccuous. However, many real deployments (most famously the US Census [2]) argue that there are tangible privacy benefits to these algorithms nonetheless. Consequently, there is a critical need for rigorous auditing frameworks to evaluate the privacy guarantees of synthetic data deployments. To remain practical, such an audit must be fundamentally decoupled from—and robust to—the specific algorithmic techniques used to generate the data. Motivated by these considerations, we adopt the perspective of an internal privacy auditor seeking to quantify leakage risks prior to releasing synthetic data. Our approach centers on disclosure detection within the generated dataset, where a disclosure is defined as any feature or information that occurs rarely in the source corpus yet resurfaces in the synthetic output. By focusing on disclosures, our framework relies only on looking at the data, and offers several distinct advantages. Black-box auditing. Given the myriad ways in which synthetic data might be generated, our system makes no assumptions about the nature of the data or the synthetic data generation procedure. The synthetic data does not need to have been generated by fine-tuning and prompting a model [47, 28, 25], but could be the result of any synthetic data generation procedure such as inference [4, 41] or evolution [27]. This contrasts with prior work on model based auditing [39, 7, 46] which can only audit synthetic data generated through a model. In order to conduct the audit, the auditor needs access only to the synthetic data, the private data that was synthesized, and a held-out dataset that was not used for synthesis. Turn-key deployment. Prior black-box approaches [32] require designing domain-specific canaries to attack the system and training additional reference models [48]. Such systems require privacy experts with domain knowledge of the data to ensure adequate canaries are inserted into the system. Our system avoids both the computational bottleneck of fine-tuning large models, and the human-in-the-loop dependency created by canary design. Flexible disclosure detection. Our system produces witnesses of privacy leakage, called disclosures. Identifying these disclosures is important as it allows the auditor and decision makers to reason concretely about the risks in the synthetic data release. Moreover, the system provides 2
the auditor with a predefined list of disclosure classes to choose from. This list is flexible and can be expanded as users of the system identify new types of risks that they wish to measure. Phantom disclosure detection. We identify and formalize a pervasive but previously overlooked phenomenon: a large fraction of apparent privacy violations in synthetic data are what we call phantoms — disclosures that would occur with equal probability regardless of whether the user’s data was included in training. In our experiments, phantoms account for over 35% of detected disclosures (e.g., 271 of 763 PII matches in the Finance dataset). This finding has immediate practical implications: naı̈ve disclosure counts dramatically overstate privacy risk. Our system specifically measures and grounds the phantom disclosure rate using holdout data. Formal privacy leakage. Beyond simple detection, we also use the set of detected disclosures to provide formal measurements of privacy leakage. Our framework provides two levels of analysis: a zero-learning test that detects any dependence between synthetic outputs and source data, and a DP-bounded learning test that assesses whether observed disclosures are consistent with ε-differential privacy. Both tests provide formal type I error control (Theorems 1 and 3) and yield empirical lower bounds on the privacy parameter ε (Theorem 2). The framework is analogous to a controlled experiment in which the holdout set serves as the control group and the training set as the treatment group. We also construct membership inference attacks using just disclosures, providing yet another formal metric of privacy leakage (the AUC of the attack). Unlike prior MIA approaches, our attack requires no model access, no canary insertion, and no shadow-model training — only the released synthetic data and a held-out sample from the same distribution. As with any statistical testing (and any empirical privacy testing), evidence gathered in this way can only formally disprove the null hypothesis that the synthetic data deployment is privacy-safe. However, failure to reject the null hypothesis for small ϵ is nevertheless quite informative when few concrete disclosures are detected, and the disclosure classes accurately characterize the types of risks that the auditor is practically concerned about.
1.1
Related work
Our work provides a framework for auditing synthetically generated data for privacy violations. We provide a brief overview of existing literature on private synthetic generation and privacy auditing. Privacy-preserving synthetic data generation Since its introduction [12], Differential Privacy (DP) has emerged as the gold standard for formal privacy protection. Recent advancements in generating differentially private synthetic data typically follow one of two paradigms: fine-tuning a model with privacy constraints or utilizing a public model with privacy protections applied during inference. The first approach [47, 28, 25] involves learning using DP-SGD [1] on a private dataset, often starting from a language model pretrained on public data. Once trained, this DP-protected model can be prompted to generate an arbitrary volume of synthetic data without further compromising user privacy. The second approach avoids the high computational costs of private training [13] by employing models trained exclusively on public data, but where private data is used somewhere during inference. Some methods in this category prompt the model using private data [4, 41] and sample synthetic data from a perturbed distribution. Others [27, 45, 26] utilize private evolution, where the private data is used to “vote” (via DP mechanisms) on which model-generated samples to retain during an iterative process, ensuring the model is never directly queried with private inputs. Because our audit methodology requires access only to the resulting synthetic data rather than the underlying model it is applicable to all such generation methods, including those without inherent privacy protections (e.g., sampling from an SFT model trained without DP). 3
Privacy auditing Generative models are known to sometimes expose their training data creating privacy risks [9, 8] and copyright risks [31, 38] (see [35] for a survey on memorization, recitation, and data extraction). Consequently, significant research has focused on empirically testing these systems. Central to this field is the study of attacks on models trained with DP-SGD, primarily through membership inference attacks (MIA) [21, 36, 10, 20, 8, 9, 40] and data reconstruction attacks [16, 5]. Empirical testing of generative models generally follows two directions: model-based auditing and data-based auditing. Model-based auditing is the more prevalent approach (see [40, 39, 9, 8, 17, 20, 43]). This approach typically involves inserting “canaries” (i.e., artificially crafted examples) into the training set and subsequently querying the model either for completions or intermediate weights to determine if a specific canary was memorized. Auditing Data The more relevant work to our own is the pioneering study by Meeus et al. [32], who were the first to investigate auditing synthetic text data directly. They are motivated by the accuracy of the attack surface; synthetic data is often released without the model used to generate it. Given the proliferation of synthetic data generation techniques, we are also motivated by the need for algorithm-agnostic techniques for evaluating the privacy properties of synthetic data. The framework of Meeus et al. [32] assumes an attacker who can inject canaries into the training set and has access only to the generated synthetic data, not the model itself. The authors demonstrate that training simple n-gram models on the synthetic data allows an attacker to identify inserted canaries. This method performs multiple retrainings of the model on partial subsets of the canary data (to obtain so called reference models). Our approach, notably, does not require such retraining reducing the computational cost. Prior to this, synthetic data audits focused on specific domains such as images [18] or tabular data [30]. In contrast, our work focuses on the same general text data setting as [32]. Canary design Since many auditing methods rely on canary insertion, selecting the optimal canary is a non-trivial problem that significantly impacts attack performance. This has motivated research into optimized canary design [33, 32, 6]. Our work sidesteps this challenge by not requiring the explicit insertion of canaries, though it remains flexible enough to utilize canary data during the audit, as shown in our empirical evaluation.
2
Disclosures
Consider using a data generation algorithm (see [34] for a recent survey) to create a synthetic version of an email dataset (e.g., the Enron dataset [23]). Since the algorithm is supposed to learn how emails are formatted and what users write in emails, we may observe an output such as the following. From: [email protected] To: [email protected] Subject: New phone number Dear Jane, My new phone number is 212-555-1234. Yours, John Smith We expect this data to contain strings that resemble personally identifiable information (PII) such as names, emails, phone numbers, etc. However, if the PII belongs uniquely to a user in the 4
source data — for example, if 212-555-1234 is an actual user’s phone number — then there is much larger cause for concern. In this work, we call such events disclosures. We loosely define a disclosure as any information that appears rarely in the source corpus, but also appears in the synthetic data. While the specification language is generic, we use it to instantiate three classes of disclosure corresponding to threats that appear commonly in the privacy literature: 1. PII leakage. PII is any string that can trace a user’s identity (such as a name, address, account number, etc). A PII disclosure occurs if a string is detected as PII in the source corpus, appears rarely in the source corpus, and also appears in the synthetic corpus. 2. Regurgitation. In text data, regurgitation occurs if a sequence of tokens appears rarely in the source corpus but is reproduced in the synthetic corpus. 3. Semantic reconstruction. Semantic reconstruction occurs if the meaning of a record is preserved in the synthetic data, and few records have the same meaning in the source corpus. These classes are not meant to be complete, but are illustrative of the types of leakage that an auditor might be practically interested in measuring. A key feature of our system is that it provides a formalism for specifying different classes of disclosures as auditors identify new threats.
2.1
Phantom Disclosures
We note that a disclosure captures a relationship between the synthetic dataset and the private dataset that was used to generate the synthetic data. The same relationships can be measured between the synthetic dataset and an in-distribution private dataset that was not used to generate the synthetic data. Suppose we have a dataset D that has been randomly partitioned as D = Dtrain ∪ Dhold , and where a synthetic dataset Y was generated from Dtrain . We may take the same measurements on (Y, Dhold ) as we do on (Y, Dtrain ). For example, we may check whether the phone number 212-555-1234 appearing in synthetic data is unique to a holdout user. We call these phantom disclosures. Naively, one might expect that phantom disclosures happen rarely, if at all. On the contrary, our empirical results demonstrate that such disclosures can and do happen quite frequently. Thus, if we are to use disclosures as evidence of privacy leakage, it is important to establish the phantom disclosure rate as a baseline when interpreting the disclosure rate measured on (Y, Dtrain ). The existence of phantom disclosures invites discussion as to why phantom disclosures occur. We identify three potential causes: 1. Generalization. The objective of many synthetic generation procedures is to produce a dataset that is distributionally similar to the source data. For example, the procedure might recognize that training examples predominantly use a particular area code, increasing the probability of incidentally reproducing a holdout phone number. 2. Inductive bias. The synthetic generation procedure may be predisposed to producing certain types of data before ever encountering training examples. For example, the procedure may have a subroutine that produces US phone numbers as a 10-digit sequence. Alternatively, an LLM used to produce phone numbers may understand their structure from pretraining. 3. Model contamination. If the synthetic data generation procedure makes use of a foundation model, and the source data is publicly available, it is difficult to guarantee that the heldout data was not seen during pretraining. 5
Critically, the auditor need not determine which of these mechanisms produced a given phantom. Our framework is agnostic to these causes; it uses the phantom disclosure rate to measure excess disclosures attributable to training-set membership. Finally, we highlight that contamination is largely an academic phenomenon. For real deployments (e.g. a hospital service generating synthetic records), the synthetic data is useful because the source data has not and will not be made public. For demonstrations on publicly available data, the possibility of contamination only underestimates the audit’s capabilities; access to an uncontaminated model would lower the phantom disclosure rate and increase the significance of disclosures detected on the training dataset.
3
Disclosure Framework
Our framework allows the system designer to flexibly define classes of disclosure that are of interest to the auditor. We describe this in greater detail. Throughout, we will consider data records that belong to some space X . When considering private input data, we think of x ∈ X as all the data belonging to a particular user.
3.1
Data generation
We assume access to a combined dataset D = Dtrain ∪Dhold . We also assume as input a randomized mechanism M : X ∗ → X m that takes a subset of X ∗ and outputs m synthetic records in X . We denote the synthetic dataset using Y = M(Dtrain ). Importantly, we place no assumptions on how M is implemented. For example, we do not require that M constructs a generative model for producing text data, nor do we require glass-box access to the internals of M in order to audit it.
3.2
Features and Rareness
Recall that we loosely defined a disclosure as any information that is rare in the source data that appears in the synthetic data. In order to define a new class of disclosures, we begin by specifying two functions: extract and rare. Given a feature space F, extract : X ∗ → F ∗ is a function that maps a dataset to a collection of features. rare : F × X ∗ → {0, 1} is a function that takes a feature and a dataset and determines whether the feature is rare with respect to the dataset. Given a combined dataset D = Dtrain ∪Dhold , we determine the set of features that are rare relative to D: Frare = {f ∈ extract(D) : rare(f, D) = 1}. For example, the disclosure classes introduced in Section 2 are instantiated as follows. PII leakage. extract returns strings from the source data that appear to be personally identifiable information. For our experiments we use the Google Cloud DLP API to detect such strings. rare takes a hyperparameter k and indicates that a string is rare if it belongs to k users in D. We use Fk to denote Frare when features are defined in this way, and note that F1 are PII that are unique to users. Regurgitation. extract takes hyperparameters Lmin and Lmax and returns all substrings in the source data with length in [Lmin , Lmax ]. For our experiments, we tokenize substrings by whitespace and measure length by number of tokens. rare is defined as above. Semantic reconstruction. extract maps each user’s document to an embedding in Rd . For our experiments, we use Gemini Embedding 2 with d = 768. rare takes hyperparameters κ and q. We compute an approximate κ-nearest neighbors for the embeddings generated this way using cosine similarity. We rank each embedded datapoint by smallest average similarity to its κ-nearest 6
neighbors. The record with the least average similarity indicates the user whose record is most semantically distinct from other users in D. q ∈ [0, 1] specifies what quantile is considered rare.
3.3
Disclosure Quantification
We use rare features to characterize whether the synthetic data set Y discloses information about a user x ∈ D. We do this by way of a function score : F ∗ × X ∗ → O. score is applied on the rare features belonging to user x (i.e. extract(x) ∩ Frare ) and the dataset Y . Abusing notation slightly, we write score(x, Y ) := score(extract(x) ∩ Frare , Y ). PII leakage and regurgitation. In these settings, the features are discrete. A natural instantiation of score is therefore to count the number of rare features belonging to a user x that appears in the synthetic data. score does not need to return a scalar. For discrete settings, we also consider the function A(x) ∈ {0, 1}|Frare | that lists, for each rare feature, whether user x had the feature and it appeared in Y , disaggregating which features of x appeared in the synthetic data. Semantic reconstruction. We instantiate score as the similarity in embedding space between x and its 1-nearest neighbor in Y . When applicable, we can also report the similarities between x and it’s κY -nearest neighbors in Y . In the semantic reconstruction setting x generates a single feature fx for each user x (its embedding), and score(x, Y ) = ⊥ when fx ̸∈ Frare .
4
Audit Pipeline
Training Data
Algorithm
Synthetic Data
Distributed Like
Hold-out Data Synthetic Features
Training Features
Hold-out Features
Phantom Disclosures
True Disclosures
Figure 1: Overview of the audit pipeline. Data consists of training and held-out sets. Training data is processed by a synthetic generation algorithm to produce synthetic data. All three datasets – training, held-out, and synthetic – are processed for features. Rare features appearing in heldout and synthetic data are phantom disclosures. Rare features in training and synthetic are true disclosures. We now have all the ingredients to describe our audit pipeline (see Figure 1). Begin with a dataset D = (x1 , . . . , xn ) ∈ X n . Each record xi is assigned a Bernoulli(p) random variable si , 7
indicating whether the record will be used in training, defining a partition D = Dtrain ∪ Dhold .1 Let Frare indicate rare features in the entire corpus for the disclosure type being audited. Run Y = M(Dtrain ). We measure disclosures on both training Strain = {score(x, Y ) | x ∈ Dtrain } and hold-out Shold = {score(x, Y ) | x ∈ Dhold }. Strain describes the disclosures present in the synthetic data release and is valuable information to the auditor and any consumers of the audit, who often simply want to understand whether phenomenon like PII leakage, regurgitation and semantic reconstruction are occurring. Similarly, Shold describes the phantom disclosure rate. Knowledge of the phantom disclosure rate is often, in isolation, also critical information for decision-makers interpreting the audit. Synthetic data that only appears to leak private information may nevertheless be a problem in real deployments. The final step of the audit is to render formal statements about privacy leakage. Hypothesis testing. The remainder of this work is dedicated to the question: can we establish formal statements about privacy leakage from observed gaps between Strain from Shold ? More precisely, we consider two counterfactual null hypotheses consisting of two strong privacy claims. The first null hypothesis considers the case when M does not process the input user data at all. We call this the zero learning test. This is the strongest privacy claim possible, and is consistent with 0-Differential Privacy. Under this null hypothesis, we expect Strain and Shold to come from the same exact distribution. Therefore, we can use statistical tools to reject this hypothesis. The second counterfactual considers the case when M is ϵ-Differentially Private (DP) for any desired range of ϵ. We call this the DP-bounded learning test. Under DP, we expect the differences between Strain and Stest to be bounded. Consistent with privacy testing in differential privacy [40], if the test rejects the null hypothesis with the appropriate significance level, we claim that we have causally established the presence of privacy-unsafe disclosure, beyond the expected set of phantom disclosures. If the test does not reject the null hypothesis, the observation is consistent with strong privacy protection against true disclosures. Notice that, as with prior literature on privacy attacks [40, 39], this test can be seen as focusing on completeness rather than soundness. It is in fact known that soundness tests (even for pure DP) have exponential sample complexity [14]. Causality. We use the term “causal” in the sense of controlled statistical experiments [19]. Our framework establishes that training-set membership causes an excess of disclosures at the population level, analogous to a randomized controlled trial establishing that a treatment causes improved outcomes in a cohort. This is distinct from the stronger claim of mechanistic or individuallevel causality — i.e., tracing a specific synthetic output to a specific training example. The latter would require interpretability tools beyond the scope of this work. Our population-level causal claim is formalized through the hypothesis tests in Section 5, which control the probability of false attribution. Membership inference attacks. When score(x, Y ) returns a scalar, it is easy to see how to use the disclosure score to launch a membership inference attack (MIA). Set a threshold, and predict that x is in training if score(x, Y ) exceeds the threshold. Thus, another metric our audit reports is the success of such an attack, which can be measured by Area Under the Curve (AUC).
5
Statistical Audits and Inference Attacks
In this section, we formally define an empirical audit and an associated membership inference attack formulation, derived from the disclosures present in the synthetic data. Together, these 1
This assignment can be conducted either by a system administrator seeking to conduct an audit, or can occur “naturally” if Dhold is already set aside (for instance for validation).
8
components assess whether the observed matching patterns align with the zero-learning or the DP-bounded learning hypotheses introduced earlier. We now define these two evaluations, which we call the Feature Match Test and the User Inference Attack.
5.1
Feature Match Test (Discrete Features)
Recall when extract produces discrete features, we can define Fk as features that appear k times in D. Let D consist of n records derived from users. We index these records by i = 1, . . . , n. As previously described, suppose that each record is sampled into Dtrain independently with probability p. Let l = |Fk ∩ extract(Y )| denote the number of features in Fk that appear at least once in the synthetic output. We index these features by j = 1, . . . , l. Audit test statistic. We construct a binary matrix A ∈ {0, 1}n×ℓ , where each row i corresponds to an input record xi and each column j corresponds to one of the ℓ output features fj . We set Aij = Afj (xi , Y ), indicating whether xi has feature fj . Pn By definition of Fk , each column has exactly k ones: i=1 Aij = k, for all j ∈ [ℓ]. For each record i, define di :=
ℓ X
Aij
(1)
j=1
the number of output features that appear in record i. Our test statistic is defined as the total number of feature-record disclosures associated with the training data: X T = di (2) i:xi ∈Dtrain
5.1.1
Zero learning test
Under the zero learning hypothesis, we consider a mechanism M that outputs the same distribution of synthetic data regardless of the input data. Intuitively, since the mechanism does not learn or memorize the input features, their occurrences in the output should not be overly concentrated in records that happen to be in the training set. Hence, large values of T provide evidence against the zero-learning hypothesis. This can be formalized as follows. Decision rule at significance level α. Under the zero learning null hypothesis, the event that a feature from Fk appears in the synthetic output is independent of whether a record with this feature was present in the training set. Hence, conditional on the observed matrix A, each record is still included in Dtrain with probability p, independent of other records. This allows us to characterize the null distribution by writing the test statistic as: n (d) X
T =
di si ,
(3)
i=1 (d)
where ‘ = ’ means in distribution, and we recall that si ∈ {0, 1} are independent Bernoulli random variables with Pr(si = 1) = p. Under the zero learning hypothesis we have E[T ] =
n X
di E[si ] = p
i=1
n X i=1
9
di = ℓkp .
By applying Hoeffding’s inequality, for any t > 0, 2t2 Pr(T − ℓkp ≥ t) ≤ exp − Pn
2 i=1 di
For a desired significance level α ∈ (0, 1), for example α = 5%, define the critical value v u X u1 d2i log(1/α) cα := ℓkp + t 2
(4)
(5)
i∈[n]
We then use the following one-sided test2 for the zero learning hypothesis: P • Compute the observed statistic T = i∈S di . • Reject the zero learning hypothesis if T ≥ cα . This rule flags potential true disclosures when the observed counts of synthetic features from the training set is unusually large compared to what would be expected from the no-learning mechanism. Conversely, failing to reject the null indicates that the disclosures observed in the training data cannot be distinguished from those produced completely by chance. We recall that the type I error of a test is the probability of falsely rejecting the null hypothesis. By (4), the type I error of our audit is controlled at level α; that is, under the zero-learning hypothesis, Pr(T ≥ cα ) ≤ α. This guarantees that any privacy breach flagged by the test occurs with probability at most α when the mechanism behaves according to the null, providing a clear and calibrated notion of statistical risk for the auditor. The test also instantiates a p-value, pval = Pr(T ≥ cα ), as well as a confidence interval around the sampling probability p (conditioned on the observed test statistic), independent of a specific decision rule. The p-value provides a calibrated measure of how incompatible the observed feature matches are with the zero-learning hypothesis, and thus can be interpreted as privacy metric in its own right. We provide a more detailed discussion in Appendix B. The same is true for the confidence interval, which we formalize next. Confidence interval for sampling probability. Our test statistic allows us to construct a one-sided confidence interval for the sampling probability p, i.e., the probability that a record is included in the training set. This is formalized in the following lemma. Lemma 1. Fix a significance level α and set v u X u1 tα := t d2i log(1/α), 2
p̂ =
i∈[n]
T − tα ℓk
(6)
Then, under the zero learning hypothesis, the following holds with probability at least 1 − α: p ∈ CI(1 − α) := [p̂, 1]
(7)
In our experiments, (Table 5) we report p̂ as the evidence against the null. 2
We focus on a one-sided test because, under the alternative, we expect more matches with the training data than with the hold-out set. Moreover, the privacy risk we want to assess is the disclosure of features from training data. However, a two-sided version of the test can also be derived straightforwardly.
10
5.1.2
DP-bounded learning test
We next consider a weaker hypothesis than zero learning (but still consistent with strong privacy), where we allow the mechanism to do some learning. We develop audit test for the null hypothesis that the data generation mechanism M is ϵ-DP (note that the zero learning claim is consistent with 0-DP.) As we will discuss our audit test also provides empirical lower bounds on the privacy loss ϵ. Our test statistic is same as the one in zero learning test, given by (2). For a decision rule, we will work with a larger critical value than the one given in (5). Decision rule at significance level α. For a desired significance level α ∈ (0, 1), define the critical value v u X p u1 cϵ,α := ℓk + d2i log(1/α) (8) t −ϵ p + (1 − p)e 2 i∈[n]
We then use the following one-sided test for DP-bounded learning hypothesis: P • Compute the observed statistic T = i∈S di . • Reject the ϵ DP-bounded learning hypothesis if T ≥ cϵ,α . In our next theorem, we show that the type I error of our audit test (its type I error) is controlled at the desired significance. Theorem 1. The type I error of the feature match audit test for the DP-bounded learning hypothesis is controlled at level α, i.e., under the null hypothesis we have Pr(T ≥ cϵ,α ) ≤ α . The proof of theorem is deferred to the appendix. The proof uses the definition of ϵ-DP to show that under the null hypothesis, and conditional on the synthetic features, the test statistics is stochastically bounded from above and below by two weighted sums of independent Bernoulli random variables. We then use these bounds to prove that for the specific choice of critical value cϵ,α the type I error is controlled under the desired level α. Empirical lower bound on ϵ. Our analysis of the audit test statistic under ϵ DP-bounded learning hypothesis can be used to derive empirical lower bound on the privacy loss ϵ. Theorem 2. For significance level α ∈ (0, 1) and the observed test statistic T given by (2), define r T 1 ∥d∥2 A := − log(1/α) ∥d∥1 2 ∥d∥1 r T 1 ∥d∥2 B= + log(1/α) ∥d∥1 2 ∥d∥1 with d = (d1 , . . . , dn ) and di given by (1). We define ( 1−p A + log log p 1−A , ϵ′∗ := 0
11
if A > 0 otherwise
Algorithm 1: User-match audit Input : A dataset D = {x1 , . . . , xn }, generative mechanism M, privacy budget ϵ to audit, Score function score : X × X ∗ → R, classifier Φ : R → {−1, 0, 1} that maps scores score(x, Y ) to predictions, significance level α. Output: 1 if the ϵ-DP guarantee is rejected at level α, 0 otherwise. Sample s ∈ {0, 1}n and partition D into Dtrain = {xi ∈ D : si = 1} and Dhold = {xi ∈ D : si = 0}. Y ← M(Dtrain ) // Generate m synthetic records 3 W+1 ← {i ∈ [n] : Φ(score(xi , Y )) = 1} // Set of positive predictions 4 wtrain ← |{i ∈ W+1 and xi ∈ Dtrain }|. // Compute true positives 5 r ← |W+1 | // Compute total number of positive predictions
1
2
6
p . return 1(wtrain ≥ c̃ϵ,α ), where c̃ϵ,α is the (1 − α)-quantile of Binomial r, p+(1−p)e −ϵ
ϵ′′∗ :=
( p log 1−p + log 0
1−B B
,
if B < 1 otherwise
We then have ϵ ≥ ϵ∗ = max(ϵ′∗ , ϵ′′∗ ), with probability at least 1 − α. In the case A ≤ 0, the bound ϵ′∗ becomes vacuous, and our procedure does not reject the no-learning hypothesis (since T < cα ). In this regime, the data are therefore consistent with the stronger no-learning guarantee, which in particular implies that the weaker DP-bounded learning hypothesis is not violated for any ϵ > 0. The conclusion of Theorem 2 can also be phrased in testing terms: consider the null hypothesis that the mechanism is ϵ-DP versus its alternative. The smallest value of ϵ for which our test does not reject this null is ϵ∗ .
5.2
User Inference Attack
The feature-match test of Section 5.1 operates at the level of aggregate statistics: it counts how many rare-feature matches fall in the training set overall, but does not examine how those matches are distributed across individual records. A natural question is whether disclosure signals can also be used to make predictions about individual users — that is, whether our framework yields a membership inference attack (MIA). We show that it does, as a corollary of the auditing pipeline. Unlike prior MIA methods that require model access [7, 39, 46], shadow-model training [32], or canary insertion [32, 33, 6], the resulting attack operates solely on the released synthetic data and the auditor’s held-out sample. Let score : X ×X ∗ → R be a scalar scoring function quantifying the similarity between a record x and a synthetic dataset Y . We model an adversary who uses these scores to predict whether a record belongs to the training set (1) or hold-out set (−1), with the option to abstain (0) for low-confidence records. The attack is formalized as a classifier Φ(score(x, Y )) : R → {−1, +1, 0}, typically obtained via thresholding on the similarity score score(x, Y ). These tests are known in the literature as membership inference attacks [40, 31]. Unlike similar approaches that require baseline normalization, our proposed scores are computed directly from the corpus D and synthetic data Y . For an ϵ-DP algorithm, the adversary’s prediction accuracy is bounded as a function of ϵ. We present the full user-based test in Algorithm 1 and prove in Theorem 3 that its type I error is 12
controlled under the target significance level α. Note that, as in Section 5.1, we can use the estimated binomial parameter and corresponding adversarial advantage to quantify disclosure risk. Alternatively, given access to intermediate similarity scores score(x, Y ) for records x ∈ Dtrain ∪ Dhold , one can compare with other membership inference attacks using the AUC metric. Theorem 3. The type I error of the User-match audit test for the DP-bounded learning hypothesis is controlled at level α, i.e., under the ϵ DP-bounded null hypothesis we have Pr(wtrain ≥ c̃ϵ,α ) ≤ α . p where c̃ϵ,α is the (1 − α)-quantile of Binomial r, p+(1−p)e ϵ , r denotes the total number of positive predictions, and wtrain is the total number of true positive predictions, as described in Algorithm 1. Remark 1. By Hoeffding’s inequality, p + c̃ϵ,α ≤ r p + (1 − p)e−ϵ
r
r log(1/α). 2
Using this upper bound for the critical value c̃ϵ,α still controls type I error at significance level α.
6
Experiments
We evaluate the practical utility and statistical power of the proposed tests through extensive experiments on publicly-available data. We show that both feature-match and user-match tests effectively detect significant disclosures in non-private synthetic data generation processes. In the context of DP synthetic data, we observe a non-negligible number of disclosures. However, we show these are primarily phantoms; our test outcomes and the estimated ε values confirm the theoretical privacy guarantees of the generation methods used, and the impact of explicit privacy protections in mitigating the risk of true disclosures. We benchmark our approach against state-of-the-art synthetic data audit methods by Meeus et al. [32]. To the best of our knowledge this is only data-based audit for synthetic text data. We show that we obtain tighter disclosure measures for non-private synthetic data without requiring canary insertion or reference model training, and comparable results for differentially private synthetic data. The remainder of this section is organized as follows. First, we outline the experimental setup: datasets, synthetic data generation processes, feature extraction techniques, and baselines. We then present auditing results for each generation method, comparing our performance against the baseline proposed by [32].
6.1
Experimental setup
Synthetic Data Generation. For each dataset, we partition the records into training and holdout splits by independently selecting each record with probability p = 0.5. We generate synthetic data through three commonly used techniques: • Rewrites: We prompt gemini-3-flash-preview3 accessed through its API, to rewrite each record in the corpus, instructing the model to avoid reproducing exact sentences and to refrain from including PII. While this method does not provide theoretical guarantees in terms of DP, it is indeed a common approach in practice [3]. 3
https://ai.google.dev/gemini-api/docs/models/gemini-3-flash-preview
13
• Fine-tuning (SFT): For fine-tuning we use the open-source Gemma model (gemma-3-1b-it checkpoint) [42] on a next-token prediction task using the training split. All records have an initial prompt of the form “Write a [content-type]:”, where [content-type] corresponds to the content category of the record. The model is fine-tuned using the standard Adam optimizer without privacy constraints. • DP-SGD: Similar to SFT but the model is fine-tuned using a Differentially Private SGD optimizer. We configure the privacy budget to satisfy (ε, δ)-DP with ε = 10 and δ = N −1.1 , where N is the training set size. For rewrites, we generate one synthetic record per input record. For SFT and DP-SGD, we generate 100,000 synthetic records from each model by sampling outputs conditioned on the same prompt distribution as the training data. Auditing Methods. We evaluate our proposed methods and a state-of-the-art baseline: • Feature-Match and User-Match (Ours) The feature-match (Section 5.1) and user-match tests (Section 5.2), which operate directly on the synthetic output without requiring reference models or canaries. The user-match test has two variants: a verbatim variant based on exact-match features (substring or PII matching), and a variant based on semantic similarity captured via embedding cosine similarity. • Canary-based Audit (Meeus et al.): We implement as baseline the methodology of [32], which relies on inserting “hybrid canaries” into the training data. Following their procedures, we generate 1000 canaries by sampling real records (r), truncating them after 20 tokens (rpref ix ), and generating a 30-token suffix (rsuf f ix ) using a pre-trained checkpoint such that the suffix perplexity is contained in the interval [0.9P, 1.1P ] (with target perplexity P = 31). We insert 500 canaries into the training set and keep 500 as holdout. Membership inference scores are computed using an n-gram model and normalized against four reference models trained on disjoint subsets of the canaries. Feature Extraction. To generate the feature set Fk , we use three different extraction methods: • Strings (n-grams): We extract all contiguous (overlapping) word sequences with lengths in the interval [nmin , nmax ], to capture verbatim disclosures of arbitrary text. For the experiments we focus on sequences with lengths between nmin = 11 and nmax = 20. • DLP (Semantic PII): We identify semantically sensitive features using the Google Cloud Data Loss Prevention (DLP) tool [15], accessed via its API. This tool detects a wide variety of PII types, including identification numbers, financial information, and contact information. • Embeddings: We use the Gemini Embedding method (via API access) to embed texts in 768 dimensions. For each text embedding we calculate its average cosine distance across its 10 nearest neighbors. We then filter out the 0.05 percentile of embeddings with largest average cosine distance for all experiments. On the role of feature selection. The choice of feature extractor is necessarily domain-specific: n-gram matching is appropriate for detecting verbatim memorization in text, DLP-based PII detection targets semantically sensitive information, while embeddings capture semantic similarity. This flexibility allows auditors to test for precisely the types of disclosures they care about, and to obtain explanations of detected leakage (e.g., “the model leaked phone numbers from the training set”). In contrast, model-based MIAs produce a single membership score per record without explaining what 14
was leaked. We compare all feature types across all datasets and show that qualitative conclusions — rejection of the zero-learning null for non-DP methods (SFT and rewrites), failure to reject for DP-SGD — are robust to the choice of extractor (see Table 1). We now discuss the results of audits for each generation method.
6.2
Rewrites
We start by auditing rewrites for six public datasets: Finance [44], New York Times (NYT) comments4 ), Panorama, and Panorama+ [37], Postings [24], and Tweets5 . Section A.1 provides further information on each dataset. The Finance and Panorama and Panorama+ datasets are specifically designed to contain a large number of fictitious PII (e.g., names, phone numbers, bank account details). The Tweets and NYT datasets consist of diverse public internet user posts, which sometimes contain personal information linked to their authors. First we present the results of a two-sample test using the distributions of cosine similarities between training and holdout records to their nearest synthetic records. Specifically, we compare vectors {xi }i ⊆ Rd and {yi }i ⊆ Rd where xij is the cosine similarity between training record i and its j-th nearest synthetic record, and yij is analogously defined for holdout records. We set the rarity quantile to 0.05. The two-sample test shows that synthetic records are indeed more similar to training than to holdout records: we are able to reject the null hypothesis of zero learning in all datasets. Table 1: Feature Match statistics for Rewrites (k = 1). We report the estimated binomial parameter lower bound p̂, highlighting in bold the results for which the null hypothesis (p ≤ 0.5) is rejected at α = 0.05. Dataset
Feature extractor
Finance NYT comments Panorama Panorama+ Postings Tweets Finance NYT comments Panorama Panorama+ Postings Tweets
Disclosures
|F1 |
p̂
Total
Train
Holdout
DLP
1.5 × 104 35 3.6 × 104 2.3 × 104 3.3 × 104 68
31 – 39 2 121 –
17 – 37 1 116 –
14 – 2 1 5 –
0.315 – 0.743 0.000 0.836 –
Strings
5.0 × 107 6.9 × 107 7.6 × 107 4.3 × 106 7.7 × 108 3.1 × 106
28,278 1,368 8,362 43 8,245 128
26,602 1,358 8,293 23 4,492 127
1,676 10 69 20 3,753 1
0.792 0.308 0.548 0.131 0.456 0.533
We now switch to feature-match and user-match tests to interpret to measure the amount of leakage in terms of the lower bound for the privacy budget ε using strings, DLP, and embeddingbased audits. Raw disclosure counts. We first analyze raw disclosure counts to highlight the importance of distinguishing between true disclosures and phantoms. In Table 1, we report results for unique features held by exactly one user (k = 1) in the data set. (We explore the impact of varying the rarity parameter k in Section A.2.) All hypothesis testing results use the standard significance level 4 5
https://www.kaggle.com/datasets/aashita/nyt-comments https://www.kaggle.com/datasets/kazanova/sentiment140/data
15
α = 5%. Initial inspection of Table 1 reveals a high volume of rare features in the original data (|F1 |), ranging between 35 and 7.7 × 108 instances. We then use our framework to establish if these matches are evidence of actual leaks. Feature-match audit. We focus first on feature matches using DLP. Unsurprisingly given that we prompted explicitly the model to rewrite the data removing the PII, we find that many synthetic rewrite datasets have few or no PII disclosures. Nevertheless, as our audit shows, these disclosures can still happen and be significant privacy violation in some cases. For example, in the synthetic Postings dataset, we detect that out of the 121 total PII matches found, 116 are from the training set, while only 5 appear in the holdout set. The overwhelming excess of training matches over holdout matches provides strong evidence of leakage as confirmed by the binomial lower bound in Equation (6): p̂ = 0.84, rejecting the zero-learning hypothesis. This example highlights both that synthetic rewriting via LLMs is not always successful in removing privacy risk and that our framework can detect such remaining risk. Similar leakage is detected in the Panorama dataset. Similarly, using rare strings, we find significant leakage for Finance, Panorama, and Tweets for exact verbatim matches with the training data than the holdout, showing that even when instructing a model to avoid repetition, the model still replicates significant parts of input records exactly. Nevertheless, for some datasets we do not find evidence of leakage of verbatim substrings or PII (NYT comments, Tweets, or Panorama+) using feature-match tests alone. User-match audit. We next evaluate the performance of the User-Match test. To ensure a direct comparison with the state-of-the-art baseline by [32], we report the Area Under the Curve (AUC) as the evaluation metric, following their protocol. To evaluate the significance of the results we use the standard non-parametric Mann–Whitney–Wilcoxon test [29] (a.k.a. Mann–Whitney U test) for AUC (with significance level 5%). Table 2 summarizes the results.6 We observe that our test based on embeddings (semantic similarity) outperforms the Meeus et al.[32] baseline on all datasets. Moreover, both tests (embeddingand string-based) reveal that NYT comments and Tweets rewrites leak enough information to reidentify individual training records with significant accuracy: the AUC using semantic features is 0.93 for NYT comments and 0.86 for Tweets. To illustrate the risk, Table 4 shows some example training records paired with their closest synthetic matches, identified using our embedding-based approach. We observe often that substantial rephrasing is present, so these leaks would go unnoticed by standard n-gram based tests, including [32]. (More examples are reported in Section A.4.) Table 2: User Inference Attack AUC scores for Rewrites. Our User-Match test (specifically using embeddings) outperforms the canary-echo baseline. Asterisks indicate significant results using the Mann–Whitney–Wilcoxon test for AUC. Bold font indicates the best method in terms of AUC. Dataset
Strings (Ours)
Embeddings (Ours)
Canary-Echo Meeus et. al [32]
Finance NYT Comments Panorama Panorama+ Postings Tweets
0.65⋆ 0.73⋆ 0.73⋆ 0.48 0.49 0.68
0.53⋆ 0.93⋆ 0.52⋆ 0.65⋆ 0.75⋆ 0.86⋆
0.53⋆ 0.51⋆ 0.51⋆ 0.52⋆ 0.52⋆ 0.51⋆
6 Mann–Whitney–Wilcoxon test for AUC computes the p-value based on the deviation of AUC from 0.5, accounting for the number of positive and negative cases. When evaluating significant results, note that AUC alone is not a measure of statistical significance; a high AUC may not be significant in small sample sizes, while a modest AUC can be significant with large sample sizes.
16
DP-bounded tests. As introduced in section 5.1, we map the statistics from feature-match and user-match tests to differential privacy budgets ε via the DP-bounded learning tests. We present here the user-match ε values (derived via Theorem 3) and defer to Table 9 in Section A.5 the values derived from the feature-match p̂ estimates in Table 1 (which also map to positive ε estimates when p̂ > 0.5). Table 3 reports the results. The estimated ε values reach as high as 5.0 for Tweets and 5.3 for NYT, indicating substantial privacy leakage for these datasets under the rewriting procedure. Notice how our method using either embeddings or strings always outperforms the Meeus et al. baseline with embeddings being particularly effective. Table 3: User-match derived ε for a DP-bounded test, using DLP, strings, and embeddings extractors on synthetic data generated via rewrites. We present the estimated ϵ privacy budget lower bound. Dataset DLP Finance NYT Panorama Panorama+ Postings Tweets
0.0 0.0 1.65 0.0 2.30 0.0
ϵ (Ours) Strings Embeddings 2.04 0.65 0.81 0.0 0.02 1.29
ϵ (Meeus et al.[32])
0.25 5.28 0.99 0.80 2.73 5.01
1.77 0.09 0.26 0.39 0.24 0.16
Table 4: Examples of semantic and structural leakage from rewrites synthetic datasets. Training records are paired with their closest synthetic match using cosine similarity. Long texts are truncated for brevity. Across all datasets, rewrites leak semantic information from training data, which is captured by cosine distance in the embedding space. Dataset
Original Train Record (Cropped)
Closest (Cropped)
Synthetic
Record
NYT
... think that FIFA is going to void the championships ... owned by cocaine landlords such as the Rodriguez Orejuela... America, Nacional and Millonarios have not been punished...
... FIFA will ever revoke the league trophies ... subsidiaries of the Cali and Medellı́n cartels... Rodriguez Orejuela used their drug billions... America de Cali, Atletico Nacional, and Millonarios have kept their stars...
Panorama
Richard Hunt (born July 19, 1954...) is a dedicated childcare worker known for his lifelong commitment... born to Lance and Gabrielle Hunt...
Richard Hunt is a dedicated Canadian childcare worker... born on October 11, 1946... to Jeremy and Laura Hunt...
Interpretability and Efficiency. Beyond these numerical comparisons, our approach offers two key advantages over existing methods. First, the baseline evaluates privacy risk exclusively on inserted, out-of-distribution canaries, making it difficult to translate those metrics into realistic privacy risks for true records. In contrast, our User-Match test measures the disclosure of actual user data from the training corpus, yielding a more actionable and interpretable assessment of a 17
model’s privacy leakage regarding its training subjects. Second, our method captures semantic memorization that evades traditional verbatim filters. Even when a model reproduces training data, it often does so non-consecutively, scattering or reordering the leaked information throughout the generated output. Because standard n-gram or strict substring metrics require contiguous text overlap, they systematically fail to capture this dispersed leakage (as shown in table 4). Finally, our method is significantly more efficient, requiring only a single round of training and sampling. In contrast, the [32] procedure is computationally expensive, requiring the training of four separate reference models (shadow models) on disjoint subsets of canaries (in addition to the primary training corpus) to normalize membership scores of the audited synthetic data. Finally, we observe that our method does not require the insertion of canaries, simplifying its deployment. Nevertheless, is possible to optionally incorporate the canaries into our own auditing framework. Doing so yields similar results (see Section A.6).
6.3
SFT and DP generated synthetic data
We next audit two additional procedures used in the literature to generate synthetic datasets, namely supervised fine-tuning (SFT) and differentially private SFT through DP-SGD, focusing on the three datasets with explicit fictitious PII insertion: Finance, Panorama, and Panorama+.7 As with rewrites, we start with a two-sample test using the embedding similarity distributions for training and holdout records. For the rarity threshold of 0.05 we observe that this test rejects the null hypothesis for 2 of the three datasets: Finance, Panorama. (More results are reported in Section A.4). Feature-match tests. We continue with the feature-match test in Table 5. For the SFT models, we reject the null hypothesis of the zero-learning test (p ≤ 0.5) with high confidence in all datasets for at least one feature type (DLP or strings). The estimated lower bounds p̂ (bolded in Table 5) significantly exceed 0.5. In contrast, for the DP-SGD generation processes, all p̂ values are close to or less than 0.5. In all cases, we fail to reject the zero-learning null hypothesis. This again confirms the validity of our tests and the importance of accounting for phantom disclosures: while matches do occur even in DP data (e.g., 15 matches in Finance using DLP), they are distributed evenly between train and holdout, consistent with the random baseline. Table 7 reports the corresponding ε lower bounds for SFT; all DP-SGD estimates are zero. User-match tests. We evaluate the User-Match test on SFT and DP-SGD generated data. Table 6 summarizes the results. For SFT, at least one of our methods yields significant AUC for Finance and Panorama; results on DP-SGD data are not significant. Both of our proposed user-match tests outperform the Meeus et al. baseline on two of the three datasets, while Meeus et al. obtains significant results only on Panorama+ (both SFT and DP-SGD). Specifically, on the Finance dataset, we achieve an AUC of 0.63, significantly higher than the baseline’s 0.48. On Panorama, we achieve 0.53 compared to 0.50.
7
Conclusion
In this work, we introduced a causal auditing framework designed to distinguish between “true disclosures”—where the synthetic data contains private user information—and “phantom disclosures” arising from generalization or coincidence. Our approach provides a rigorous statistical mechanism to distinguish between these two cases and to audit the data against strong privacy bounds—such as zero-learning or specific Differential Privacy (DP) bounds. 7
Due to computational costs of generating the synthetic data, we limit ourselves to these datasets.
18
Table 5: Feature Match statistics using DLP and strings extractors on synthetic data generated from SFT and DP-SGD, for k = 1. We show the total number of disclosures appearing in either the train or holdout splits, and the counts of each split. We present the estimated binomial parameter lower bound p̂, and present in bold results where the null (p ≤ 0.5) is rejected at significance α = 0.05. Dataset
Feature
Disclosures
extractor
Total
Train
p̂
Holdout
Method: SFT Finance Panorama Panorama+
DLP
763 55 586
492 39 356
271 16 230
0.590 0.544 0.556
Finance Panorama Panorama+
strings
20,491 5,114 664
11,942 3,211 322
8,549 1903 342
0.827 0.654 0.390
Method: DP-SGD Finance Panorama+ Panorama
DLP
26 0 3
15 0 1
11 0 2
0.302 0.0 0.0
Finance Panorama+ Panorama
strings
13, 693 0 73
7,269 0 38
6,424 0 35
0.458 0.0 0.302
Our empirical evaluation confirms that while non-private synthetic data generation processes exhibit significant privacy leakage, disclosures observed in models trained with DP-SGD are statistically indistinguishable from phantom disclosures, validating the efficacy of formal privacy protections. Furthermore, our method offers an interpretable, efficient, and configurable framework to audit against a variety of privacy risks without the need to design canaries or train multiple reference models. Limitations and future work. Several directions remain open. First, our framework currently targets the setting where a data owner controls the train/holdout partition. Second, while our empirical lower bounds on ε are valid for the chosen feature set, tighter bounds may be achievable with richer features or more powerful tests. Finally, systematically evaluating disclosure rates across different base models, model scales, and generation paradigms would strengthen the empirical understanding of when and why true disclosures arise.
19
Table 6: User Inference Attack AUC scores for string features. We compare our User-Match test against the [32] baseline. We observe that [32] finds significant results only on the Panorama+ datasets and that our method outperforms the baseline on the Finance and Panorama datasets with Non-DP generated data while requiring 5× fewer computational resources for training and sampling. Dashes (-) indicate cases where insufficient matches were found to calculate an AUC. Asterisks indicate significant results using the Mann–Whitney–Wilcoxon test for AUC. Bold font indicates the best method in terms of AUC. Data Generation
Dataset
Substring features (Ours)
Embeddings features (Ours)
Canary-Echo Meeus et al. [32]
SFT
Finance Panorama Panorama+
0.63⋆ 0.53⋆ 0.48
0.53 0.52 0.50
0.48 0.50 0.56⋆
DP-SGD
Finance Panorama Panorama+
0.52 0.50 -
0.50 0.46 -
0.49 0.50 0.56⋆
Table 7: User-match derived ϵ lower bounds for the DP-bounded test on SFT-generated data, using DLP, strings, and embeddings extractors. All DP-SGD estimates are not significant (not shown). Dataset DLP
ϵ Strings Embeddings
Method: SFT Finance Panorama Panorama+
0.65 1.13 0.0
3.24 1.16 0.34
20
0.24 0.97 0.2
References [1] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 308–318, 2016. [2] John M Abowd. The us census bureau adopts differential privacy. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pages 2867–2867, 2018. [3] Federico Albanese, Pablo Ronco, and Nicolás D’Ippolito. Anonymous-by-construction: An llm-driven framework for privacy-preserving text. arXiv preprint arXiv:2603.17217, 2026. [4] Kareem Amin, Alex Bie, Wei Kong, Alexey Kurakin, Natalia Ponomareva, Umar Syed, Andreas Terzis, and Sergei Vassilvitskii. Private prediction for large-scale synthetic text generation. In Findings of the Association for Computational Linguistics: EMNLP 2024, pages 7244–7262, 2024. [5] Borja Balle, Giovanni Cherubin, and Jamie Hayes. Reconstructing training data with informed adversaries. In 43rd IEEE Symposium on Security and Privacy (SP), pages 1138–1156. IEEE, 2022. [6] Matteo Boglioni, Terrance Liu, Andrew Ilyas, and Zhiwei Steven Wu. Optimizing canaries for privacy auditing with metagradient descent. arXiv preprint arXiv:2507.15836, 2025. [7] Nicholas Carlini, Steve Chien, Milad Nasr, Shuang Song, Andreas Terzis, and Florian Tramèr. Membership inference attacks from first principles. In 2022 IEEE Symposium on Security and Privacy (S&P), pages 1897–1914. IEEE, 2022. [8] Nicholas Carlini, Daphne Ippolito, Matthew Jagielski, Katherine Lee, Florian Tramer, and Chiyuan Zhang. Quantifying memorization across neural language models, 2023. URL https://arxiv. org/abs/2202.07646, 2202, 2023. [9] Nicholas Carlini, Chang Liu, Úlfar Erlingsson, Jernej Kos, and Dawn Song. The secret sharer: Evaluating and testing unintended memorization in neural networks. In 28th USENIX security symposium (USENIX security 19), pages 267–284, 2019. [10] Dingfan Chen, Ning Yu, Yang Zhang, and Mario Fritz. Gan-leaks: A taxonomy of membership inference attacks against generative models. In ACM SIGSAC Conference on Computer and Communications Security, 2020. [11] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 265–284. Springer, 2006. [12] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography Conference (TCC), 2006. [13] Badih Ghazi, Cristóbal Guzmán, Pritish Kamath, Ravi Kumar, and Pasin Manurangsi. Differentially private optimization with sparse gradients. Advances in Neural Information Processing Systems, 37:63406–63440, 2024. [14] Anna Gilbert and Audra McMillan. Property testing for differential privacy, 2019. 21
[15] Google. Cloud Data Loss Prevention (Cloud DLP) api. https://docs.cloud.google.com/ sensitive-data-protection/docs/infotypes-reference, 2026. Accessed: 2026-02-07. [16] Chuan Guo, Brian Karrer, Kamalika Chaudhuri, and Laurens van der Maaten. Bounding training data reconstruction in private (deep) learning. In International Conference on Machine Learning (ICML), 2022. [17] Skyler Hallinan, Jaehun Jung, Melanie Sclar, Ximing Lu, Abhilasha Ravichander, Sahana Ramnath, Yejin Choi, Sai Praneeth Karimireddy, Niloofar Mireshghallah, and Xiang Ren. The surprising effectiveness of membership inference with simple n-gram coverage. arXiv preprint arXiv:2508.09603, 2025. [18] Benjamin Hilprecht, Martin Härterich, and Daniel Bernau. Reconstruction and membership inference attacks against generative models. arXiv preprint arXiv:1906.03006, 2019. [19] Paul W Holland. Statistics and causal inference. Journal of the American Statistical Association, 81(396):945–960, 1986. [20] Matthew Jagielski, Jonathan Ullman, and Alina Oprea. Auditing differentially private machine learning: How private is private SGD? Advances in Neural Information Processing Systems, 33:22205–22216, 2020. [21] Bargav Jayaraman and David Evans. Evaluating differentially private machine learning in practice. In USENIX Security Symposium, 2019. [22] James Jordon, Lukasz Szpruch, Florimond Houssiau, Mirko Bottarelli, Giovanni Cherubin, Carsten Maple, Samuel N Cohen, and Adrian Weller. Synthetic data–what, why and how? arXiv preprint arXiv:2205.03257, 2022. [23] Bryan Klimt and Yiming Yang. The enron corpus: A new dataset for email classification research. In European conference on machine learning, pages 217–226. Springer, 2004. [24] Arsh Koneru. Linkedin job postings (2023 - 2024), 2024. [25] Alexey Kurakin, Natalia Ponomareva, Umar Syed, Liam MacDermed, and Andreas Terzis. Harnessing large-language models to generate private synthetic text. arXiv preprint arXiv:2306.01684, 2023. [26] Zinan Lin, Tadas Baltrusaitis, Wenyu Wang, and Sergey Yekhanin. Differentially private synthetic data via apis 3: Using simulators instead of foundation model. arXiv preprint arXiv:2502.05505, 2025. [27] Zinan Lin, Sivakanth Gopi, Janardhan Kulkarni, Harsha Nori, and Sergey Yekhanin. Differentially private synthetic data via foundation model apis 1: Images. arXiv preprint arXiv:2305.15560, 2023. [28] Justus Mattern, Zhijing Jin, Benjamin Weggenmann, Bernhard Schoelkopf, and Mrinmaya Sachan. Differentially private language models for secure data sharing. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing (EMNLP 2022), pages 4860–4873. ACL, 2022. [29] Patrick E McKnight and Julius Najab. Mann-whitney u test. The Corsini encyclopedia of psychology, pages 1–1, 2010. 22
[30] Matthieu Meeus, Florent Guepin, Ana-Maria Creţu, and Yves-Alexandre de Montjoye. Achilles’ heels: vulnerable record identification in synthetic data publishing. In European Symposium on Research in Computer Security, pages 380–399. Springer, 2023. [31] Matthieu Meeus, Igor Shilov, Manuel Faysse, and Yves-Alexandre De Montjoye. Copyright traps for large language models. arXiv preprint arXiv:2402.09363, 2024. [32] Matthieu Meeus, Lukas Wutschitz, Santiago Zanella-Béguelin, Shruti Tople, and Reza Shokri. The canary’s echo: Auditing privacy risks of llm-generated synthetic text. arXiv preprint arXiv:2502.14921, 2025. [33] Milad Nasr, Jamie Hayes, Thomas Steinke, Borja Balle, Florian Tramèr, Matthew Jagielski, Nicholas Carlini, and Andreas Terzis. Tight auditing of differentially private machine learning. In 32nd USENIX Security Symposium (USENIX Security 23), pages 1631–1648, 2023. [34] Natalia Ponomareva, Zheng Xu, H Brendan McMahan, Peter Kairouz, Lucas Rosenblatt, Vincent Cohen-Addad, Cristóbal Guzmán, Ryan McKenna, Galen Andrew, Alex Bie, et al. How to dp-fy your data: A practical guide to generating synthetic data with differential privacy. arXiv preprint arXiv:2512.03238, 2025. [35] USVSN Sai Prashanth, Alvin Deng, Kyle O’Brien, Jyothir SV, Mohammad Aflah Khan, Jaydeep Borkar, Christopher A Choquette-Choo, Jacob Ray Fuehne, Stella Biderman, Tracy Ke, et al. Recite, reconstruct, recollect: Memorization in lms as a multifaceted phenomenon. arXiv preprint arXiv:2406.17746, 2024. [36] Shadi Rahimian, Tribhuvanesh Orekondy, and Mario Fritz. Differential privacy defenses and sampling attacks for membership inference. In ACM Workshop on Artificial Intelligence and Security, 2021. [37] Sriram Selvam and Anneswa Ghosh. Panorama: A synthetic pii-laced dataset for studying sensitive data memorization in llms. arXiv preprint arXiv:2505.12238, 2025. [38] Weijia Shi, Anirudh Ajith, Mengzhou Xia, Yangsibo Huang, Daogao Liu, Terra Blevins, Danqi Chen, and Luke Zettlemoyer. Detecting pretraining data from large language models. arXiv preprint arXiv:2310.16789, 2023. [39] Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In 2017 IEEE symposium on security and privacy (SP), pages 3–18. IEEE, 2017. [40] Thomas Steinke, Milad Nasr, and Matthew Jagielski. Privacy auditing with one (1) training run. Advances in Neural Information Processing Systems, 36:49268–49280, 2023. [41] Xinyu Tang, Richard Shin, Huseyin A Inan, Andre Manoel, Fatemehsadat Mireshghallah, Zinan Lin, Sivakanth Gopi, Janardhan Kulkarni, and Robert Sim. Privacy-preserving in-context learning with differentially private few-shot generation. In 12th International Conference on Learning Representations (ICLR 2024), 2024. [42] Gemma Team, Thomas Mesnard, Cassidy Hardin, Robert Dadashi, Surya Bhupatiraju, Shreya Pathak, Laurent Sifre, Morgane Rivière, Mihir Sanjay Kale, Juliette Love, et al. Gemma: Open models based on gemini research and technology. arXiv preprint arXiv:2403.08295, 2024.
23
[43] Johnny Tian-Zheng Wei, Ryan Yixiang Wang, and Robin Jia. Proving membership in llm pretraining data via data watermarks. arXiv e-prints, pages arXiv–2402, 2024. [44] Alex Watson, Yev Meyer, Maarten Van Segbroeck, Matthew Grossman, Sami Torbey, Piotr Mlocek, and Johnny Greco. Synthetic-PII-Financial-Documents-North-America: A synthetic dataset for training language models to label and detect pii in domain specific formats, June 2024. [45] Chulin Xie, Zinan Lin, Arturs Backurs, Sivakanth Gopi, Da Yu, Huseyin A Inan, Harsha Nori, Haoming Jiang, Huishuai Zhang, Yin Tat Lee, Bo Li, and Sergey Yekhanin. Differentially private synthetic data via foundation model apis 2: Text. In Proceedings of the 41st International Conference on Machine Learning (ICML 2024), volume 235, pages 54531–54560. PMLR, 2024. [46] Jiayuan Ye, Aadithya Maddi, Sumanth K Murakonda, Vincent Bindschaedler, and Reza Shokri. Enhanced membership inference attacks against machine learning models. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security (CCS 2022), pages 3093–3106. ACM, 2022. [47] Xiang Yue, Huseyin Inan, Xuechen Li, Girish Kumar, James McAnallen, Huseyin Shajari, Huan Sun, David Levitan, and Robert Sim. Synthetic text generation with differential privacy: A simple and practical recipe. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1321–1342. ACL, 2023. [48] Sajjad Zarifzadeh, Philippe Liu, and Reza Shokri. Low-cost high-power membership inference attacks. arXiv preprint arXiv:2312.03262, 2023.
24
A
Experimental details
A.1
Datasets
We leverage three existing publicly available datasets for synthetic data generation. Finance This dataset contains 55,940 fictitious financial records generated using the Gretel package. It contains financial documents with distinct PII types in different languages. For details on the generation, document and PII subcategories, and software, see [44]. This dataset contains 82 unique prompts specifying the type of document (e.g. a statement, a formal document, insurance claim) and the type of sensitive features to include (e.g. patient information and diagnosis or income). One example is “A form capturing personal, financial, and employment details of a loan applicant, including loan amount, purpose, and supporting documents.” NYT comments This dataset contains comments on articles published in the New York Times during the preiod of January through May 2017, and January through April 2018. We sample 100,000 records. Panorama The Panorama dataset introduced by [37] contains 384,789 records from 9674 fictitious user profiles emulating online activity by the users (e.g., social media posts). The records contains personally identifiable information from the (fictitious) authors of the content designed to evaluate PII detection methods and LLM auditing tools. We accessed the dataset on December 1, 2025. The dataset contains six different prompts of the form “write a [content-type]” where content-type is a field specified for each record and corresponds to one of the categories wiki-style articles, social media posts, forum discussions, online reviews, comments, and marketplace listings. Panorama+ The Panorama Plus dataset, also introduced by [37], contains 9,674 structured user profiles that serve as the ground truth identities for the Panorama dataset. This dataset has the explicit PII attributes for each fictitious user, including full names, family details, socioeconomic status, health attributes, and other sensitive demographics. We accessed the dataset on December 1, 2025. Postings This is a dataset [24] containing job postings from LinkedIn listed in 2023 and 2024. Tweets This dataset contains tweets extracted using the twitter API. We sample 100,000 records.
A.2
Impact of Feature Rarity (k)
While the main text focuses on unique features (k = 1), we extend our analysis here to features shared by multiple users. Figure 3 plots the estimated lower bound of the binomial parameter, p̂, as a function of the rarity parameter k. We observe that |Fk | (the number of features appearing in the synthetic output that are shared by exactly k users in the original corpus) decreases as k increases. This reduction in the effective sample size leads to looser estimates of p̂. As the number of available matches diminishes, the statistical confidence decreases, making it increasingly hard to distinguish true disclosures from phantoms. To illustrate this, Figure 2 presents the point estimate for the binomial parameter (computed as T obs /ℓk). The shaded region indicates the confidence interval. While all tests are significant for k = 1, the lower bound diverges from the point estimate as feature counts increases. Larger values of k are primarily relevant for datasets where users share secrets, resulting in correlated or shared features. In contrast, the datasets studied here are synthetic and generated via independent sampling for each user.
25
DLP
Strings
0.8
p
0.6
Null: p=0.5
Null: p=0.5
dataset
Panorama Finance Panorama+
0.4 0.2 0.0
2
4
6
8
Number of records with feature overall
10
2
4
6
8
Number of records with feature overall
10
Figure 2: Impact of feature rarity (k) on the audit lower bound p̂. As k increases (features shared by more records), the number of valid audit features |Fk | decreases. This reduction in sample size leads to looser statistical bounds, reducing the power of the tests.
Test statistic and CI lower bound.
DLP
Strings
0.8 0.6
Null: p=0.5
Null: p=0.5
0.2 0.0
Dataset
Panorama Finance Panorama+
0.4
2
4 6 8 Number of records with feature overall
10
2
4 6 8 Number of records with feature overall
10
Figure 3: Point estimates and confidence intervals for varying k. The solid line represents the empirical match rate (point estimate). The shaded region illustrates the gap between the point estimate and the conservative lower bound p̂ used for auditing. The gap highlights the increased statistical uncertainty caused by the lack of non-unique features in the synthetic corpus at higher frequencies.
26
Finance
Rejects
Rejects
Rejects
NYT
Rejects
Rejects
No evidence
Panorama
Rejects
No evidence
No evidence
Panorama+
Rejects
Rejects
Rejects
Postings
Rejects
No evidence
No evidence
Tweets
Rejects
Rejects
No evidence
0.1
0.5
0.05
Rarity Threshold
Figure 4: Two-sample test results comparing the distribution of cosine similarities between training records and synthetic rewrites against the distribution of cosine similarities between holdout records and synthetic rewrites. As we include more common records, the power of the test decreases for most datasets.
Finance
Rejects
Rejects
Rejects
Panorama
Rejects
Rejects
No evidence
Panorama+
No evidence
No evidence
Rejects
0.1
0.5
0.05
Rarity Threshold
Figure 5: Two-sample test comparing distributions of training-to-synthetic and holdout-tosynthetic embedding similarities for SFT generated data .
A.3
Impact of rarity threshold on the two-sample test
In Figure 4 we report results for the effect of the rarity threshold on the two-sample test on the rewrite data. Notice that in all datasets, the rarity threshold 0.05 is significant. As we include more common records in the test (i.e., as the rarity threshold increases), the distributions become to distinguish. Nevertheless we observe that the test is able to identify significant leakage in all datasets for low thresholds. In Figure 5 we report results for SFT. Unlike rewrites, as we increase the rarity threshold, the test can becomes more powerful in some cases. This is consistent observations of [32], finetuned models are more likely to generate common patterns than rare unique features. Thus, by considering more rare embeddings, it is less likely to find matches in the synthetic data, as these rare patterns may not have been learned by the fine-tuned model yet or may require a larger number of synthetic samples to appear.
27
A.4
Example matches identified by the embedding-based method
We report in Table 8 more examples of matches identified by the embedding-based method for datata obtained by rewrite. Notice the ability of the method to identify leakage even in the presence of extensive rewriting.
A.5
DP-bounded learning tests
We present the results for DP-bounded learning tests on Non-DP generated data. The p̂ estimated values map to positive ε estimates, confirming significant privacy violation. We present these results in Table 9. All ϵ estimates for DP-SGD generated data are not significant. This means we fail to reject the hypothesis of positive ϵ values based on the synthetic data. This confirms the positive effect of using Differential Privacy in preventing true disclosures.
A.6
Feature and user match audits with canaries.
Our framework can easily be adapted to work with canaries by simply inserting the train canaries to the train set Dtrain , and holdout canaries to the holdout set Dhold . We present these results in Table 10. Adding canaries yields mixed results, providing a slight performance boost on Panorama (0.533 → 0.549) but showing negligible impact on Finance. In the DP settings, most scores lie near the random baseline of 0.5 or fail to produce sufficient matches (indicated by “-”), consistent with the privacy guarantees of the model. We highlight that, while increasing MIA scores is desirable and adding canaries can help with this, it does not necessarily provide a causal explanation for natural data disclosures, which is the focus of the present work. However, exploring how to combine these methods is an interesting avenue of future work.
B
P-Value Interpretation
P-value. Instead of committing to a specific significance level α in advance, the auditor may report a p-value, which summarizes how strongly the data speak against the zero-learning hypothesis. A concrete type I error guarantee is obtained once a decision threshold α is fixed a priori and the rule “reject if pval ≤ α” is adopted. Lemma 2. Define pval :=
( −ℓkp)2 Pn exp − 2(T , 2 d i=1
1
if T ≥ ℓkp,
i
otherwise
Then, pval is a valid p-value for the zero learning hypothesis, i.e, Pr(pval ≤ t) ≤ t for any t ∈ [0, 1]. Proof of Lemma 2. Recalling (4) we have the following for any t > 0, 2t2 Pr(T − ℓkp ≥ t) ≤ exp − Pn
2 i=1 di
(9)
We consider two cases. • Case 1: T < ℓkp. Then pval = 1 ≥ t for any t ∈ [0, 1], so the event {pval ≤ t} has probability zero.
28
Table 8: Examples of semantic and structural leakage from rewrites synthetic datasets. Training records are paired with their closest synthetic match using cosine similarity. Long texts are truncated for brevity. Across all datasets, rewrites leak semantic information from training data, which is captured by cosine distance in the embedding space. Dataset
Original Train Record (Cropped)
Closest Synthetic Record (Cropped)
NYT
... think that FIFA is going to void the championships ... owned by cocaine landlords such as the Rodriguez Orejuela... America, Nacional and Millonarios have not been punished...
... FIFA will ever revoke the league trophies ... subsidiaries of the Cali and Medellı́n cartels... Rodriguez Orejuela used their drug billions... America de Cali, Atletico Nacional, and Millonarios have kept their stars...
Panorama
Richard Hunt (born July 19, 1954...) is a dedicated childcare worker known for his lifelong commitment... born to Lance and Gabrielle Hunt...
Richard Hunt is a dedicated Canadian childcare worker... born on October 11, 1946... to Jeremy and Laura Hunt...
Finance
09:00:01 - Job Ferran: Goedemorgen, bedankt voor de hulp. Ik heb moeite met het aanmaken van mijn account. ...
10:01:22 Customer: Goedemorgen/nedeem/middag, ik heb moeite met het aanmaken van mijn account. ...
Finance
MsgType=35 SenderCompID=AcmeBroker TargetCompID=Exchange BeginString=FIX.5.0 News=Market volatility expected...
... MessageType = 35 SenderCompID = AcmeTrading TargetCompID = Exchange NewsType = 35 NewsText = ”Acme Trading announces significant market volatility”...
Panorama+
[...] children count: 0 credit score: 521 disability: None drivers license: GB-DL-6687495077 employer: Group Store fathers name: Antony Simmons finance status: Low first name: Georgia gender: Female job title: Retail Sales Associate last name: Simmons locale: en GB marital status: Single mothers name: Shirley Simmons national id: GB-ID-9261993 nationality: British net worth: £8342.85 [...] spouse name: N/A
children count: 0 credit score: 612 disability: None drivers license: GBDL-71839502649 [...] employer: Retail Group Ltd fathers name: Mark Simmons finance status: Medium first name: Chloe gender: Female job title: Sales Assistant last name: Simmons locale: en GB marital status: Single mothers name: Sarah Simmons national id: GB-ID-8829401 nationality: British net worth: £-1150.40 spouse name: N/A [...]
Tweets
According to the 2009 Cedar Point Rider Safety guide, I am 30 lbs too heavy, 3 inches too tall, and chest measurement that is too large
Based on the 2015 Alton Towers Accessibility and Health Manual, my current stats put me 14 kilograms over the limit, 8 centimeters past the height ceiling, and possessed of a shoulder span that simply won’t clear the harness lock.
29
Table 9: Feature Match statistics for a DP-bounded test, using DLP and strings extractors on synthetic data generated for Non-DP. We present the estimated ϵ privacy budget lower bound, and present in bold results where the null is rejected at significance α = 0.05. All DP-SGD estimates are not significant. Feature extractor
Dataset
ϵ
Method: SFT Finance Panorama+ Panorama
DLP
0.364 0.223 0.177
Finance Panorama+ Panorama
Strings
1.561 0.0 0.636
Table 10: User Match AUC scores for string features (n ∈ [11, 20]). We compare our User-Match test (with and without canaries) against the Canary-Echo baseline. Our framework outperforms the baseline on the Finance and Panorama datasets while requiring 5× fewer computational resources for training and sampling. Dashes (-) indicate cases where insufficient matches were found to calculate an AUC. Asterisks indicate significant results using the Mann–Whitney–Wilcoxon test for AUC. Bold font indicates the best method in terms of AUC. Ours Generation Model
Dataset
Baseline
User Match
User Match (+ Canaries)
Canary-Echo Meeus et al.[32]
Non-DP
Finance Panorama Panorama+
0.63⋆ 0.53⋆ 0.48
0.63⋆ 0.55⋆ 0.47
0.47 0.50 0.55⋆
DP-SGD
Finance Panorama Panorama+
0.52 0.50 -
0.47 0.38 -
0.49 0.50 0.56⋆
−ℓkp)2 −ℓkp)2 Pn Pn ≤ t ⇔ − 2(T ≤ • Case 2: T ≥ ℓkp. The event {pval ≤ t} is equivalent to exp − 2(T 2 2 d i=1 i i=1 di q P log t ⇔ T − ℓkp ≥ 12 ( ni=1 d2i ) log(1/t) where we used that T ≥ ℓkp and log t < 0 for t ∈ [0, 1). Using (9) with this threshold, the last term has probability at most t. Since {pval ≤ t} ⊆ {T ≥ ℓkp}, we obtain Pr(pval ≤ t) ≤ t. The two cases together show that pval is a valid p-value. Likewise, we can construct the p-value for testing the DP-bounded learning hypothesis. Let p qϵ := p+(1−p)e −ϵ and define pval :=
( obs 2 ϵ) exp − 2(TPn−ℓkq , 2 d i=1
1
i
if T obs ≥ ℓkqϵ , otherwise
Then, pval is a valid p-value for the DP-bounded learning hypothesis, i.e, Pr(pval ≤ t) ≤ t for any 30
t ∈ [0, 1]. The proof of validity follows along the same lines as in the proof of Lemma 2 and is omitted.
C
Proof of theorems and technical lemmas
C.1
Proof of Lemma 1
As P discussed in (3), under the zero-learning hypothesis, the test statistic T has the same distribution as ni=1 di si , with si ∈ {0, 1} independent Bernoulli random variables with Pr(si = 1) = p. Hence, by applying Hoeffding bound with the threshold tα , we obtain Pr(T − ℓkp > tα ) ≤ α ,
(10)
Pr(T − ℓkp ≤ tα ) ≥ 1 − α ,
(11)
or equivalently
The event {T − ℓkp ≤ tα } is equivalent to the event {(T − tα )/(ℓk) ≤ p}. Hence, with probability at least 1 − α, we have hT − t i α p∈ ,1 , ℓk which completes the proof.
C.2
Proof of Theorem 1
For each record i ∈ [n], let si ∈ {0, 1} be the indicator that record i belongs to the training set Dtrain (denoted by si = 1) or the hold-out set Dhold (denoted by si = 0). For each feature j ∈ F, let oj ∈ {0, 1} be the indicator that feature j appears in the synthetic output. We write o = M(s) with o ∈ {0, 1}|F | and s ∈ {0, 1}n . We first establish upper and lower tail bounds for the distribution of the test statistic under the DP-bounded learning hypothesis. Our proof strategy follows the lines of Proposition 5.1 in [40], but generalizes their analysis from the special case p = 1/2 to arbitrary sampling probabilities p ∈ (0, 1). More importantly, our test statistic—based on feature-unit incidence patterns—requires a different analysis. Proposition 1. Suppose that the mechanism M is ϵ-DP. Conditional on the synthetic P features ∗ in the output (o = o ), the test statistic from (2) is stochastically dominated by i∈[n] di zi , n where {z } are i.i.d. Bernoulli(q ) random variables. In addition, it stochastically dominates i i=1 ϵ P ′ ′ ′ n i∈[n] di zi , where {zi }i=1 are i.i.d. Bernoulli(qϵ ) random variables, with p p , qϵ := p + (1 − p)eϵ p + (1 − p)e−ϵ P P Formally, for any value v ∈ R, Pr( ni=1 di zi′ ≥ v|o = o∗ ) ≤ Pr(T ≥ v|o = o∗ ) ≤ Pr( ni=1 di zi ≥ v|o = o∗ ) P P n Using Proposition 1, we have Pr(T ≥ cϵ,α |o = o∗ ) ≤ Pr( ni=1 di zi ≥ cϵ,α |o = o∗ ) = Pr i=1 di zi − q Pn qϵ i=1 di ≥ ∥d∥2 12 log(1/α) o = o∗ ≤ α , where the last step follows from the Hoeffding bound P applied to the sum ni=1 di zi . Note that conditional on o = o∗ , the quantities di become deterministic. The result then follows by marginalizing over the output o. qϵ′ :=
31
C.2.1
Proof of Proposition 1
We use asterisks s∗ , o∗ to indicate a realization of vectors s = (s1 , . . . , sn ) and o = (o1 , . . . , ..., o|F | ). Fix i ∈ [n], and s∗<i ∈ {0, 1}i−1 . By Bayes’ law Pr(si = 1|M(s) = o∗ , s<i = s∗<i ) Pr(M (s) = o∗ |si = 1, s<i = s∗<i ) Pr(si = 1|s<i = s∗<i ) = Pr(M(s) = o∗ |s<i = s∗<i )
(12)
We have Pr(si = 1|s<i = s∗<i ) = Pr(si = 1) = p as the records are included in the training set independently. We also have Pr(M(s) = o∗ |s<i = s∗<i ) = Pr(M(s) = o∗ |si = 1, s<i = s∗<i ) Pr(si = 1) + Pr(M(s) = o∗ |si = 0, s<i = s∗<i ) Pr(si = 0) = Pr(M(s) = o∗ |si = 1, s<i = s∗<i )p + Pr(M(s) = o∗ |si = 0, s<i = s∗<i )(1 − p)
(13)
By definition of ϵ-DP we have Pr(M(s) = o∗ |si = 1, s<i = s∗<i ) ∈ [e−ϵ , eϵ ] , Pr(M(s) = o∗ |si = 0, s<i = s∗<i )
(14)
which along with (13) implies that Pr(M(s) = o∗ |s<i = s∗<i ) Pr(M(s) = o∗ |si = 1, s<i = s∗<i ) ∈ p + (1 − p)e−ϵ , p + (1 − p)eϵ
(15)
Using this bound in (12) we obtain " Pr(M(s) = o|s<i = s∗<i ) ∈
1
#
1
, 1−p −ϵ ϵ 1 + 1−p p e 1+ p e
.
(16)
We proceed by proving the P claim via induction on the number of records n. Note that the test statistics can be written as i∈[n],j∈[|F |] si δij oj where δij = 1 if feature j appears in record i and δij = 0 otherwise. We have X si δij oj i∈[n],j∈[|F |]
=
X
si δij oj + sn
i∈[n−1],j∈[|F |]
=
X
X
δnj oj
j∈[|F |]
si δij oj + dn sn ,
i∈[n−1],j∈[|F |]
where the last equality holds since dn is defined as the number of features in the output that appear in record n. P ∗ By the induction hypothesis, Pconditional on o = o , the partial test statistic Tn−1 := i∈[n−1],j∈[|F |] si δij oj is stochastically dominated by i∈[n−1] di zi . Moreover, as shown above, conditioning on (o, s1 , . . . , sn−1 ), the variable sn is stochastically dominated by zn ∼ Bernoulli(qϵ ). Since dn is measurable with respect to o, it follows that dn sn is dominated by dn zn . Lemma 3 below then implies that, conditional on (o, Tn−1 ), dn sn is stochastically dominated by dn zn . 32
Lemma 3. If X|U is stochastically dominated by Y |U , then for any deterministic function f , X|f (U ) is stochastically dominated by Y |f (U ). To complete the induction step, we apply [40, Lemma 9], stated here for convenience: Lemma 4. Suppose X1 is stochastically dominated by Y1 . Suppose that, for all x ∈ R, the conditional distribution X2 |X1 = x is stochastically dominated by Y2 . Assume that Y1 and Y2 are independent. Then X1 + X2 is stochastically dominated by Y1 + Y2 . Using lemma 4 for X1 = Tn−1 (conditional on o = o∗ ) X di zi (conditional on o = o∗ ) Y1 = i∈[n−1]
X2 = dn sn (conditional on o = o∗ ) Y2 = dn zn (conditional on o = o∗ ) Lemma 4 yields the desired result. A nearly identical argument applies to obtain the claimed lower tail bound using zi′ . −1 (b). Then Pr(X ≥ v | f (U ) = b) = Pr(X ≥ v | U ∈ Ω ) = Proof of Lemma 3 Let b R Ωb = f Pr(U ∈Ωb |X≥v)Pr(X≥v) = Pr(U ∈Ωb )
have
Ωb Pr(U =u|X≥v) du Pr(U ∈Ωb )
Pr(X ≥ v). Since X|U = u is dominated by Y |U = u, we
Pr(X ≥ v|U = u) ≤ Pr(Y ≥ v|U = u), and thus Pr(U = u|X ≥ v)Pr(X ≥ v) ≤ Pr(U = u|Y ≥ v)Pr(Y ≥ v). Substituting this bound yields Pr(X ≥ v | f (U ) = b) R Ω Pr(U = u | Y ≥ v) du ≤ b Pr(Y ≥ v) Pr(U ∈ Ωb ) = Pr(Y ≥ v | f (U ) = b), which completes the proof. □
C.3
Proof of Theorem 2
By Proposition 1, under the DP-bounded learning hypothesis and conditional on the observed outP put, the test statistic T is stochastically dominated by ni=1 di zi where zi ∼ Ber(qϵ ), independently. Hoeffding’s inequality then yields ! n X 2t2 . Pr di zi − qϵ ∥d∥1 ≥ t ≤ exp − ∥d∥22 i=1 Setting t = ∥d∥2
p (1/2) log(1/α) gives Pr
n X
! p di zi ≥ qϵ ∥d∥1 + ∥d∥2 (1/2) log(1/α)
i=1
33
≤ α.
Thus, with probability at least 1 − α, T ≤ qϵ ∥d∥1 + ∥d∥2
p (1/2) log(1/α)
p Rearranging and substituting qϵ = p+(1−p)e −ϵ yields
T ∥d∥2 A := − ∥d∥1 ∥d∥1
r
1 p . log(1/α) ≤ 2 p + (1 − p)e−ϵ
Solving for ϵ gives the lower bound ϵ ≥ ϵ′∗P . Likewise, T stochastically dominates ni=1 di zi , where zi ∼ Ber(qϵ ), independently. The onesided Hoeffding bound gives ! n X p ′ ′ Pr di zi ≤ qϵ ∥d∥1 − ∥d∥2 (1/2) log(1/α) ≤ α , i=1
or equivalently, Pr
n X
! di zi′ ≥ qϵ′ ∥d∥1 − ∥d∥2
p (1/2) log(1/α)
≥ 1−α.
i=1
Thus, with probability at least 1 − α, T ≥ qϵ′ ∥d∥1 − ∥d∥2
p (1/2) log(1/α).
Rearranging the terms yields T ∥d∥2 B := + ∥d∥1 ∥d∥1
r
1 p log(1/α) ≥ qϵ′ = . 2 p + (1 − p)eϵ
Solving for ϵ gives the lower bound ϵ ≥ ϵ′′∗ . Combining these bounds, under the ϵ-DP hypothesis we have ϵ ≥ ϵ∗ = max(ϵ′∗ , ϵ′′∗ ), with probability at least 1 − α.
C.4
Proof of Theorem 3
We recall that the vector s ∈ {0, 1}n encodes which records are in the training set or the hold-out set. Let u ∈ {−1, 0, 1}n with ui := Φ(g(xi , Y )) denoting the adversary’s guess of si . Under the null hypothesis, M is ϵ-DP and P so by the postprocessing property of DP, u is an ϵ-DP function of s. By definition, wtrain = ni=1 max{0, u(si )si }. By a similar argument as in Proposition 5.1 in [40], we have ! n X Pr max{0, u(si ) · si } ≥ v u(s) = u i=1
≤ Pr
n X
! S̃i |ui | ≥ v
,
i=1
where S̃i ∼ Bern
p p+(1−p)e−ε
are independent random variables.
34
Since Φ can “abstain” to make predictions for certain scores, let r(u) be the number of predictions given u = u(s). We can average over the zeroed bernoullis to get that ! n X Pr S̃i |ui | ≥ v = Pr(X ≥ v) (17) i=1
p where X ∼ Binomial r, p+(1−p)e −ϵ . By combining the previous equations, we get Pr(wtrain ≥ v | u(s) = u) ≤ Pr(X ≥ v) . p By setting v = c̃ϵ,α , the (1 − α)- quantile of Binomial r, p+(1−p)e −ϵ , we get Pr(wtrain ≥ c̃ϵ,α | u(s) = u) ≤ α , which completes the proof.
35