On the Inadequacy of Similarity-based Privacy Metrics: Reconstruction Attacks against ``Truly Anonymous Synthetic Data''

We thank the reviewer for their detailed review and helpful comments. We made several changes (summarized in the common message above). Here, we address individual comments.

Weaknesses:

These datasets were commonly known as the relatively ‘trivial’ ML tasks, mainly because of how simple they are. Therefore, reconstructing this data (as shown in works such as [1,2,3,4]) is A) relatively straightforward even with simple inversion attacks and B) is very often due to a very limited reconstruction space that the adversary is present with (i.e. there are many ways to define a valid number in MNIST, for instance).

I would argue that this, in part, violates your threat model and really harms the applicability of your method to real-world imaging tasks.

The primary focus of our paper, in terms of data modality, is tabular data. All companies and privacy metrics studied in App. A offer solutions for tabular data. Additionally, the studied DP generative models (potentially with the exception of DPGAN) in App. C.1 were originally proposed for tabular data. (we added clarifications in Sec. 1 and App. C.1) As such, Adult and Census are datasets used in numerous studies.

A) Unlike [1,2,3,4] which either have white-box access to the target model and/or observe the gradients and/or posses other auxiliary information such as representable publicly available train data, we (in addition to the metrics, which leak privacy) only assume a black-box access to a single trained generative model and no other side information. Therefore, we cannot use any of the proposed techniques which makes the reconstruction challenging.

B) Compared to previous black-box attacks vs synthetic data, we study more datasets, 6 (vs 2 for both (Stadler et al., 2022, Annamalai et al., 2023), with much higher dimensionality, 65 (vs 18/10 for (Stadler et al., 2022, Annamalai et al., 2023). In other words, the reconstruction space is far greater than previous studies. Also in the case of MNIST, our reconstruction accuracy is pixel wise.

Therefore, I would like to see similar results being presented on non-trivial tasks to show that the proposed flaws do affect more realistic settings too.

As mentioned above, we used datasets of a much higher dimensionality and domain support. As such, we respectfully argue that they are non-trivial and represent realistic settings in the context of tabular synthetic data.

It was previously shown that models such as DPGAN, for instance, are not particularly great at generating meaningful datasets when there are outliers which need to be represented (which is, again, poorly captured in datasets such as MNIST).

To the best of our knowledge, DPGAN is still widely used for private tabular data generation, given that a variation of it won a NIST competition [5]. We agree that it potentially is not great at generating underrepresented data records (especially if there is a high imbalance and a strict privacy budget is applied, as visible in Fig. 6). Our experiments confirm that since our attack is consistently least effective against DPGAN. However, this could be interpreted that we do not need high utility models to reconstruct records successfully due to the severe metrics leakage.

I agree that issue 4 correctly identifies the issues when adversarial samples are present - but this is also an assumption applicable to almost all ML settings too?

In many ML settings, such as classification, regression, etc., we usually care about the average-case or how well the model generalizes. For privacy problems, however, we require some level of guarantee and should instead care about the worst-case scenario. In this context, DP is a worst-case guarantee, while the privacy metrics look at the average-case.

Same for issue 5: while I agree that it is often easy to misinterpret what SPBM mean numerically, the same can be said about DP (which given issue 1 is ‘supposed to be’ an alternative to SPBMs as it gives you objective guarantees), which has a privacy parameter often poorly interpreted and contextualised.

My concrete suggestion here would be to tone down some of the issues (and maybe consider if all of them are really relevant to these specific methods you present) and then use the space that you gained to include more information on how the attack works in the main body.

We agree that DP is also often misinterpreted (or difficult to interpret) and discuss that in App. I.1. We moved Issue 5 (now Issue 6) to App. D to free some space and left only the most relevant Issues in the main paper. We use this space to provide an overview of the attack in Sec. 4.

Questions:

Could you also, perhaps, clarify how exactly was DP training performed? From my understanding, construction of privacy filters requires you to derive information from the private data: hence it is unclear to me how this was handled and accounted for in terms of the privacy budget?

We agree and do state that training the generator while satisfying DP but allowing unperturbed queries to the metrics breaks the end-to-end DP pipeline -- please see Sec. 5.2.1. We rephrased our statements to make this point more clear in the Abstract and Sec. 1. Our motivation for combining DP model training and direct/unperturbed metrics access is to emulate the product offerings of some companies in practice. We also made this point more clear in Sec. 5.2.1 and App. 1.

Also: it seemed to me that all of your algorithms except for CT-GAN used DP already, why a separate section?

In Sec. 5.1, we attack the DP generative models while keeping $\epsilon=\infty$. We added a clarification in Table 1. In Sec. 5.2.1, we experiment with different epsilon values, namely 1 and 0.1. We keep our experiments with DP and low-utility generative models in a separate subsection because both of them produce synthetic data with reduced utility.

Additionally: I would like you to present the SearchAttack in more detail: it is unclear what ‘history of records from the first pass’ is.

We provided more details for both $SampleAttack$ and $SearchAttack$ in Sec. 4 and App. F. In particular, we clarified the steps of $SearchAttack$ in Algorithm 1 in App. F. The history is an internal object of the adversary, where they keep track of all the records they fed into the metrics (as illustrated in steps 16, 27, and 35). This way, the adversary can check what records they have already sent to the metrics API and greatly reduce the overall number of calls.

References:

[5] NIST, The Unlinkable Data Challenge, 2018

We thank the reviewer for their time and comments. We made several changes (summarized in the common message above). Here, we address individual comments.

Weaknesses:

These queries provide a huge amount of information: the distance to real data points (given by DCR and NNDR) and the amount of synthetic data points that match the real ones (given by IMS).

My impression over the main take-away of the paper is that revealing the privacy metrics is dangerous.

It is not surprising that one could successfully reconstruct outlier data points with arbitrary access to that information.

This is indeed the main contribution of our paper – through our analysis, counter-examples, and a new privacy attack, we formally show that relying on IMS, DCR, and NNDR to demonstrate/guarantee privacy leaks privacy. This is an inadequate approach and, as the reviewer pointed out, dangerous. Moreover, to the best of our knowledge, we are the first to rigorously study and scrutinize these metrics.

While it might not be surprising to (most) privacy experts, this approach and, in particular, these privacy metrics are adopted by all top companies in the space, as discussed in App. A. In fact, the privacy tests are used to guarantee privacy of cancer patients in a technical report by the EU (Hradec et al., 2022). Furthermore, we would also like to highlight that there are numerous research papers and whitepapers by companies like AWS that rely entirely on these/similar metrics to demonstrate the privacy of their models (we referenced several such studies in Sec. 1 and Sec. 2).

the contribution presents an attack that attempts to recover the original data points from the synthetic data generator.

We would like to highlight that we attack a single trained synthetic data generator in a black-box manner without any other auxiliary data, such as the training mechanism or representable training data. Whereas, previous studies on synthetic data (Stadler et al., 2022, Annamalai et al., 2023) require many such instances and access to the training mechanism and representable data.

The attack heavily relies on the ability to query privacy metrics an arbitrary amount of times.

This is a common assumption in privacy attacks vs synthetic data (Stadler et al., 2022, Annamalai et al., 2023), where the adversary can train an arbitrary amount of models. Other papers on generative models (Hilprecht et al., 2019) require sampling 1,000,000 times from the train and test data, while papers on DP auditing [1] require training 100,000 models on a fixed dataset. Finally, unlimited querying to a model/dataset is, for better or worse, common in production settings -- like for the Diffix system (Pyrgelis et al., 2018; Gadotti et al., 2019; Cohen & Nissim, 2020a), as discussed in Sec. 6.

it success does not rely on the sensitive information released by synthetic data, which is only used marginally.

To address this specific issue, we designed $SampleAttack$ to rely only on synthetic data samples generated by the generative model, i.e., it cannot search for nearby data records. In this sense, the synthetic data quality is central to the success of the attack.

it does not provide a compelling argument against the release of synthetic data itself when its IMS, DCR and NNDR scores are not revealed.

First, to remove any confusion, we rephrased the introduction of the attack to mention that it is specifically designed to expose the weaknesses of the metrics (IMS, DCR and NNDR) -- please see Sec. 1.

Second, for many providers, similarity-based metrics are the only way they demonstrate/guarantee the privacy of the product to their end users, which makes access to the metrics crucial. We clarified this in App. A. As confirmed by our direct experience with these companies (details had to be omitted to preserve double-blind submission), in commercial settings, restricting access to these metrics would severely limit the desirability of these products.

To provide a practical example, consider the following scenario: a company holds some sensitive data that needs to be shared internally to another team in a private way. The data owner team trains the generative model on the synthetic data platform and gives access to the other team. An adversary that is part of this team could then generate data using the platform. Since every generated synthetic dataset needs to be private, and privacy is guaranteed through the metrics, the metrics need to accompany every generated dataset. The adversary can then run our attack.

Dear authors,

I thank you for your detailed responses. I comment on them below.

1- Attacks that rely on an arbitrary number of queries: I do not agree with the authors that existent attacks allow the same kind of queries to sensitive data than this submission:

1a- It is not true that the attacks proposed in (Stadler et al., 2022, Annamalai et al., 2023) are able to arbitrarily query sensitive datasets. What they are able to do is to train an attacker form a reference dataset or partial non-sensitive data, but they have limited access the sensitive synthetic datasets. I find this substantially different than your attack from a security point of view.

1b- In [1], the purpose of querying the sensitive dataset many times is done to provide statistically significant estimations of privacy parameters and not to incrementally strengthen the attack as in your case. Therefore the fact that "100,000" models are trained is different and not comparable to your setting.

1c- Indeed I agree that attacks to the Diffix system that you mention are allowed to arbitrarily query the sensitive information. However, these attacks are realistic because the Diffix system allows any user to do these kind of queries to sensitive data. Therefore, demonstrating that it is not private using the same interface of any user is more relevant. In your contribution, you are attacking a data+metrics generator that, in practice, does not accept arbitrary queries over the sensitive data with your own (manipulated) synthetic dataset. Therefore this does not seem realistic to me.

In addition to the above points, these papers that the authors referenced in their rebuttal have clearly defined the attacker model, distinguishing games and reconstruction algorithms. Contrary to that, your paper presents its main contribution in the appendix and in a confusing way (see my point below).

2- The success of the attack does not rely on the sensitive information released by the synthetic data: Indeed the loose description of $SampleAttack$ in Section 4 explains that the algorithm can reconstruct information without manipulating the input data points of the metrics. However, the (still loose) explanation of $SampleAttack$ in Appendix F remarks that "by manipulating or augmenting the input synthetic data, we can precisely determine the distance between a target synthetic record and the nearest train data counterpart.". Therefore this gives me the impresion that manipulation still occurs and I am not convinced that this is realistic in the current setting. In addition, $SampleAttack$ does not provide the same reconstruction accuracy as the main claims of the paper, which are obtained with $SearchAttack$.

3- Revealing the metrics is "the only way they demonstrate/guarantee the privacy of the product to their end users". I disagree with the authors in this point. Revealing privacy metrics is by no means a proof that these metrics have been computed correctly. An adversary can generate unsafe synthetic datasets and publish them along with fake acceptable metrics. Auditing such behavior is equally difficult regardless of the disclosure or lack of disclosure of the metrics.

Given the points above, my score is likely to remain unchanged.

Refs.

[1] Tramer et al, Debugging Differential Privacy: A Case Study for Privacy Auditing, arXiv:2202.12219, 2022

We are thankful to the reviewer for engaging with the discussion process and for providing us with further feedback. We provide further clarification below.

1- Attacks that rely on an arbitrary number of queries In your contribution, you are attacking a data+metrics generator that, in practice, does not accept arbitrary queries over the sensitive data with your own (manipulated) synthetic dataset. Therefore this does not seem realistic to me.

We appreciate the reviewer's concern about the realism of attacks relying on arbitrary queries. As clarified in our Ethics Statement, we explicitly state that we are not directly attacking deployed systems but rather a simulated one. Instead, our main contribution is to formally show that relying on IMS, DCR, and NNDR (which are the most commonly used privacy metrics in industry and adopted by numerous research papers) to demonstrate/guarantee privacy is not safe and actually leaks privacy. We do so through our analysis, counter-examples, and a novel proof of concept reconstruction attack.

The core of our argument, detailed in Sec. 1, Sec. 2, and Sec. 4, challenges and disproves the prevailing statement that passing these three privacy tests equates to creating “truly anonymous synthetic data” (Platzer & Reutterer, 2021; Mobey Forum, 2022). Indeed, the goal of the adversary is to “build a collection of synthetic datasets considered private by the provider” which could be used to reconstruct the train outliers. Theoretically, how the adversary builds this collection of synthetic datasets should not be of great importance as long as the individual datasets are deemed safe by the tests. Additionally, the tests, as presented and used in practice, are completely agnostic to the adversary behavior (the do not even provide an adversary) and do not limit the number of queries made to them (infinite amount of synthetic data can be generated). They only take into account the distances between real/test/synthetic datasets (we explain this in Sec. 3 and App. D).

From all potential strategies that could be employed to construct such a collection of datasets, we present one through our attack, $ReconSyn$. The adversary relies on key 3 assumptions, which are all clearly stated in the main paper in Sec. 4. It just so happens that there are companies that not only make our assumptions realistic in practice but also advertise them widely (in short, unlimited data generation, data augmentation, metrics evaluation per every dataset -- we urge the reviewer to carefully go through our citations in Plausibility of the Attack. in Sec. 4).

To reinforce the point that our attack is not a general reconstruction attack but one designed to specifically demonstrate the unreliability of the 3 privacy metrics, me introduce our attack as a proof of concept attack in Sec. 1.

We thank the reviewer for their time and helpful comments and suggestions. We made several changes (summarized in the common message above). Here, we address individual comments.

Weaknesses:

A thorough description of the attack is lacking in section 4.. a paragraph explain the logic of the attack and where the information is being extracted would significantly improve the paper.

We added an extended description of the attack in Sec. 4 and provided more details in App. F. Furthermore, we updated Algorithm 1 to make it cleaner/easier to follow.

Figure 2 should be presented in a way where it is possible to distinguish between the different training algorithms and datasets.

We tried to improve the presentation of Fig. 2 (now Fig. 3). Basically, the top 5 lines are from Adult Small, the bottom 5 from Adult, while the middle 5 are from Census. We also reduced the space allocated to Fig. 4 (now Fig. 5).

I do not entirely understand what the takeaway is from Figure 3.

The main takeaway is that all models generate MNIST digits that are further away from the train data compared to the distance between test data and train data (min distance is 6). This is the main reason $SampleAttack$ performs so poorly (0% for all models). We explain this in Sec. 5.1.1.

'outliers' is never clearly defined

We added more details about how we define outliers for every dataset in App. C.2. While there are various definitions of outliers (Carlini et al., 2019a; Meeus et al., 2023), we opt for a simple and intuitive selection of roughly 10% of the train data as outliers, aiming to cover various scenarios. We also explain better how the adversary fits the $OutlierDetector$ and decides on the outliers regions in App. F.

Any model regarded as formally satisfying DP would never be able to look directly at the private data in this way.

We agree and do state that training the generator while satisfying DP but allowing unperturbed queries to the metrics breaks the end-to-end DP pipeline -- please see Sec. 5.2.1. We rephrased our statements to make this point more clear in the Abstract and Sec. 1. Our motivation for combining DP model training and direct/unperturbed metrics access is to emulate the product offerings of some companies in practice. We also made this point more clear in Sec. 5.2.1 and App. 1.

these results could be better presented to really hammer the point to ensure the key message of this paper reaches the synthetic data community.

We introduced Fig. 1, which hopefully manages to demonstrate the success of our attack as well as the weakness of the privacy metrics.

Questions:

Can you report the privacy metrics with DP or would your recommendation be to not report distance metrics?

We are not sure this will scale as querying the metrics in a DP way would eventually deplete the DP budget. This means that no more synthetic datasets would be able to be generated, which contradicts one of the main selling points of synthetic data providers – unlimited querying of the model (generation of new samples of synthetic data).

We thank the reviewer for the detailed and helpful comments and suggestions. We made several changes (summarized in the common message above). Here, we address individual comments.

Weaknesses:

Paper Structure/Understanding $ReconSyn$

The attack needs to be described in the main paper.

In the revised paper, we add an overview of the main algorithmic steps describing how the attack works in the main paper in Sec. 4.

The algorithm needs to be described more formally.

We added more details of the algorithmic steps and clarified Algorithm 1 in App. F.

How practical is the attack?

Assuming the adversary can query any dataset with the metric seems far-fetched.

First, we would like to clarify that generating unlimited synthetic data from a trained generator is essentially a universal selling point of synthetic data providers. Second, for many providers, similarity-based metrics are the only way they demonstrate/guarantee the privacy of the product to their end users, which makes access to the metrics crucial. We clarified this in App. A. As confirmed by our direct experience with these companies (details had to be omitted to preserve double-blind submission), in commercial settings, restricting access to these metrics would severely limit the desirability of these products.

We would also like to highlight that there are numerous research papers and whitepapers by companies like AWS that rely entirely on these/similar metrics to demonstrate the privacy of their models (we reference several such studies in Sec. 1 and Sec. 2). Finally, unlimited querying to a model/dataset is, for better or worse, common in production settings -- like for the Diffix system (Pyrgelis et al., 2018; Gadotti et al., 2019; Cohen & Nissim, 2020a), as discussed in Sec. 6.

However it was not clear how the attack could know the reconstruction rate of the previous component without access to the training data.

We now added more details in Sec. 4 and App. F. As discussed in Example 2 in App. E and explained in App. F, we can use $SampleAttack$ to trick the metrics to output the exact distance of a given synthetic record to its closest train record. Thus, we can detect exact matches in the first phase of the attack through the metrics without having access to the train data.

It would be helpful to list the number of queries to the metric oracles/the effect that a rate-limiting defence would have on attack success.

The number of queries to the metrics for $SampleAttack$ are provided in Sec. 5.1.1; for Small Adult, Adult, and Census, we plot them in Fig. 3. Namely, $SampleAttack$ makes between 1,000 and 5,000 rounds (or calls to the metrics) depending on the dataset. One round involves generating a synthetic dataset and making one call to the metrics API. For comparison, previous papers on generative models (Hilprecht et al., 2019) require sampling 1,000,000 times from the train and test data, while papers on DP auditing [1] require training 100,000 models on a fixed dataset.

Also, as mentioned above, limiting the rates would contradict one of the main advertised reasons for adopting synthetic data – unlimited samples of “private” synthetic data, where privacy is guaranteed through the metrics.

While the attack is useful for a proof of concept, it doesn't have any merit in the case that the privacy metrics are not leaked.

We rephrased the introduction of the attack to mention that it is a proof of concept attack designed to specifically expose the weaknesses of the metrics in Sec. 1.

DP argument

It can not be DP while allowing unperturbed queries about the training dataset (the metrics).

We agree and do state that training the generator while satisfying DP but allowing unperturbed queries to the metrics breaks the end-to-end DP pipeline -- please see Sec. 5.2.1. We rephrased our statements to make this point more clear in the Abstract and Sec. 1. Our motivation for combining DP model training and direct/unperturbed metrics access is to emulate the product offerings of some companies in practice. We also made this point more clear in Sec. 5.2.1 and App. 1.

Perhaps more interesting would be to show what happens if the metrics are released with DP (an actual defence).

We are not sure this will scale as querying the metrics in a DP way would eventually deplete the DP budget. This means that no more synthetic datasets would be able to be generated, which, as mentioned, contradicts one of the main selling points of synthetic data providers.

Best defence would be removing the metrics entirely.

In principle, we agree. Indeed, the best defense would be to train the model in a DP way and not accompany data releases with metrics. However, as mentioned earlier, for many companies (and research papers), these metrics are the only way to demonstrate/guarantee privacy to customers and users and that is why in practice they are released in the first place.

We thank the reviewer for the encouraging and thoughtful comments. We made several changes (summarized in the common message above). Here, we address individual comments.

Weaknesses:

Why do the authors focus on outliers only? Intuitively, an average record is more likely to be generated by the synthetic data model than an outlier record.

We agree that the average record is more likely to be generated and thus probably easier to reconstruct. To confirm this hypothesis, we run new experiments, which we discuss in App. G. In short, reconstructing any train records is indeed much easier.

However, in the main body of the paper, we focus on outliers because they likely correspond to the most vulnerable individuals, they are more challenging to attack (which puts our attack to the test), are more susceptible to memorization, and are specifically highlighted by regulators (we also discuss this in Sec. 4). Therefore, if we manage to reconstruct them successfully, this will constitute a clear and serious privacy violation.

The attack results are contingent on the definition of outliers. Both the targets of the attack and the test records are constructed using similar clustering methods. This may lead to over-optimistic results.

We add more details about how we define outliers for every dataset in App C.2 (including new references to (Carlini et al., 2019a; Meeus et al., 2023)). While the adversary follows the same steps as the provider to determine the outliers regions, we would like to clarify two points: 1) the targets of the attack are the outliers from the train data, not the test data; 2) there is no leakage from the provider to the adversary, i.e., the adversary fits $OutlierDetector$ on their own sample of synthetic data (using the fitted generative model) without having access to any of the train/test data. Therefore, if the adversary does not do a good job with $OutlierDetector$, they will reduce the attack’s performance. All these, also combined with our experiments in Sec. 5.2.2 and App. G (in which the adversary reconstructs large proportions of any train data), lead us to believe that our results could actually serve as a lower bound on the number of records that could potentially be reconstructed.

It’s unclear which of the similarity-based metrics is used in the empirical evaluation.

The adversary in Sec. 5 has access to the 3 privacy metrics (IMS, DCR, NNDR). In the revised paper, we highlight this in Sec. 2 and Algorithm 1 in App. F. We do so to emulate the real-world product offerings of some companies.

Missing method description in the main paper and insufficient method description in the Appendix. In the Appendix, to ensure reproducibility, the authors should precisely describe steps 18-32 of Alg. 1.

In the revised paper, we provide a description of the two phases of the attack in the main paper in Sec. 4. Furthermore, we add more details of the algorithmic steps and clarified Algorithm 1 in App. F.

Can the authors describe (add a paragraph on) how their reconstruction method relates to Dick et al.?

To initiate their successful attack, Dick et al. (2023) need access to the publicly known data distribution and true answers to a number of queries. They use this information to generate multiple synthetic datasets using a RAP variant (Aydore et al., 2021), ranking them based on the number of duplicated rows. In contrast, our attack does not require such any information, except for the privacy metrics. Additionally, our method has a black-box access to a single generative model which does not depend on preserving the actual statistics of the data (which is often the case for the models we evaluate).

Unfinished sentence on page 3

We fix the sentence.

Questions:

Is it possible, using the authors' method, to assign a confidence or likelihood to each reconstructed record?

Since the metrics are deterministic and unperturbed (as discussed in Sec. 3), the adversary can be 100% confident for each reconstructed record. We tried to allude to that in the take-aways in Sec. 4.

What do the authors mean by “all three tests pass” (relating to the metrics)?

Every metric is associated with a statistical test. The passing criteria are either the average or 5th percentile comparison between ($D_{train}, D_{test}$) and ($D_{train}, D_{synth}$). We made this more clear in Sec. 2.