Advertisement personalized to a user's browsing behavior is a fixture of the modern internet. The ability to target ads based on a user's latent interests has many benefits for the ecosystem, as personalized ads are often more relevant to the user, obtain better performance for the advertiser, and achieve higher revenue for the publishers. All these benefits, which fund the free web, however, come with a privacy cost. Traditionally, to sustain personalized advertisements, many adtechs have extensively used third-party cookies to amass large and detailed profiles of users' browsing activities [15]. As the extensive reliance on third-party cookies incurs privacy risks, many browser vendors have recently proposed a variety of Privacy-Preserving Ads (PPA) APIs to enable personalized ads without the use of third-party cookies. These PPA APIs include, for instance, the Chrome Privacy Sandbox's APIs [20], Microsoft Edge's Private Ad Selection API [28] and Apple's AdAttributionKit [4]. The main goal of all these initiatives is to significantly reduce the privacy risk of advertisement compared to methods using thirdparty cookies.
Given the widespread deployment on the web of such PPA APIs, academics, browser vendors, and regulators alike have all shown interest in analyzing the privacy properties of such methods [1,2,8,9,16,17,22,31,34]. Unfortunately, however, the empirical study of these proposed methods by academic researchers is hindered by the lack of publicly available data on the output of such APIs.
Researchers not affiliated with the internet industry, for obvious reasons including privacy, do not have easy access to high-quality real browsing data from a large number of users. For this reason prior work from academic researchers has often relied on small scale data (few thousands of users) or on fully synthetic data (not based on real browsing histories) [1,2,8,22]. Using data that does not match real browsing histories of a representative large population can skew privacy analysis arbitrarily and in unpredictable ways. Moreover, the accurate replication of prior work from industry researchers with access to large-scale real data [9,17] is not feasible on a small-scale dataset. This hinders the ability to credibly verify (or disprove) the claims of browsing vendors.
To address this problem, in this work, we design a methodology to release a privacy-preserving large-scale dataset of PPA APIs output traces. We focus on one API, Chrome's Privacy Sandbox Topics API [21] which has been extensively studied in the past in terms of its re-identification risk [1,2,8,9,17,22,34]. Our methodology, and the dataset we release, has the aim of allowing any researcher to study the re-identification risk of the API and to replicate prior work. Our data release (and links to the supporting code) are made available through kaggle [11].
The main technical contribution of our work is a methodology to construct synthetic API outputs that mimic the real API traces while providing strong provable privacy guarantees. To ensure privacy, we use the gold-standard provable privacy protection of Differential Privacy (DP), mitigating the risk that our release leaks information about individual users. Thanks to DP, our methodology allows us to safely provide, for the first time, a release based on the real browsing data of hundreds of millions of users (as opposed to prior work with thousands of users [8,22]).
In terms of accuracy we show that our methodology generates traces that have similar re-identification risk to the real data, thus facilitating external researchers in verifying the claims in prior work and in studying the Topics API in depth. We believe that large scale data releases like ours will further deepen the understanding of the research community on the properties of Privacy Preserving Ads technologies.
Our methodology to obtain a privacy-preserving data release is based on four steps.
Statistics extraction. The first step analyzes the Topics API data of a large number of users-see Section 3 for details on how the API works. From this data, we define a large number of statistics describing real users' topic traces and their evolution over time. The statistics include the point-wise distribution of the topics in output and their pairwise co-occurrence within (and across) periods of time. Crucially, we obtain these aggregate statistics with strong privacy protection using differential privacy-see Section 4 for details on how the statistics are obtained. The rest of the data release methodology uses as input exclusively these anonymous, highly aggregated, differentially private statistics, thus bounding the privacy risk of all downstream modeling steps.
Model optimization. Next, we design a parameterized model describing a distribution over sequences of Topics API data. The parameters of the model are optimized with stochastic gradient descent methods to reduce the discrepancy between the statistics induced by the model on the data and the statistics obtained in the previous step-see Section 5 for how the model is defined and trained. This model is, by the post-processing properties of differential privacy, itself differentially private.
Data sampling from the model. Finally, we use the prior obtained DP model to create the synthetic Topics API data by drawing i.i.d. samples from its distribution (see Algorithm 2).
Notice that both the model and data sampled from it are derived solely by post-processing the DP statistics obtained in the first step. Hence, we can publish the statistics, the parameters of the model, and the data sampled while satisfying differential privacy.
Verification of the data accuracy. After we generate the data, we verify its quality by empirically comparing its properties with the original data. First, we verify that the synthesized data very closely matches the statistics observed in the real data.
Then, we follow the methodology of prior work [9] and empirically verify that the synthetic data has good agreement with the re-identification rate of the real data (see section 6). This allows us to replicate prior work with good accuracy.
Understanding the effect of different web technologies on user privacy has been a major focus of the privacy and security community for decades. In this area of work, the privacy risks involved in the use of third-party cookies are well-understood [27].
Another well-established area of research is the measurement and mitigation of the so-called browser fingerprinting risk [5,14,19,25,29], i.e., the potential for tracking users based on information provided in HTTP request headers or extracted from other web APIs (e.g., user agent, screen size, fonts, etc.).
As web browsers have reduced access to third-party cookies while increasingly deploying [23] a variety of Privacy Preserving Ads APIs, the privacy community has devoted significant attention to understanding the privacy implications of these APIs. Some research in this space has focused on bounding the theoretical worst-case privacy risk properties of APIs, for instance through the lens of differential privacy, as in the case of the Attribution Reporting API [18].
Another research direction, which is the focus of this work, has been understanding the impact of these APIs in the wild by empirically analyzing real browsing data. In this body of work, the most relevant research to our paper is the study of the reidentification risks of the Topics API [1,2,8,9,17,22,34]. These papers have focused on assessing the likelihood of an attacker correctly matching the identity of a user across two sites based on the Topics API outputs observed on both sites [9]. Results in these analyses have varied widely (even using similar methodology) due to the vastly different underlying datasets used to measure the risk.
For instance, consider the size of the data, which is known to affect the re-identification risk [9], as re-identifying a user is simpler among fewer other users. While some industry researchers [9,17] could perform their analysis on proprietary datasets containing hundreds of millions of real users from different countries, several academic studies have instead been based on datasets with around 100-2000 users [8,22]. The work of [8], for instance, uses data from about 2000 volunteers in Germany. Other work used imputed API outputs from data collected long before the introduction of the PPA APIs (e.g., AOL logs from 2006 [2]) or pure theoretical analysis [1]. This is expected, as academic researchers unfortunately do not have easy access to good-quality, large-scale browsing data.
Unsurprisingly, the use of datasets with different scales, creation methodologies, and potential biases has resulted in widely different estimates of re-id risk, sometimes disagreeing by orders of magnitude.
The goal of our work is to publish an open-source dataset that is based on the real, large-scale proprietary data usually available only to tech companies, thus enabling the replication of prior work by all researchers. This dataset will also allow for comparing different study methodologies on the same data.
Finally, a related area of research is that of DP Machine Learning, and especially synthetic data generation with DP (we refer to a research survey for more details [30]). A large body of work in this area has focused on designing general-purpose DP models for generating text data [33], images [26], and tabular data [32], for instance. Our work is in the line of research of synthetic data generation with DP using marginal-based methods [6]. Our paper specifically designs a custom synthetic data model for the Topics API, based on the unique properties of the API discussed in the next section, and that requires only aggregated access to statistical information on the private data.
3 The Topics API Algorithm 1 Topics API. Input: Topics O, probability to return a random topic .
On device (at the end week ): Select the set of top 5 most frequent topics in the on-device websites visited by the user, and that have called the API, during the week . If fewer than 5 topics are present, pad with uniformly at random (u.a.r.) topics from O. On call GetTopic() from website , during week , for user : Seed the random number generator with , , . Flip coin with heads probability . if Heads then return Element of O chosen u.a.r. else return Element of -1 chosen u.a.r. end if
As our work focuses on studying in depth the privacy properties of the Topics API [21] part of Google Chrome's Privacy Sandbox [20], we first describe how the API works. (We refer to [21] for detailed specifications of the API.) The purpose of the Topics API is to enable interest-based advertising without the use of third-party cookies in order to reduce the risk of cross-site tracking. To do so, the API introduces several privacy protections including limiting the interest analyzed to a coarse-grained curated list of interests and introducing noise.
The API has two main processes (See Algorithm 1). First, when a client visits a website that calls the API, that website is classified (on-device) into a taxonomy O of topics, where |O| = 469 in the v2 taxonomy 1 . This allows the API to build a weekly on-device interest profile of the user. This computation is done at the end of week , when the browser builds an interest profile for the user that will be used the next week. This profile contains the top five topics (from the taxonomy) of the websites visited by the user during the week that have called the API. is guaranteed to be of size 5 by padding it, if necessary, with random topics from O whenever there are fewer than 5 topics visited during a week. Importantly, this profile is kept on the browser and not shared with others, and is kept fixed until the update at the end of the subsequent week. Then, during week , whenever a website calls the API, the browser selects a topic at random from the top topics in the profile -1 of the user obtained in the previous week. This correct topic is released with probability 1 -, while a uniformly at random topic among all O topics is selected with probability ( = 5% in the current specifications). Notice that, for every user-website pair, the topic sampled for that website for the user is fixed the entire week (i.e., two visits of the user to the website will result in the same topic). Samples from the same user (within a week) on two sites are instead drawn independently. After the week is complete, the profile is updated again as described above. 2
Our goal is to develop a model of the Topics API output observed by an adtech (or third party present on a site such as adtechs) for a set of users, over a period of time. Consider the observation of the output of the API for user on website , for weeks. We will number those weeks without loss of generality 1, 2, . . . , . We call ( , ) = ( 1 ( , ), . . . , ( , )) the trace of the output of the API for user on website for the weeks 1 to , (i.e., ( , ) is the output for week for the user). Notice that by the property of the API there is a fixed ( , ) observed by the site (and all third-party present on the site) during week for the user even if the user visits the site multiple times. When clear from context we will omit , and call = ( 1 , . . . , ) the trace of the user. Notice that describes completely the Topic API outputs observed by the website for the user during the period of time. Our goal is to learn a privacy-preserving model of the distribution ( ) over traces so that we can sample ( , ) ∼ ( ) for users ∈ U. Notice, in fact, that for any set of sites , the traces ( , ), for ∈ , are all sampled i.i.d. from the distribution ( ). So we will focus the rest of the discussion on how to model ( ).
From the definition of the API, the distribution ( ) is entirely described by the sequence ( ) = ( 0 ( ), . . . , -1 ( )) of the 5 top topics of the user for the weeks 0 to -1. In fact, we have
So it is sufficient for us to only model the distribution of ( ) = ( 1 ( ), . . . , ( )), for a given user, in order to model the output of the API on arbitrary many sites. This will be the focus of all the modeling efforts of the paper.
Unfortunately, exactly modeling this distribution ( ) is infeasible for even small , and even neglecting the privacy constraints. This is because the support of this distribution is the set of all sequences of length of 5 topics out of |O| = 469 topics. This scales with |O| 5 which is too large to measure accurately, or just output, for even very small (for instance for = 1 it contains more than 100 billion parameters!) . Since our goal is to model the long term evolution of the traces of a user for several weeks we need to accept a less general model.
For this reason, our approach is to impose a series of simplifying assumptions on the distribution that we can model allowing a computationally efficient and privacy-preserving model design. As we will see next, our approach will be to impose that the distribution of the data we can generate must approximately match, across a large number of statistics, the same statistics of the real distribution. Our ML model will learn a set of parameters to maximize the match over those statistics. The choices of the statistics, described in the next section, is inspired by identifying a small set of the salient parameters that fully characterize the evolution of the top topics of a user under assumptions of time-stationarity of the trace evolution.
We now define and justify the statistics we measure from real user data and that we use to fit a parametric distribution. As we discussed above, we model the top user topic sets 0 , . . . , -1 in weeks 0, . . . , -1 as these uniquely determine the distribution over topic traces that would be observed by any website for that user in weeks 1, . . . , . In our model, we define the following statistics:
where is a randomly chosen user and is a randomly chosen week in {0, . . . , -1}. There are 469 such statistics.
where is a randomly chosen user and is a randomly chosen week in {0, . . . , -1}. There are 469 2 = 109, 746 such statistics. • For each pair of (possibly equal) topics
where is a randomly chosen user and is a randomly chosen week in {1, . . . , -1}. There are 469 2 = 219, 961 such statistics.
Roughly speaking, * single and * within measure the popularity of topics and pairs of topics, while * across measures how topics change over time. Also, notice that, since the sets ( ) are guaranteed to have topics, we can derive * single from * within :
Note that all three kinds of statistics are averaged over the training data weeks and are imposed on the model for all weeks simulated. This constitutes a stationarity assumption: the topic popularity and transition dynamics do not significantly change over the data weeks. In particular, when generating data for ′ weeks, we enforce the popularity statistics * single and within * on every week, and the transition statistics * across on every pair of consecutive weeks. The main advantage is that this allows us to generate synthetic topics data for many weeks without the need to obtain a collection of statistics that grows with the number of weeks. This is computationally efficient and enables better statistical accuracy at parity of privacy guarantee as it reduces the number of parameters that must be estimated privately.
Summary. The simplifying assumptions described in this section greatly decrease the parameters needed to describe the distribution of the Topics API traces. The key enabling this simplification is a stationarity assumption postulating that the probability distribution of topics and their transition probabilities are stable over time. We test this assumption in Appendix C where we show that all the statistics we compute on our training data have ≥ 99.8% correlation coefficient with the same statistics computed on a different period of time from the validation data, confirming that the stationarity assumption holds with high accuracy.
While an arbitrary trace distribution over weeks would require
parameters to describe, thanks to this simplifying assumption our model require estimating only |O| 2 + |O| 2 ≈ 329,000 statistics * within , * across for arbitrary long traces. The models we fit to these statistics (described in Section 5) have approximately 4.7M parameters. As we discuss in the next section, these statistics can be estimated efficiently and accurately in a privacy-preserving way. Moreover, as we observe in our empirical analysis (see Section 6) our modeling closely matches some important aspects of the real data behavior. Before describing in Section 5 how we learn a model to sample arbitrary long traces approximately matching the observed statistics we described how to estimate * within , * across in a privacy preserving way.
We now describe the data used to obtain the DP statistics. Our work is based on a Google proprietary log of de-identified Topics API outputs for Chrome's users. From this dataset we obtain for more than a hundred million users the top = 5 topics assigned to the user for a period of time. More precisely, we based our analysis on the latest 4 weeks of data 3 to obtain the sequences ( ) = ( 0 ( ), 1 ( ), 2 ( ), 3 ( )) associated to a set of users ∈ U of users for = 4 weeks. The statistics used to build the model are based on analyzing a dataset containing the first two weeks of data = ( 0 ( ), 1 ( )) ∈U while the full 4 weeks are used in the re-identification risk measurement (see Section 6).
Differentially privacy. We briefly introduce the framework of Differential Privacy which enables us to provide strong privacy protections for the statistics computed on this data.
Differential privacy (DP) [13] (refer to [12] for an in-depth treatment of the area) has emerged as the gold standard for ensuring strong privacy protection, when dealing with private data. Intuitively, differential privacy promises that the output of an algorithm remains approximately the same (in distribution), whether or not a particular individual users' data is included in the input of the algorithm. This guarantee provably limits the ability of an adversary to accurately infer any sensitive information about a specific individual (including even whether the user is present in the data or not). More formally, our differential privacy protection can be stated in the following way. To achieve DP for the statistics computed we use the well-known Gaussian mechanism. Suppose the statistics computed by the algorithm are represented as a vector-valued function : D → R where is the number of statistics computed. The sensitivity of this function is defined as Definition 4.3 (ℓ 2 sensitivity). The ℓ 2 sensitivity Δ 2 ) of the function is defined as the maximum of adjacent datasets , ′ ∈ D
Proposition 4.4 (Gaussian Mechanism [7]). Let : D → R be a function with ℓ 2 sensitivity Δ 2 ( ). For any > 0 and ∈ (0, 1], the mechanism
where Φ : R → R be the standard Gaussian cumulative density function, and is the identity matrix of size .
Proposition 4.4 allows setting a parameter depending on the sensitivity and desired ( , )-DP guarantees for the Gaussian noise to be added to the statistics.
For our statistics computation we used a dataset containing the first two weeks of data, over which we define the following three functions:
(1) 11 ( ) [ , ], for , ∈ O 2 , is the number of users with both topic and in the first week;
(2) 22 ( ) [ , ] is the number of users with both topics in week two; (3) 12 ( ) [ , ], for , ∈ O 2 , is the number of users with topic in week 1 and topic in week 2.
It is easy to prove the following result:
Lemma 4.5. The ℓ 2 sensitivity of the functions defined above is
The proof is available in the appendix.
Implementation details. . In our data release we computed the statistics defined in the vector above using a Google DP pipeline implementing the Gaussian mechanism [3] We used a total privacy budget of = log(3), = 10 -15 in line with strict privacy protection standards. Internally the count vectors in 11 and 22 received 25% of this budget while the counts 22 received 50%. Notice that from simple post-processing of the DP counts thus obtained (by normalization) we can obtain the the statistics * single , * within , * across . Specifically, we estimate * within averaging (and normalizing) the count vectors 11 , 22 while * across comes from normalizing the counts 12 (and * single is induced by * within as described above).
Description of the statistics obtained. We now briefly describe the DP statistics * single , * within , * within obtained. The full DP statistics tables are provided as part of our data release. Due to space limitations, we only present some basic statistics. In Figure 1, we visualize the top topics for the * single . In Appendix B we provide the top entries in * within and * across . It is possible to observe that /News, /Arts & Entertainment, and /Shopping are the top topics observed. For the top pairs of topics in the * within and * across we observe that the distribution comes mostly from those same top topics. More details are provided in Appendix B. Name Rate /News 34.60% /Arts & Entertainment 24.52% /Shopping 23.34% /Sports 18.31% /Games/Computer & Video Games 17.70% /Internet & Telecom 12.97% /Computers & Electronics/Software 11.82% /Computers & Electronics 10.46% /Food & Drink/Cooking & Recipes 9.72% /Arts & Entertainment/TV & Video 8.02% Figure 1: Top topics distribution as represented by the top DP statistics in * single .
In this section, we design a model for sequences of top topic sets that is consistent with the statistics collected in Section 4. Our strategy is inspired by the Relaxed Adaptive Projection mechanism for private synthetic data, proposed by Aydore et al. [6], and the dataset reconstruction attack methodology of Dick et al. [10]. The high level idea is as follows: we design a parameterized distribution over topic set sequences such that all of the statistics from Section 4 are differentiable functions of the model parameters. Then we use gradient-based optimization techniques to search for distribution parameters such that the statistics for the parameterized distribution closely match those privately collected from real user topic set sequences. Given the fit distribution, we generate synthetic topic set sequences by sampling users i.i.d. from it. Due to the post-processing guarantees of Differential Privacy, the fit distribution and sampled synthetic user topic traces can be released while satisfying differential privacy. We begin by describing the parametric form of our topic set sequence distribution. The most basic component is a slot, which is a distribution over a single topic. Each slot's topic distribution is parameterized by one weight/logit for each topic, which is converted to a topic distribution by the softmax function. In other words, each slot is a distribution over topics encoded by a logit vector. Next, a type represents a simple distribution over topic set sequences. If is the number of weeks and is the number of top topics per week (generally = 5), then each type contains slots. The first slots correspond to the topics in the first week, the next slots correspond to the second week, and so on. To sample a topic set sequence from a single type, we sample topics for each slot independently and take the topic set for each week to be the set of unique topics among that week's slots. Note that it is possible for this sampling procedure to produce topic sets that are smaller than . As in the real Topic API algorithm, when measuring the re-identification risk, any user topic sets that are smaller than size are padded with random topics. Finally, our modeled distribution over topic set sequences is a uniform mixture of many types. To sample a topic set sequence from the mixture, we pick a type uniformly at random and sample a topic set sequence from that type. Figure 2 depicts a schematic representation of the model.
Formally, the distribution is parameterized by ∈ R × × × |O| , where is the number of types, is the number of weeks, is the number of topics per week, and |O| is the number of topics in the topic taxonomy. The vector [ , , , :] = ⟨ , , ,1 , . . . , , , ,|O| ⟩ contains the logits for slot of week in type . For simplicity, we assume that the topic ids are the consecutive integers 1 through |O|. Pseudocode for sampling a topic set sequence is given in Algorithm 2.
The model described above has a number of desirable properties. First, when the number of types is sufficiently large, this model can fit any statistics computed from a sample of user topic traces. This is because we can create one type for each user that produces that user's topic trace with probability one. Then the distribution encoded by the model is exactly the empirical distribution of the sample and statistics computed from the model perfectly match those of the data sample. However, in most cases we do not need one type per user, and each type should be thought of as a distribution Algorithm 2 Topic Set Sequence Sampling Input: Distribution parameters ∈ R × × × |O| . (1) Choose type uniformly at random from [ ]. (2) Let , = so max( [ , , , :]) for each ∈ [ ], ∈ [ ] be the topic probability vector for slot in week . (3) Sample a topic , ∈ O from the probability vector , for each ∈ [ ], ∈ [ ]. (4) Let = { ,1 , . . . , , } be the set of unique topics sampled from the slots for each week ∈ [ ]. (5) Return the topic set sequence ( ) ∈ [ ] .
over topics that are typically observed together. For example, even though we use a dataset containing approximately 100 million users, we are able to achieve a very good fit using = 500 types. Second, even though the model is expressive enough to fit the statistics we collect, it is not obvious how to find the optimal parameters. As we will see in Section 5.1, each of the statistics from Section 4 can be written as a differentiable function of the model's parameters . We can therefore deploy the extensive machinery of gradient-based optimization to search for model parameters that closely agree with those statistics.
In this section we describe our approach to fitting the parameters of the topic set sequence model described in Section 5. We define a differentiable objective function of the model parameters such that achieving an objective value of 0 corresponds to perfectly matching the DP statistics computed in Section 4. Then, this objective function is optimized using Adam [24], which is an adaptive learning rate optimization algorithm originally designed for training deep neural networks. 0.004 0.002 0.000 0.002 0.004 Additive Error: (target modeled) 100 0 50000 100000 150000 200000 250000 300000 Count Histogram of Signed Errors (a) Signed Error 1.0 0.5 0.0 0.5 1.0 Relative error: (modeled target)/target 0 1000 2000 3000 4000 Count Histogram of Signed Relative Errors For Stats >= 0.1% (b) Signed Relative Error
Figure 4: Histograms of the absolute and relative errors over the terms of ( ). Notice that the x-axis in Figure 4a is clipped between [-0.005, 0.005] to increase clarity, see Figure 3a for the entire distribution.
Lemma 5.1. Let ( ) ∈ [ ] be a topic trace sampled from the model with parameters . There exist functions single , within , and across that are differentiable with respect to ∈ R × × × |O| such that (1) For every week ∈ [ ] and topic ∈ O, we have Pr( ∈ ) = single ( ; , ).
(2) For every week ∈ [ ] and distinct topics 1 , 2 ∈ O, we have
(3) For distinct weeks 1 , 2 ∈ [ ] and any topics 1 , 2 ∈ O, we have
The proof of Lemma 5.1 essentially uses the inclusion-exclusion principle to write each of the statistics as a polynomial function of . The detailed proof is given in Appendix A.
With this, we are ready to define the optimization problem we solve in order to fit the parameters to the collection of differentially private statistics obtained in Section 4:
where = |O| + |O| 2 + ( -1)|O| 2 is the total number of terms in the objective.
To optimize ( ), we perform mini-batch gradient descent where each minibatch corresponds to a subset of the terms of ( ). On each minibatch, we compute the gradient of the selected terms with respect to the model parameters and use Adam to update the parameters. In our experiments, we use the following optimization hyperparameters: we use 500 types, batches of 8192 terms, an Adam learning rate of 1.0. We initialize all parameters from a Gaussian distribution with mean zero and standard deviation 0.001 and use
6 8 10 12 14 16 18 20 Number of distinct topics 0.00 0.02 0.04 0.06 0.08 0.10 0.12
Total number of distinct topics over 4 weeks in real vs synthetic data.
Figure 5: Fraction of users with a given number of distinct topics in their sets over 4 weeks. Notice the strong correlation between the distribution of the real and synthetic data, despite the fact that this statistic is not an input to the model. 8000 training epochs / data passes. The results are stable to changes in the parameters.
In this section, we evaluate empirically the quality of the synthetic data generated by our model and released publicly [11].
Data validation. First, we verify that the model obtained has an output distribution that closely matches the statistics of interest that we have defined in the previous sections. In Figure 3, we show the cumulative distribution of the absolute and relative errors of the statistics for a training run of the model. Figure 3a represents the absolute error in percent points while Figure 3b represents the relative error between the statistics computed on the model and on the real data. Notice that virtually all statistics have an absolute error lower than 0.1%. We report the relative error in Figure 3b for all statistics above 0.1%. Notice that the relative error is ≤ 20% for 75% of statistics. This confirms the convergence of our model to an output distribution close to the desired one. To gain a better understanding of the error distribution, in Figure 4, we present the probability density function. Figure 4a reports the PDF of the absolute error in percent, while Figure 4b reports the PDF of the relative error for statistics with ≥ 0.1% value. Notice how both the absolute and relative error have a large mass centered around 0 showing that the distribution mean matches the real data.
Additional validation of non-constrained statistics. So far we tested that our model is able to capture reasonably well the statistics imposed as constraints. In Figure 5, instead, we report the distribution of a statistic not explicitly constrained by the model-the number of distinct topics in a user's sets over 4 weeks-on real and synthetic data. Notice the strong correlation between the distribution of the real and synthetic data (89% Pearson correlation coefficient). This is particularly interesting because this statistic is not part of the inputs of the model, this shows that our model is able to capture reasonably well additional properties of the data beyond the ones explicitly imposed in the training process.
In this section, we present the results for the re-identification risk analysis on our synthetic data and show how it represents well the re-identification risk measured on real data. Before presenting the empirical results we define the approach used for defining and measuring re-identification risk.
6.1.1 Methodology. In order to show the replicability of prior work using our synthetic data, we follow the same set up of [9]. We sketch briefly the random-user model for re-identification risk introduced in [9] and refer to the paper for more details. In this model, an attacker observes the Topics API outputs for a set U of users on a website 1 for a period of weeks. The adversary has hence a table
containing the topics of the users for weeks on the site. Then, a random user * (unknown to the attacker) is sampled uniformly from U and the Topics API output trace = ( 1 ( * , 2 ), . . . ( * , 2 )) for that user, observed on a different website 2 during the weeks, is revealed to the adversary. The adversary has to output a prediction ( , ) ∈ U for the identity of the user ∈ U that produced the trace . The re-identification risk is measured as the probabilityover the random sampled user * , randomness of the API and of the attacker-that the prediction of the attacker is correct, i.e.
Pr * , , ( ( , ) = * ).
The attacker function can be an arbitrary method that attempts to infer the identity of the user from the data. In this work, for replicability, we use two attacks from [9] that are available 4 as open source code. We now present them.
Hamming Attack. Given the sampled trace = ( 1 ( * , 2 ), . . . , (( * , 2 ))
and the table = {( 1 ( , 1 ), . . . ( , 1 ))| ∈ U}, the simple Hamming Attack computes the Hamming distance between the sequence and any sequence ( 1 ( , 1 ), . . . , 1 ( , 1 )) from . The Hamming distance between the sequence of in 1 and sequence is defined as the number of weeks such that ( , 1 ) ≠ ( * , 2 ) (i.e., the number of weeks where output topics are different in the two sites). The simple (unweighted) Hamming Attack predicts the identity of the user generating as the user in with the trace with the smallest Hamming distance to (ties broken randomly).
Attack is a more advanced variant of the (unweighted) Hamming Attack and is based on modeling the joint probability of the outputs on two sites [9]. This attack predicts as the user producing , the user in with the trace with the smallest (weighted) Hamming distance to where the weighted distance employs asymmetric weights 1 , 2 for 1 , 2 ∈ O that are learned from the data to maximize the probability of correctly identifying the user. We refer to [9] for more details. hamming asymmetric_hamming Attack 0.00% 0.10% 0.20% 0.30% 0.40% 0.50% 0.60% 0.70% 0.80% 0.90% 1.00% Risk Comparison of Re-identification Rate Data Kind real synthetic
. We now present the results of the re-identification risk experiment. To compare our synthetic data with the real world data, we obtain a sample of 10 million users' traces observed over 4 weeks from the real user data, and compare them with 10 million synthetic traces (of the same number of weeks) generated by our synthetic data model. On each of these two datasets (separately) we repeat the 2 attacks presented before on a sample of 10240 random users * and define as re-identification risk the fraction of correct answers for the attack / dataset. This process is further repeated for 10 independent trials (for the synthetic data, we repeat independently the training of the model on the DP statistics and the sampling of the data from the model as well).
Our results are presented in Figure 6 which compares the reidentification risk of the two attacks (Hamming Attack and Asymmetric Hamming Attack) on the real user data and on our synthetic dataset. The bars show the mean re-id risk. The error bars, instead, represent 1 standard deviation of the re-identification risk (over the 10 repetitions of the experiment).
We make a series of observations. First, we observe that we closely replicate the observations of prior work [9] concerning the re-identification risk of the two attacks on real data. The Asymmetric Attack is more sophisticated and has a higher re-identification risk. However, both attacks have a re-id risk less than 1%.
More interesting, it is possible to observe that re-identification risk measured by each attack on the synthetic data is remarkably close to the result of the same attack on real data. In both attacks, the re-identification risk on the synthetic data is within 1 standard deviation from the mean re-identification of the same attack on real data. This highlights that our model, despite its necessary simplifications, is sufficiently accurate to characterizing the reidentification risk of the Topics API under the attacks studied.
In this paper we presented a novel methodology for generating synthetic data enabling the study of the privacy properties of the Topics API. Using our method we release an open source dataset [11] that is derived from real user data while providing strong privacy protection. As shown in our experiments, this dataset is accurate enough to preserve important properties of the data including allowing us to replicate a prior re-identification analysis performed on a proprietary datasets. Notwithstanding these positive results, it is important to highlight that like all synthetic data releases, our data can not replicate exactly all properties of the original (private) data. In fact, while we show that many important statistics are accurately preserved, it is indeed possible that the model might not preserve other statistics (including important statistics that are not considered in our work, but are relevant to other studies). In our model, we made several assumptions, especially on the time-stationarity of the user data. We stress that the stationarity assumption in particular is crucial for the validity of our results. While we partially validated these assumptions on the data available, it is possible that the data may evolve over longer time scales (or in the future), diverging from our measured statistics. Moreover, as we observed, since preserving an arbitrary distribution is infeasible due to its extremely large parameter space, our model must necessarily have neglected some aspects of the real dataset. While our methodology focused on replicating some prior attacks on re-identification risk, it is possible that the synthetic data we released may be unable to correctly replicate other methodologies.
While this synthetic data release has its inherent limitations, we believe that our work will benefit the study of the privacy properties of the Topics API providing researchers with access to large-scale and sufficiently realistic data. As future work, we believe that our methodology could be generalized to several Privacy Preserving Ads APIs providing insights in other efforts in this space. We also believe that future work on improving our synthetic data methodology, by for instance, reducing the assumptions needed for its validity, is of great interest. by applying so max, which is also differentiable, to , it follows that is a differentiable function of . With this, we turn to calculating expressions for each statistic computed in Section 4. Calculating the probability that two distinct topics 1 , 2 ∈ O both appear in week ∈ [ ] can be done using the inclusionexclusion principle: The probability of observing topic 1 ∈ O in week 1 ∈ [ ] and topic 2 ∈ O in week 2 ∈ [ ] when 1 ≠ 2 can be calculated using the fact that, conditioned on the type , these events are independent.
Finally, all three functions single , within , and across are differentiable functions of , since they are differentiable in . □ The same is true for 22 , while for 12 we have a 1 in the 2 counts for topics pairs ∈ 0 ( ) and ∈ 1 ( ) ( in the corresponding positions in 12 ). Hence the ℓ 2 norm of the difference is 2 for 11 and 22 and for 12 . □
DP statistics. In Figure 7 we present additional statistics on the top 10 pairs of topics within a week (Figure 7a) and top 10 pairs of topics across two consecutive weeks (Figure 7b). Notice how most top pairs of topics in the * within and * across are from the top topics by frequency Figure 1 as expected. Also notice that due to the correlation of topics in two consecutive weeks several top pairs in Figure 7b have the same topic.
This section studies the extent to which the statistics we measure are stationary over time. We define the following single-week versions of each statistic: These are identical to the statistics defined in Section 4 except that instead of averaging over weeks of training data, they define the statistics from a specific week, or a specific week transition in the case of * across . In Figure 8, we provide the Pearson correlation coefficient between each pair of weeks (or pair of week transitions) for each of the statistics * single , * within , and * across . We see that there is a very high degree of correlation between the statistics, supporting the claim that these statistics are very close to being stationary over time. These results are reported in Figure 8. Notice that for any statistic and for any pair of periods the Pearson correlation coefficient is ≥ 99.8% thus supporting the stationarity assumption at the basis of our model.
https://raw.githubusercontent.com/patcg-individual-drafts/topics/refs/heads/main/ taxonomy_v2.md
We follow the methodology of[9] and omit two complicating details from the actual API. First, the API also returns the cached results of the previous two weeks. Modeling the real output observed by an adtech on a site for weeks simply corresponds to + 2 weeks of observations in our model, so we omit this detail. Second, the API applies a filtering to the output to remove topics that were not observed by an adtech on any site. We make the more pessimistic assumption that no filtering ever happens, as this provides more information to an attacker of the API.
In line with our data access and retention policy, user ids are removed from this data and access is restricted to the latest 28 days of logs. The data was collected for the
weeks between 2024-12-16 and 2025-01-12.
https://github.com/google-research/google-research/tree/master/re_identification_ risk