Evaluating Google’s Protected Audience Protocol

Minjun Long David Evans

University of Virginia University of Virginia
Charlottesville, Virginia, USA Charlottesville, Virginia, USA
ml6vq@virginia.edu evans@virginia.edu

ABSTRACT immediately blocking all third-party cookies, they announced their

While third-party cookies have been a key component of the digital intention to phase them out gradually through a plan they called
marketing ecosystem for years, the way they allow users to be the “Privacy Sandbox”. This initiative aimed to find alternative ways
tracked across web sites raises serious privacy concerns. Google to deliver personalized ads without compromising user privacy by
has proposed the Privacy Sandbox initiative to enable ad targeting phasing out the usage of third-party cookies, fingerprinting, and
without third-party cookies. While there have been several stud- other advertising techniques that enable tracking web users across
ies focused on other parts of this initiative, there has been little multiple sites [32]. While the original plan was to deprecate third-
analysis to date as to how well the system achieves the intended party cookies by early 2022, Google delayed this process to late
goal of preventing request linking. This work focuses on analyz- 2023, partly due to regulatory pressure from the UK’s Competition
ing linkage privacy risks for the reporting mechanisms proposed and Markets Authority (CMA) [20]. Later, Google postponed the
in the Protected Audience (PrAu) proposal (previously known as date again to the second half of 2024 [6], as they have received
FLEDGE), which is intended to enable online remarketing without constant feedback that more time is needed to evaluate and test the
using third-party cookies. In this work, we summarize the overall new Privacy Sandbox technologies before deprecating third-party
workflow of PrAu and highlight potential privacy risks associated cookies in Chrome. As of May 2024, Chrome still does not block
with its proposed design. We focus on scenarios in which adver- third-party cookies by default.
saries attempt to link two requests to different sites to the same Google’s Privacy Sandbox initiative comprises several compo-
user and show that a realistic adversary would be still able to use nents including the Private State Token API for fighting fraud and
the privacy-protected reporting mechanisms to link user requests spam on the web, the Attribution Reporting API for enabling digital
and conduct mass surveillance, even with correct implementations ads measurement, and the Fenced Frames API to strengthen cross-
of all the currently proposed privacy mechanisms. site privacy boundaries [47]. Among all the proposals in Google’s
Privacy Sandbox, most of the work in the privacy research com-
1 INTRODUCTION munity has focused on the Federated Learning of Cohorts (FLoC)
proposal [11], which analyzes users’ online activity within the
As designed, the HTTP protocol is stateless—each HTTP request
browser and group a given user with other users who access sim-
from web browsers is treated independently [18]. To maintain
ilar content. After getting feedback from the FLoC’s Origin Trial,
state, web cookies were introduced. These allow a server to re-
Google replaced the FLoC proposal with the Topics proposal [21]
trieve previously provided information, such as the contents of
in January 2022, where the browser observes and records topics
a user’s shopping cart [29]. Cookies can be categorized as either
that appear to be of interest to the user based on their browsing
first-party cookies, placed by the website owner, or third-party cook-
activity. Ad platforms can then access a user’s interests through an
ies, placed by a site other than the domain hosting the page the
API without obtaining their detailed browsing history.
user visited. Third-party cookies can be used to track user activity
In this paper, we focus on the Protected Audience (PrAu) compo-
across multiple sites. This enables ad targeting which increases
nent (originally called FLEDGE, an acronym of First Locally-Executed
revenue for publishers [30, 38], but raises serious privacy concerns.
Decision over Groups Experiment, and renamed as Protected Audience
To address the use of third-party cookies by companies, the Euro-
in April 2023 [46]). Since March 2022, Chrome has been running
pean Union has adopted privacy regulations with strict penalties
the First Origin Trial (FOT ) on PrAu, which enabled this feature
for non-compliance [31] and the US Federal Trade Commission
for a subset of Chrome users. Sites can also request trial tokens to
(FTC) has raised concerns [17] and taken action [16].
participate in the FOT and thus experiment with the API [43].
Several popular web browsers have taken steps to safeguard user
The PrAu proposal [12] redesigns the advertising ecosystem
privacy by combating tracking. In 2018, Firefox revealed its plans to
by letting the browser client, rather than the centralized market
block third-party cookies based on tracking domains [35]. In 2020,
operator, maintain the information about the user’s interests for ad
Safari became the first widely-used browser to block third-party
targeting. It moves ad auctions from external servers to the client
cookies by default [54]. Google also acknowledged the importance
browser, thus avoids the need to send information that can be used
of protecting user privacy in a 2019 blog post [42], where they im-
to track a user to a centralized ad auction server. PrAu is intended
proved cookie control in their Chrome browser. However, instead of
to enable advertisers to target ads based on user interests, but
This work is licensed under the Creative Commons Attribu- without revealing information about the user—in particular, PrAu is
tion 4.0 International License. To view a copy of this license designed to prevent user tracking by ensuring that advertisers and
visit https://creativecommons.org/licenses/by/4.0/ or send a
letter to Creative Commons, PO Box 1866, Mountain View, CA 94042, USA. publishers cannot link requests to an individual, while enabling
Proceedings on Privacy Enhancing Technologies 2024(4), 892–906 some degree of interest-based behavior targeting.
© 2024 Copyright held by the owner/author(s).
https://doi.org/10.56553/popets-2024-0147
892
Evaluating Google’s Protected Audience Protocol Proceedings on Privacy Enhancing Technologies

Although PrAu shares the goal of grouping users by interests entered into the auction by the buyers. By storing interest groups
with the Topics API, its approach and implications for privacy are in the browser and moving the auction process to isolated browser
markedly different. The Topics API facilitates a better understand- worklets, one running code provided by the prospective ad buyer
ing of the content that users are interested in without sharing and one running code provided by the seller, PrAu aims to enable ad
specific user data, but recent studies have shown that it is it possi- targeting without the privacy compromises associated with third-
ble for adversaries, through statistical modeling and collaboration party cookies. The individual’s interests are stored in their own
with third parties, to re-identify users across different websites browser and can be used for ad targeting without even needing
[3, 25]. In contrast, PrAu is designed to enable advertisers to target to be revealed to the ad seller or a centralized auction server; the
specific user groups without disclosing individual user data but its buyer can buy an ad to be displayed to the individual on the seller’s
privacy mechanisms and potential vulnerabilities have not been site without learning about the site visited. After the auction ends,
as thoroughly explored. Since there are several parties involved in the winning ad will be rendered in a fenced frame. Unlike iframes,
the PrAu protocol, any part of the lifecycle may be compromised fenced frames allow access to cross-site data without sharing it
and result in weaker privacy protection than intended. Thus, it with the embedding context [45]. Code running in a fenced frame
is worth examining the whole workflow of PrAu to evaluate how cannot communicate with the embedding context and vice-versa,
well it satisfies its key privacy goal of preventing request linking. though it may leak information through side channels [44].
We focus on the ad reporting mechanism in PrAu as this is the
only explicit communication channel that sends user data back to
centralized servers.
Although Google’s most recent announcement set the date for 2.1 Protocol Overview
removing third-party cookies in 2024 [6], the currently available Figure 1 shows the design of PrAu. Our understanding of the proto-
implementation of PrAu is only partial. Many components are not col is based on publicly-available information, including Google’s
yet implemented including the Trusted Key/Value Service, the in- official documentation [12, 13], examining the code provided in
tegration of k-anonymity, and Trusted Aggregation Service, and associated github repositories [53], observing network traffic from
much of the documentation is still incomplete. Our analysis and the FOT , answers to our questions from the Google team, and our
evaluation are based on the official PrAu API developer guide [12] own inferences regarding the planned design based on our best
and experiments on the available FOT implementation of the PrAu interpretation of the available material. Figure 5 (in the Appen-
API. In this sense, our security analysis is premature—we analyze a dix) shows what is currently implemented in the FOT , which does
system that does not yet fully exist and for some aspects we must not incorporate the Trusted Aggregation Server and other essen-
speculate on what the eventual design will be. Nevertheless, there tial aspects of the planned design. Since Chrome is still supporting
is an urgent need for the privacy research community to indepen- third-party cookies, the lack of privacy mechanisms in the currently
dently and objectively evaluate privacy risks of the proposed PrAu deployed PrAu is reasonable since the tracking they are designed to
design before it is deployed at a wide scale, and hope the results of thwart is fully enabled by the supported third-party cookies. How-
such an evaluation will influence the eventual deployment of PrAu. ever, once Chrome phases out third-party cookies, the adoption of
PrAu’s full suite of privacy mechanisms is intended to inhibit the
Contributions. We summarize the PrAu protocol, describing the
type of request linking that third-party cookies currently enable.
interactions through the PrAu APIs among its components (Sec-
PrAu allows websites to store information about a user’s interests
tion 2). To analyze how well the PrAu design meets its privacy
in the form of interest groups that are stored in the browser and tied
goals, we introduce a threat model (Section 3.1) and evaluate three
to the user profile for up to 30 days. Note that interest groups are tied
scenarios in which advertisers may use PrAu auctions to track users
to a browser profile instead of a Google account, so are not shared
between sessions (Section 4). We find that the aggregate reporting
across different browsers and devices even when they are connected
mechanisms provided by PrAu can be used to link requests with
to the same Google account. While the content of the group can
high accuracy, scaling up to a level where mass surveillance is possi-
be updated by the owner of the group by providing the name of
ble (Section 4.3) even when the proposed 𝑘-anonymity mechanisms
the interest group, it cannot be read directly—interest groups are
are implemented (Section 5). Although there is no simple fix that
stored in an internal data structure and no API is provided to obtain
provides both the desired reporting and unlinkability, we discuss
a user’s interest groups. When a user visits a site that sells ad space,
several potential mitigations in Section 6.
buyers who are the owners of interest groups stored in the user’s
browser can participate in an auction. The in-browser auction will
2 THE PROTECTED AUDIENCE PROTOCOL obtain some information from the buyer’s code such as bid value
The PrAu protocol enables on-device auctions that run in the user’s and ad information, a score from the seller’s code for each potential
browser instead of running on a remote server to support ad target- ad, and select the ad with the highest score to display.
ing (including remarketing, which lets advertisers customise their The PrAu design relies on several Trusted Servers operated on
display ads campaign for users who have previously visited the the behalf of buyers and sellers. These services are trusted based
website [34]) without third-party cookies. Potential ad buyers can on code reviews conducted by a trusted auditor and the servers
perform on-device bidding based on interest group metadata and that receive and respond to requests are required to run within a
data loaded from a trusted server at the time of the on-device auc- Trusted Execution Environment (TEE). A TEE is an isolated execu-
tion, and the sellers who own ad display space on the visited page tion context that provides hardware memory protection and storage
can perform on-device ad selection based on bids and metadata protection through cryptography, ensuring that its contents are
893
Proceedings on Privacy Enhancing Technologies Evaluating Google’s Protected Audience Protocol

K-anonymity
Buyer's Server Browser Core Seller's Server
Server
1. visit

2. joinAdInterestGroup
(interestGroup, time) Join(b, t, s)
3. visit

4. runAdAuction
(auctionConfig)
fetch bidding code
Query(t, s)
Update k-anon bit

Buyer's Trusted Bidding Auction Seller's Trusted

K/V Server Worklet Worklet K/V Server

5a. send bidding 5c. send scoring

signals keys 5. Connect controlled signal keys
inputs and outputs across
5b. send bidding 5d. send scoring
worklets to run auction.
signal values signal values

6. Connect controlled
inputs and outputs across
worklets to report
outcome.

6a. send encrypted report

6b. send encrypted report after some time
after some time

update interest group content

Buyer's Trusted Aggregation Seller's Trusted

Aggregation Server Coordinator Aggregation Server

7a. send 7e. send

encrypted report(s) 7f. send metadata encrypted report(s)
and bucket key list 7b. send metadata and bucket key list
in report(s)
in report(s)
7g. issue decryption key and
7c. issue decryption key and validate requests
7d. send 7h. send
validate requests
aggregated report aggregated report

Figure 1: Protected Audience Protocol. For simplicity, we show a single seller and buyer (who is also the winner of the auction), although
there would typically be many buyers and sellers. Dashed lines indicate requests that do not necessarily happen at a particular step in the
protocol, and may be interleaved with other request in different ways. The black dashed line for “fetch bidding code” is discussed at the
end of Section 2. The black dashed line for “update interest group content” is requested daily, detailed in Section 2.2. The requests to the
K-anonymity server are done periodically, details in Section 2.6. The controlled inputs and outputs across worklets are specified in Figure 4.

shielded from observation and tampering by unauthorized parties, Step 4. The seller’s script running in the browser calls runAdAuc-
including the root user [40]. tion(·) to initiate an auction (Section 2.3).
The interactions among buyers, sellers, and browsers in PrAu
Step 5. The browser runs auctions with each potential buyer’s
can be divided into the following main steps, depicted in Figure 1:
code in a separate bidding worklet and the seller’s code
running in the auction worklet (Section 2.4). Code in
worklets can send requests to Trusted K/V Servers to
Step 1. The user visits a buyer site. exchange real-time information [24].
Step 2. The buyer’s script running in the browser calls joinAdInter- Step 6. After a random delay of up to one hour, encrypted event-
estGroup(·), which attaches an interest group to the user. level reports on the auction results are sent to servers
Step 3. The user visits the seller’s site. owned by the buyer and seller.
894
Evaluating Google’s Protected Audience Protocol Proceedings on Privacy Enhancing Technologies

Step 7. Buyers and sellers submit encrypted event-level reports 2.4 Running the Auction in the Browser
with queries to their respective Aggregation Server, which After the seller’s script initiates the auction by calling runAdAuc-
interacts with the Aggregation Coordinator to enable de- tion(·) (Figure 1, Step 4), the browser creates worklets running code
crypting the event-level reports to produce and return a provided by the buyers and sellers. Functions running inside the
privacy-noised aggregated report (Section 2.5). worklets provide controlled communication channels through their
Note that none of these privacy protections are implemented in inputs and outputs, and the browser connects those inputs and
the FOT , which just immediately sends a cleartext report directly outputs across the worklets. To prepare the execution environment
to the buyer and seller. In our experiments with the current imple- of the auction, the browser first iterates through all the interest
mentation, we also observed additional messages with associated groups associated with the user and creates one bidding worklet for
privacy risks depending on the server and browser implementation. each interest group the seller allows to participate in the auction
For example, when we set a "No-Store" cache policy for the buyer (specified in the auctionConfig object). It also creates an auction
server, the browser sends a request to retrieve the buyer’s bidding worklet for the seller. Then, the browser obtains the code for each
code via the url specified in biddingLogicURL between Step 4 and buyer involved in the auction (which should already be cached
Step 5 (shown as the dashed line in Figure 1). This is a privacy in the browser) from the biddingLogicURL field in each interest
concern as the buyer server can log information of this cross-site group and gets the seller’s code from the decisionLogicURL field in
request, such as timestamp, IP address, and user-agent headers. seller’s auctionConfig object. The code for each buyer will run in
Although ensuring the deployed protocol matches some specified a corresponding bidding worklet to provide bids for each interest
protocol that has been analyzed to satisfy desired properties is group and the seller’s code will run in the auction worklet to score
essential, PrAu is not yet at the stage where the actual protocol these bids. The ad with the highest score is selected as the auction
is clearly specified. Since our goal is to understand fundamental winner to be displayed in the browser.
issues with the intended PrAu protocol, we conduct our analysis
based on our best interpretation of the plans for PrAu, assuming
that proposed privacy mechanisms (like the 𝑘-anonymity server)
2.5 Aggregate Reporting Service
will be implemented and that this and other implementation issues
will be fixed in the eventual PrAu implementation. Our focus is on In the FOT , event-level reporting happens right after an auction
identifying issues in the intended PrAu protocol as designed instead ends, as the winning buyer and the seller can send arbitrary in-
of the current implementation in the FOT . formation as arguments to reportWin(·) and reportResult(·) in the
form of a URL parameter. This poses obvious and severe privacy
risks. For example, it allows both parties to determine when a user
2.2 Attaching an Interest Group
visited the seller’s site. The buyer could also include a tracking
To attach an interest group to the user’s browser (Figure 1, Step 2), ID in the interestGroup object and send it to the seller via the ad
the buyer’s script in the browser calls the joinAdInterestGroup(·) metadata in the generateBid(·) function. Similarly, the seller could
API with two parameters: interestGroup and time. The time param- include a tracking ID in the auctionConfig object when initiating
eter to the joinAdInterestGroup(·) API is a number specifying the the auction and transmit it to the buyer through the sellerSignals
duration of the membership in seconds. The maximum value PrAu in the reportResult(·) function. Through this method, the buyer
allows for time is 30 days (2,592,000 seconds). The interestGroup and seller can track a user by exchanging tracking IDs through the
is a JSON object that includes: (1) the interest name, an arbitrary reporting URL.
string selected by the buyer site; (2) the owner of the interest group The proposed PrAu design avoids the most obvious privacy viola-
which is typically the buyer site’s origin; (3) a bidding URL; (4) an tions by encrypting event-level reports and waiting a random time
update URL, which the browser requests once daily to replaces delay before they are sent. The Trusted Aggregation Service aims
fields (except the interest group name and owner) in the original to allow participants of PrAu auctions to create summary reports
interest group object; and (5) an ad field that can contain arbitrary that can be used to understand ad placements without compro-
ad metadata. The bidding URL provides the buyer’s code will be run mising individual users (Step 7 in Figure 1). To maintain privacy,
in a browser worklet to generate bids and report auction results. To the aggregation service code must be audited and approved before
avoid side channel leaks, this code should be requested periodically deployment and operate in a TEE in a public cloud platform.
and cached in the browser (the current FOT implementation does As depicted in Figure 1, only the winning bidder learns about the
not always do this, as discussed in Section 2.1). auction. Buyers can also implement a reportLoss(·) function that
provides information to the buyer when they participate but lose an
2.3 Initiating an Auction auction. The details of what information is passed to this have not
To start an auction (Figure 1, Step 4), the seller’s script in the browser yet been determined. The current plan is to support unencrypted
calls runAdAuction(·), passing in auctionConfig, a JSON object event-level reporting in the reportWin(·) function until at least 2026,
that contains information including the seller domain URL and a while using the the privateAggregation(·) API for losing buyers,
decision URL. Similar to the bidding URL, it points to seller’s code but the details of this plan have not yet been disclosed [52]. For
that is later used in the browser to score different bids and report our analysis, we assume the proposed design (post-2026) in which
auction results. The auctionConfig contains other fields such as only encrypted reports are sent back to the buyer or seller and
auctionSignals, which will be passed to all participating buyers all semantic information about auction results has to be obtained
during the auction. through the aggregation server.
895
Proceedings on Privacy Enhancing Technologies Evaluating Google’s Protected Audience Protocol

After an auction ends, the buyer’s code can generate event- is large enough to provide a sufficiently tight lower bound on the
level reports in the form of key-value pairs (𝑘, 𝑣) by calling the number of different browsers in a group, but these identifiers are
privateAggregation(·) API within the worklet. The bucket key 𝑘 is not unique. Many browsers will share the same identifier, which
a BigInt with maximum length of 128 bit and the value key 𝑣 is a mitigates the privacy risks associated with the identifier. Since the 𝑘-
32-bit integer. The browser then generates an encrypted event-level anonymity check is performed on both interest group name and ad
report by encrypting the (𝑘, 𝑣) pair. Finally, the browser sends this creative URLs, t specifies the type of the object. At the 𝑘-anonymity
encrypted event-level report to the buyer and seller’s server after server receiving the Join(·), the browser’s identifier b is inserted
some random delay time up to an hour. into the set of browser identifiers associated with the object s. The
In order to prevent adversaries from using the reports to leak size of this set is what determines if a 𝑘-anonymity check is passed.
too much information, PrAu implements restrictions on the API The Query(·) call has two parameters: a type t and an object
calls in the reporting function. When the buyer or seller calls the represented by a hash s. When the browser makes a Query(·) call,
privateAggregation(·) API in the worklet function, the browser it checks the number of browser identifiers associated with the
limits the total value that can be contributed to bucket keys. The object s and responds with a Boolean value indicating whether the
sum of all contributions across all buckets, i.e., the total value of 𝑘-anonymity check has passed (that is, the group associated with s
all the contributions, may not exceed 216 . If this limit is exceeded, has at least 𝑘 members).
future contributions will be dropped without notification, meaning The 𝑘-anonymity check is applied in two places: 1) during the
no further encrypted event-level reports can be sent to the API auction phase—where an ad must pass the 𝑘-anonymity check to
caller’s server once the budget is depleted. The contribution limit participate in the auction; and 2) at the reporting time, to determine
will be reset over a rolling 10-minute window for each buyer or if the interest group name is included during report generation.
seller site with a daily cap of 220 . The difference between these two checks is whether or not the
Later, when buyers and sellers query the aggregation servers, interest group name is included in the checking object. For the first
they send a collection of encrypted reports along with a list of check, the interest group name is not included, and the object is
bucket keys to be included in the aggregated report. The aggre- a tuple consisting of the interest group owner’s URL, the bidding
gation service sums the value for each bucket across all provided script’s URL, the creative’s URL, and the ad’s size. The reason the
encrypted reports, add noise to provide a differential privacy bound, interest group name is not included in the first object to check
and returns an aggregated report as a histogram with a noised sum is to allow advertisers implement various bidding strategies (e.g.
for each bucket. All bucket keys in the query will appear in the multiple small-size interest groups can share some ads). For the
summary report; if a key does not appear in any of the encrypted second check, the interest group name is also included, meaning
reports, it will still be included as zero plus noise value in the that there are interest groups that pass the first check to be eligible
aggregated report. for the auction, but not the second one. This is intended to prevent
The coordinator in Trusted Aggregation Service limits the num- advertisers from using information in the interest group name to
ber of queries each report, and PrAu plans to enforce a non-duplicate generate report if the interest group has less than 𝑘 users.
rule, only allowing one query per event-level report. This means Although the 𝑘-anonymity check is designed to prevent tracking
each encrypted report can only appear once within a batch and individuals, in Section 5 we show how the 𝑘-anonymity checks are
cannot contribute to more than one aggregated report. insufficient for preventing high confidence large-scale surveillance.

2.6 Checking for k-anonymity

The PrAu design includes 𝑘-anonymity checks with the aim of pre-
venting buyers from using interest groups to track users [22]. The 3 ATTACK OVERVIEW
𝑘-anonymity [41] privacy notion aims to safeguard the identities In the current online advertising ecosystem, third-party cookies al-
of individuals within a dataset by grouping them into clusters of low websites to track users across sites and build user profiles. This
at least 𝑘 individuals with similar attributes. PrAu plans to enforce information is then used by buyers and sellers to tailor personalized
𝑘-anonymity with 𝑘 = 50 over a 30-day period with hourly updates. ads to users. The goal of PrAu is to support targeted advertising
The 𝑘-anonymity tracking is done using the 𝑘-anonymity server, without third-party cookies or a centralized data collector. There-
with Join(·) API calls used to record group membership and Query(·) fore, it is worth investigating how well PrAu achieves this goal of
calls used to check if there are at least 𝑘 members in the group preventing user tracking.
associated with an object. These calls are shown in Figure 1, but the To limit our scope, we only consider the goal of protecting user
actual calls are made outside of the critical path of an ad auction. The privacy from buyers and sellers operating in the ad ecosystem and
browser periodically reports new objects, which are created when a focus on the ability of an adversary to link two requests. There are
buyer calls the joinAdInterestGroup(·), via Join(·) calls. Similarly, the numerous other security and privacy aspects of PrAu, including
browser periodically sends Query(·) requests to the 𝑘-anonymity preventing buyers and sellers from manipulating the ad auctions
server for relevant objects, caching the results for use during in- to their benefit, protecting the confidentiality of buyers from other
browser auctions. buyers and sellers, and other ways information about user interests
The Join(·) call has three parameters: a browser identifier b, a type can be leaked to buyers and sellers. These are important issues that
t, and an object represented by a hash s. The browser identifier b is merit consideration, but are outside the scope of this analysis which
a 𝑗-bit identifier, where 8 ≤ 𝑗 ≤ 16. The space of browser identifiers only considers user tracking through linking requests.
896
Evaluating Google’s Protected Audience Protocol Proceedings on Privacy Enhancing Technologies

3.1 Threat Model The general attack process unfolds over the following four steps:
To assess the effectiveness of PrAu in preventing tracking, we con-
Step 1. Users visit the primary site where the adversary asso-
sider a threat model where adversaries who can control buyer do-
ciates the user’s browser with 𝑛 interest groups, each
mains and seller web servers attempt to gather information about
representing a different buyer controlled by the adver-
users. The adversary’s goal is to link requests made to two different
sary.
sites to the same user by using information provided through PrAu
reports. Step 2. Before the interest groups expire, a user navigates to the
We assume that other currently available ways to link user re- secondary site, which is a sensitive site where the user
quests will not be available, so the adversary cannot identify a user expected to be anonymous. The adversary controls an
through a stable IP address or digital fingerprinting. Without mask- ad auction on the secondary site, and lets each of the 𝑛
ing the IP address or protections against fingerprinting, most users colluding buyers win one of 𝑛 separate auctions.
today can be uniquely identified by their visit directly [27, 33], so
there would be no additional linking risk from PrAu in situations Step 3. After winning the auction, each colluding buyer gener-
where the two requests can already be linked. In a future where ates encrypted reports using identical bucket-value pairs,
fingerprinting protections are deployed and third-party cookies are which are then sent to the adversary.
eliminated, it becomes difficult to track users and link requests di- Step 4. The adversary submits all the encrypted reports with
rectly. Hence, the focus of our analysis is to understand how much selected bucket keys to the Aggregation Service and re-
these risks increase over when PrAu is deployed over the (hopeful ceived the aggregated output. By analyzing the aggre-
future) baseline where user tracking would otherwise be infeasible. gated output, the adversary links user visits across the
We focus our study on the design of PrAu and the information primary and sensitive sites to identify users on the sensi-
channels provided through auction reports, so further assume the tive site.
browser can be trusted and that everything works as intended. This
requires that: Section 4 explains how an adversary can execute the attack in
• Dedicated worklets created by the browser are isolated with- three different scenarios: linking a single targeted user, linking one
out access to outside network or storage, and there is no way out of many users, and conducting large-scale surveillance.
for code running in other worklets to exploit side-channel
attacks to infer information from these communication chan- 3.3 Attack Feasibility
nels.
As outlined in the attack steps, the attack which enables linking
• The TEEs used to execute the K/V servers and Aggregation
is only possible in settings where a user makes requests to both
servers (Section 2.5) operate securely as trusted execution
a primary site and a sensitive secondary site, both of which are
environments without leaking and information, and the attes-
controlled by the adversary who wants to link the requests. In PrAu,
tation and management of the attestation keys is all correct
the duration that an interest group can remain active in a user’s
and invulnerable.
browser is capped at 30 days. Consequently, the feasibility of a
• The process used to audit the code for the K/V and Aggrega-
linking attack is contingent upon the user visiting both sites within
tion servers is sound and ensures that any code that passes
this 30-day window.
this process cannot violate the required properties.
Effectiveness of the attack also depends on an adversary’s abil-
All of these are strong assumptions and difficult to achieve in ity to control multiple buyer domains, and Google controls access
practice. Even in cooperative settings, implementing differential to the APIs needed to participate in ad auctions. As various APIs
privacy mechanisms correctly (as is required for the aggregate from Google’s Privacy Sandbox begin to reach general availability,
reports) is challenging [9, 26, 28, 48] and analyzing software for Google has outlined plans to implement a verification process for
security vulnerabilities is challenging and can rarely be done com- entities accessing these APIs. Google initiated the enforcement of
pletely [23, 36, 51]; in adversarial settings where the code author enrollment starting in mid-October 2023, with the release of Chrome
may be deliberately making their code hard to analyze and to hide 118 Stable. To ensure auditable transparency, the enrollment infor-
a prohibited behavior in it, relying on perfect audits requires a leap mation related to each company will be publicly accessible. This
of faith [1]. There are many subtle ways a program can be designed verification procedure is designed to mitigate API misuse such as
to intentionally leak data [39], and no known method, even with preventing one developer from impersonating another and restrict-
source code available, to ensure all leaks are detected. ing their access to the APIs. However, the underlying business
model of selling ads to many buyers around the world is incom-
3.2 Attack Steps patible with a restrictive or costly verification procedure. Enrolling
To execute the attack, the adversary needs to control at least one as a buyer or seller to access these APIs only requires basic busi-
primary site where visitors reveal their identities, and a sensitive ness contact information, a D-U-N-S number for the organization
secondary site where users expect to be anonymous. The adver- (which can be obtained for free by providing some information in
sary’s goal is to link requests to the sensitive site to requests to the a web form) [10], and the necessary input for API or server config-
primary site, and thereby learn the identity of an anonymous user urations [19]. Consequently, it does not seem unreasonable for a
on the sensitive site. In addition, the adversary may control some motivated adversary to be able to enroll many buyers. Our analysis
other domains, which are enrolled as 𝑛 buyers. in Section 4.3 shows that 200 buyers is sufficient for large-scale
897
Proceedings on Privacy Enhancing Technologies Evaluating Google’s Protected Audience Protocol

surveillance with high confidence based on just a single visit to the way. Nevertheless, such a simple attack may already be a serious
secondary site. privacy risk in some scenarios such as when an oppressive govern-
ment has a desire to gather evidence against a suspected dissident,
4 DATA LEAKAGE ANALYSIS but its scale is limited in that within a given time period only a
A primary motivation of the push to eliminate third-party cookies single, predetermined victim identity can be linked. In the next
is to make linking user behaviors across websites infeasible, or at scenario, we consider a more scalable linking attack.
least expensive enough for an adversary in order to disrupt the
most extensive user tracking. Hence, we focus our analysis on how 4.2 Scenario 2: Linking One of Many Users
well the PrAu design maintains the unlinkability goals that under- We consider a simple but realistic scenario where in addition to
lie the push to eliminate third-party cookies. We consider three controlling the primary and secondary websites, the adversary also
different scenarios based on the number of candidate individuals controls some additional ad buyer sites. Instead of just linking a
to link: Section 4.1 is the simplest case where the adversary has a single known user as in the previous scenario, now the adversary
single target individual in mind who visits a first server and wants has a list of 𝑘 candidate users (which could be everyone who visits
to determine if they are linked with a request to a second server; the primary site). We assume that some of the candidate users
Section 4.2 considers an adversary who wants to link any one of visit the primary site and subsequently visit the secondary site.
many candidates across requests; and Section 4.3 analyzes an ad- The adversary’s goal is to link these two requests to identify with
versary who want to perform mass surveillance by linking requests confidence which of the candidate users have visited the secondary
from a large pool of candidates across two sites. (sensitive) site.
The aggregate reporting service (Section 2.5) and the 𝑘-anonymity When a user visits the primary site, it can call the joinAdInterest-
check (Section 2.6) are two main features in the PrAu design in- Group(·) API on behalf of all 𝑛 colluding ad buyer sites (one of which
tended to prevent request linking. For clarity of presentation, we is the primary site), assigning a user identifier (UID) included in the
do not include the 𝑘-anonymity check in this section, but show in interest group name. This allows each buyer site to associate a user-
Section 5 how the 𝑘-anonymity checks can be circumvented. specific interest group with the user. Later, when the user visits the
secondary site, it offers 𝑛 ad spaces, each with an associated auction
4.1 Scenario 1: Linking a Single Targeted User that is designed to be won by a different one of the 𝑛 buyers.2
Consider a simple scenario where an adversary controls two sites— As outlined in Section 2.5, upon winning an auction, buyer
one buyer site and one seller site. We assume that the targeted user worklets running in the browser can generate encrypted reports
visits a primary site, and some time later, visits the secondary site. in the form of key–value pairs that are sent to the buyer’s server.
The adversary’s goal is to link these two requests. This models the In this case, in the reportWin(·) function, all buyers use the same
scenario where, for example, the primary site is a non-sensitive user identifier (UID) recorded in the interest group name as the
site such as a shopping or news site that the user visits without key and the full buyer-sensitivity budget as the reporting value.
concealing their identity and the secondary site is a politically Consequently, within an hour of the auction concluding, each of
sensitive site which a user visits expecting anonymity. In the PrAu the 𝑛 winning buyers receives an encrypted report with value ℓ1
protocol, the primary site acts as an ad buyer, and the secondary recorded in the same UID bucket.
site as an ad seller. Since these encrypted reports will be sent out of order within one
When the targeted user visits the primary site, the site can asso- hour after the auction ends, when any one of the colluding buyer
ciate a user-specific interest group with the user.1 Later, when the sites receives the first encrypted report it can notify the secondary
user visits the secondary site, that site sets up an auction that will site which can update the auctionConfig to prevent this set of
be won by the primary site as the buyer. This causes the buyer’s colluding buyers from participating in any further auctions until
worklet running in the browser to generate an encrypted report all 𝑛 reports have been received. In this way, when the adversary
in the reportWin(·) function (Step 7, Figure 4), which is sent to collects the batch of encrypted reports from the 𝑛 buyers within
the buyer’s site. Therefore, once the primary site receives this en- an hour, it is certain that only one user out of 𝑘 target users visited
crypted report, without needing to decrypt it, the adversary can the tracked site. This simplification makes the analysis easier and
already determine (with certainty) that the targeted user visited the enables high confidence for in the one target user identified. In
secondary site. The protocol imposes a random delay of up to an Section 4.3 we describe a more efficient scheme for tracking large
hour before the report is transmitted, so the buyer will not learn numbers of users.
the exact time of the visit, but will know that the specific targeted Once all 𝑛 reports have been received, the adversary queries the
user visited the secondary site sometime within a hour of the time aggregation service using the set of UIDs corresponding to the list
when they receive the report. of target users.
This attack illustrates the danger of covert channels in a set- Query Semantics. Let’s denote 𝑄 as a query function executed by
ting where adversaries have the ability to run their own code in the buyer to the aggregation service, 𝑅 as a set of encrypted reports
an environment with access to sensitive information, and have a chosen for a specific query, and 𝐵 as a list of bucket keys chosen for
communication channel back to receive results from this code. It a specific query. Then we can represent a query and its response
violates the unlinkability goals of PrAu, but only in a very limited as 𝑆 ← 𝑄 (𝑅, 𝐵), where 𝑆𝑖 = Σ𝑟 ∈𝑅 𝐵𝑖𝑟 + Laplace(0, 𝑙𝜖1 ), where 𝜖 is
1 The 𝑘 -anonymity checks should prevent this interest group from participating in the 2 There is no apparent limit to the number of ad spaces that can be sold on a single
auction, but as we discuss in Section 5, they can be circumvented. webpage visit. We have tested thePrAu protocol with up to 200 buyers.
898
Evaluating Google’s Protected Audience Protocol Proceedings on Privacy Enhancing Technologies

1.0
1. With the PrAu default setting of 𝜖 = 10, the expected accuracy
exceeds 99% with only two colluding buyers with 1 million targeted
P(xj is the Largest among k Outputs)

0.9
users, so we analyze with a lower privacy loss parameter of 𝜖 = 1.
0.8 As the aggregation service does not pose a limit on the length of
0.7 bucket list in the query and the bucket key has a maximum of 128
0.6
bits, the number of candidate users 𝑢 can be large. For reference,
it takes around 35 seconds for the Aggregation Service in local set
0.5
up to process a bucket key list with length of 1 million entries [37].
0.4 Thus, identifying one user out of millions of potential candidates
0.3 k=2 appears to be realistic.
k=100
0.2
As the number of reports (which is the number of colluding
k=1K
k=10K buyer sites controlled by the adversary) aggregated increases, the
0.1
k=100K adversary quickly reaches a high expected accuracy on identify-
0.0 k=1M ing which user on the target list visited the tracked site. With 13
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 colluders (the primary site and 12 additional buyers), the expected
Number of Colluding Buyers accuracy in prediction of this simple attack exceeds 99 percent
when the target user list has 1,000 users. Even when there are one
Figure 2: Expected accuracy for predicting the targeted user’s million target users, an adversary with at least 15 colluding buyer
presence on the secondary site (𝜖 = 1). sites can identify a user who visits the secondary site with high
confidence. This is alarming—obtaining buyer identities is unlikely
to be difficult and the economics of the system require that it be
the privacy loss budget. When the browser enforces a maximum relatively easy to set up new entities as ad buyers.
of 𝑙 1 impact for each user visit on any site over 10 minutes, the
sensitivity of a single report is 𝑙 1 , so this provides 𝜖-Differential Enhancements. The contribution limit for a single report is set
Privacy according to the Laplace Mechanism [15]. at 216 which is used as the sensitivity in the differential privacy
The aggregation service outputs a vector of length |𝐵|, where mechanism. However, this limit is reset within a rolling 10-minute
each value is a noised value. For the user who visited the tracked window for each buyer or tracked site, with a daily cap of 220 . This
site, the aggregated output value of that UID will be 𝑛 · ℓ1 + noise; for means that if the target user visits the secondary site multiple times
all of the other UIDs the value will be 0 + noise, where each noise throughout the day, the adversary could potentially generate up
value is sampled independently from the Laplace distribution to to 16 · 𝑛 reports per day for that single target user. This increased
satisfy the 𝜖-DP guarantee (assuming sensitivity ℓ1 , which is now volume of reports can significantly improve the expected accuracy
effectively violated by the collusion). A simple attack just accuses in prediction in settings where only a few colluding buyers are
the user with the UID associated with the highest value in the available. Furthermore, instead of using full contribution budget
aggregate histogram. when a target user visits the tracked site, the adversary can allocate
the budget in other ways to track more than one user at a time,
Effectiveness. To evaluate the effectiveness of this attack, we which we discuss next.
present a theorem to quantify the expected accuracy of adversary’s
prediction algorithm with respect to the number of target users, 4.3 Scenario 3: Mass Surveillance
the number of colluding buyers, and the privacy loss parameter.
The attack in the previous scenario can identify a single user from
Theorem 4.1. The number of target users is 𝑢, 𝑛 is the number a large candidate pool, but does not demonstrate the risks of mass
of colluding buyers controlled by the secondary site, and 𝜖 is the surveillance that are the primary motivation for eliminating third-
privacy loss parameter. Each 𝑌𝑧 is independently sampled from party cookies. In this scenario, we analyze the potential for mass
a Laplace distribution, Laplace(0, 𝜖1 ). Given an aggregated report surveillance after third-party cookies are eliminated and PrAu is
consisting of noisy outputs 𝒙 = [𝑥 1, 𝑥 2, . . . , 𝑥𝑢 ], and where for one deployed. Here, we consider the same scenario as in Section 4.2,
specific 𝑗 ∈ 𝑢, 𝑥 𝑗 = 𝑛 + 𝑌 𝑗 and for all other 𝑖 ∈ 𝑢, 𝑖 ≠ 𝑗, 𝑥𝑖 = 𝑌𝑖 , but instead of linking one user with 𝑛 reports per query to the
there exists an algorithm that given 𝒙 can predict 𝑗 with expected Aggregation Service, the adversary collects 𝑛 · 𝑢 reports from 𝑛
accuracy: colluding buyers corresponding to 𝑢 candidate user visits, queries
∫ ∞ the aggregation service with a fixed set of bucket keys, and infers
Accuracy = 𝑓Laplace (𝑌 𝑗 ) · 𝐹 Laplace (𝑛 + 𝑌 𝑗 )𝑢−1𝑑𝑌 𝑗 the presence of many users (approaching the number of visitors, 𝑢)
−∞
out of the large candidate pool based on the output.
Here, 𝑓Laplace (𝑥) and 𝐹 Laplace (𝑥)represent the probability density The main idea behind the attack is instead of using each bucket to
function and the cumulative distribution function of Laplace(0, 𝜖1 ). represent one user, we use the buckets as a Bloom filter to enhance
See Appendix B for a proof of the theorem and an explanation of tracking capabilities. The process of reporting and querying is a
numerical method we use to approximate the value of the integral. straightforward application of the Bloom filter [4], modified to
Figure 2 shows the relationship between the number of colluding account for noise in the aggregate reports. In a standard Bloom
buyers and the accuracy of the adversary’s prediction algorithm. filter, set membership is recorded using a vector 𝐵 of size 𝑚. There
We show the results for when the privacy loss parameter 𝜖 is set to are 𝑎 independent hash functions, ℎ 1, . . . , ℎ𝑎 , and when an element
899
Proceedings on Privacy Enhancing Technologies Evaluating Google’s Protected Audience Protocol

𝑧 is added to the set the values of each corresponding bit ℎ𝑖 (𝑧) %𝑚 is After receiving the noisy outputs from the Aggregation Service,
set to 1. An element 𝑧 is predicted to be in the set if Σ𝑖 ∈1...𝑎 𝐵 [ℎ𝑖 (𝑧) % the adversary’s task is to predict which users visited the tracked sec-
𝑚] = 𝑖. This provides a guarantee of no false negatives, and with ondary website. The adversary does this by examining the returned
appropriate parameters can achieve a very low false positive rate. vector of 𝑚 noisy values and checks the 𝑘 indices corresponding to
To adapt this approach to the PrAu setting the we need to account each user. For each user, these 𝑘 noisy values in 𝐵 report are at the
for the noise added to the aggregate reports. The protocol design non-zero positions of 𝐵 target . We denote this as 𝒙 = [𝑥 1, · · · , 𝑥𝑎 ],
is similar to the one from Scenario 2, except now each colluding where each 𝑥𝑖 is the output after adding noise at that position,
buyer computes the hash the UID with 𝑎 distinct hash functions 𝑥𝑖 = 𝑌𝑖 + 𝑐𝑖 . Here, 𝑌𝑖 represents a random variable drawn from a
ℎ 1 . . . ℎ𝑎 , and increments each 𝐵 [ℎ𝑖 (𝑧) % 𝑚] by ℓ1 /𝑎, dividing the Laplace distribution with parameters (0, ℓ𝜖1 ), and 𝑐𝑖 represents the
sensitivity budget evenly across the buckets. Thus, each buyer will original value contained in the encrypted report.
call the privateAggregation(·) API 𝑎 times to send key–value pairs In cases where there are 𝑛 colluding buyers and the user has
as (𝐵 [ℎ𝑖 (𝑧) % 𝑚], ℓ𝑎1 ) where 𝑖 ∈ 𝑎. When there are collisions, the indeed visited the secondary site, it holds that 𝑐 ≥ 𝑛 · ℓ1 /𝑎. In the
same bucket value is incremented multiple times. case where this user visited once and there are no hash collisions,
To infer around 𝑢 visitors, when the adversary has received 𝑛 · 𝑢 it would be exactly the minimum value 𝑐 = 𝑛 · ℓ1 /𝑎. Collisions only
reports, they notify the secondary site to suspend letting colluding increase the probability of detection, so we ignore than in the rest
buyers win any further auctions for the next hour, and then wait for of this analysis.
up to an hour to receive all reports to account for the random delays In this binary context, the adversary wants to compute the prob-
in sending reports. Modulo race conditions, this minimizes the risk ability that 𝑐𝑖 is non-zero (𝑐𝑖 = 𝑛 · ℓ1 /𝑎) for each observed 𝑥𝑖 :
that the collected reports will include mismatches (different visits 𝑓Laplace (𝑥𝑖 − 𝑐𝑖 )
ℓ1
reported across the 𝑛 colluding buyers). In practice, mismatched 𝑃 (𝑐𝑖 = 𝑛 · | 𝑥𝑖 ) = (1)
𝑎 𝑓Laplace (𝑥𝑖 ) + 𝑓Laplace (𝑥𝑖 − 𝑐𝑖 )
reports would just mean that for some visits fewer than 𝑛 colluding
buyer reports have been received when the aggregation is done, so Here, 𝑓Laplace (𝑥) represents the probability density function of the
an adversary may prefer to just collect reports continuously and Laplace distribution (0, ℓ1 /𝜖), reflecting the probability that the bit
perform aggregation periodically instead of suspending collection at index 𝑥𝑖 has been set in the Bloom filter (so the denominator
for an hour between every aggregation period. For our analysis, we considers the only two cases in this binary setting—either 𝑐𝑖 = 0 or
keep things simple and assume a complete set of reports. 𝑐𝑖 = 𝑛 · ℓ1 /𝑎.
The adversary sends all the reports received to the Aggregation The adversary’s goal is to distinguish between two hypotheses:
Service with a query for bucket keys 0, . . . , 𝑚 − 1. This results in the null hypothesis, 𝐻 0 , is that the user did not visit the tracked
an 𝑚-bit array, 𝐵 report , with the noisy histogram output. The ad- site; the alternative hypothesis 𝐻 1 posits that the user visited the
versary’s goal is to determine which of the candidate users visited tracked site at least once. Given the vector 𝒙, the adversary can
the secondary site during the tracking period. For each target user calculate the likelihood that the original values at all these indices
in the candidate pool, the adversary performs the same hashing are 𝑐 = 𝑛 · ℓ1 /𝑘, denoted as 𝐿(𝐻 1 | 𝒙):
process on each 𝑈 𝐼 𝐷 target , which results in another 𝑚-bit array 𝑖=𝑎
𝐵 target . For each index with a non-zero value in 𝐵 target , the adver-
Ö ℓ1
𝐿(𝐻 1 | 𝒙) = 𝑃 (𝑐 = 𝑛 · | 𝑥𝑖 ) (2)
sary estimates the probability that the noisy value in 𝐵 report at that 𝑖=1
𝑎
index corresponds to a non-zero true value. Then, they take the Finally, the adversary sorts all the users by their likelihood score,
product of all these probabilities to calculate the likelihood that all and accuses the users with highest scores. The adversary has a good
of these bit indices in 𝐵 target are non-zero, as would be the case if estimate of the actual number of visitors to the secondary site, 𝑢,
𝑈 𝐼𝐷 target visited the tracked site. Lastly, the adversary sorts these based on the number of reports received, which is equal to 𝑢 · 𝑛.
likelihood scores and accuses some users with highest scores. The number of accusations can be varied to trade-off between false
Analysis. To evaluate the effectiveness of this attack, we measure positives (invalid accusations) and false negatives (not accusing a
the number of visitors linked and the positive predictive value (PPV) user who did visit the secondary site).
through simulations and explain how we select parameters, such Results. Table 1 shows the smallest number of colluding buyers the
as the fixed domain of bucket keys 𝑚 to maximize detection with adversary needs to control to achieve a PPV over 0.99 with respect to
high PPV. The false positive rate for a standard Bloom filter with different privacy loss budget 𝜖 and the number of accusations. In the
large 𝑚 and small 𝑎 is extremely close to the theoretical bound simulations, we randomly select 10,000 users to visit the secondary
(1 − (1 − 𝑚1 )𝑎𝑢 )𝑎 [5], where 𝑚 is the length of Bloom filter, 𝑎 is website from a candidate pool of one million users who visited the
the number of hash functions, and 𝑢 is the number of elements primary site. We compute the average PPV of the attack across five
stored in the filter. PrAu limits the number of contributions in a simulations with respect to different numbers of accusations with
single report in the reportWin(·) function to 20 [49], so the number varying numbers of colluding buyers.
of hash functions can be up to 𝑎 = 20 which is the value we use. While the value of 𝜖 has not yet been determined in PrAu, the
We analyze the case where 𝑢 = 10, 000, which means the adversary currently available Aggregation Service for the Private Aggregation
aims to track 10,000 users who visit the tracked site at least once API lets developers select an 𝜖 up to 64, with a default value 𝜖 = 10
during each surveillance period. To minimize the (non-noised) false [37]. The number of colluding buyers needed for high confidence
positive rate to 0.01% with 𝑎 = 20 and 𝑢 = 10, 000, the adversary accusations scales up as the value of 𝜖 decreases or the number of
uses a Bloom filter with 𝑚 = 201, 000 bits. accusation increases.
900
Evaluating Google’s Protected Audience Protocol Proceedings on Privacy Enhancing Technologies

Number of Accusations: 1000 5000 10,000 by the adversary’s prediction algorithm when the adversary con-
trols 20 buyers for different size candidate pools. The FPR of the
𝜖=1 40.8 ± 0.2 76.0 ± 1.6 194.6 ± 4.6
attack remains very close to 0 (always below 0.00001) when the
𝜖=3 13.6 ± 0.6 25.2 ± 0.9 67.8 ± 4.6
adversary only makes 100 accusations regardless the candidate pool
𝜖=5 8.8 ± 0.2 15.4 ± 0.6 39.2 ± 1.4
size up to one million for both 𝜖 = 1 and 𝜖 = 10. The FPR becomes
𝜖=7 6.4 ± 0.2 11.6 ± 0.6 30.4 ± 4.2
unacceptably high for all but the most ruthless accuser at 𝜖 = 1 once
𝜖 = 10 5.0 ± 0.4 8.4 ± 0.2 20.6 ± 3.0
the number of accusations exceeds a few hundred, indicating the
Table 1: Number of colluding buyers needed to achieve above need for more than 20 colluding buyer sites for a high confidence
0.99 PPV. For each privacy loss budget 𝜖 (up to the default value large-scale surveillance attack.
of 𝜖 = 10) and the number of accusations, the result in each cell
is the number of colluding buyer sites needed to exceed 0.99 PPV,
5 CIRCUMVENTING K-ANONYMITY
averaged across five simulations. For all cases, there are 10,000 users
who visit the secondary site out of 1M candidates. In the previous section, our attacks in Scenarios 2 and 3 assume the
adversary creates a user-specific interest group by including the
𝑈 𝐼𝐷 in the interest group name, and that the seller can extract the
𝑈 𝐼𝐷 in the interest group name and convey it to colluding buyers
when generating encrypted report. The 𝑘-anonymity checks in PrAu
0.0010
are designed to prevent tracking using user-specific interest groups.
pool size=100K (random guess)
pool size=500K (random guess)
Recall from Section 2.6 that there are two types of 𝑘-anonymity
0.0009
pool size=1M (random guess) checks. The first check excludes the interest group name when
pool size=100K (ε=1)
0.0008 pool size=500K (ε=1) determining ad eligibility for auction wins, thwarting attempts
pool size=1M (ε=1)
0.0007 pool size=100K (ε=10)
to track users through unique creative URLs. The second check,
pool size=500K (ε=10) building upon the first, includes the interest group name in its
0.0006 pool size=1M (ε=10)
assessment to decide if the name can be disclosed during report
FPR

0.0005
generation, thus preventing re-identification of users via interest
0.0004 group names in auction reports. The attack can easily pass the
0.0003 first 𝑘-anonymity check by having 𝑘 users visit the primary site.
However, since the interest group name is specific to each user, the
0.0002
second 𝑘-anonymity check will fail, blocking the interest group
0.0001
name from being visible to the seller worklet in generating an
0.0000 auction report.
100 101 102 103 104
Number of Accusations
In this section we show that the design of the 𝑘-anonymity check
in PrAu is ineffective, and the attacks can easily be adapted to main-
Figure 3: False positive rate as number of accusations varies. tain tracking even when the 𝑘-anonymity check is implemented.
Results for setting where adversary controls 20 buyers to predict We show two approaches to obtain 𝑈 𝐼𝐷 during reporting time de-
10,000 users’ presence on the tracked site out of different candidate spite the 𝑘-anonymity check: controlling multiple Google accounts
pools with the default and a reduced privacy loss budget. Results and employing covert channels.
shown are the average over 5 simulation runs. The variance is
shown through the shading around the averaged line, where it 5.1 Controlling Multiple Google Accounts
ranges from 0 to 0.0001. The most intuitive way to bypass the 𝑘-anonymity check is to create
a group of fake users and associate them with the same interest
group as each targeted user.
With the default privacy budget of 𝜖 = 10, privacy quickly erodes. To mitigate this type of attack, Google limits the number of Join(·)
With a candidate pool of 1 million users, the adversary only needs requests a user can perform, even if they control many browser
5 ± 0.4 colluding buyers to confidently accuse 1,000 users out of identifiers, by requiring a one-time-use Private State Token [50]
10,000 users who visited the tracked site (all results are averages and for each Join(·) request. Currently, Google only provides a Private
variances over 5 simulations). If the adversary wants to make 10,000 State Token in response to requests from an authenticated Google
accusations, with 20.6 ± 3.0 colluding buyers, the adversary can user, and limits the number of tokens each user may obtain. Google
on average identify 9913.4 ± 1.6 visitors out of 10,000 true visitors employs a Privacy Pass protocol [8] to issue and redeem these
(with 86.6 ± 1.6 users falsely linked). Even with a lower privacy loss tokens to prevent them from being tied back to Google accounts.
budgets of 𝜖 = 1, the simulated averaged PPV in the prediction of While it is relatively easy to create Google accounts and control
this attack exceeds 99 percent over 10,000 accusations once there multiple browser identifiers, this attack has limited scalability, as
are over 200 colluding buyers (194.6 ± 4.6 in the simulations). This the number of Join(·) requests is limited to the number of Google
means the adversary can on average identify around 9906 visitors accounts controlled by the adversary times the number of Private
out of 10,000 true visitors with 94 false accusations. State Tokens Google issues to each account for each time period.
Figure 3 shows the relationship between the selection of the Assume Google issues 𝑡 Private State Tokens to each account, in
number of accusations and the False Positive Rate (FPR) achieved order to track 𝑢 users, the adversary would need to control at least
901
Proceedings on Privacy Enhancing Technologies Evaluating Google’s Protected Audience Protocol

𝑢 · 𝑘 Google accounts, assuming they all get a unique browser stochastic rounding in the browser to limit the precision to an 8-bit
𝑡
identifier. exponent and 8-bit mantissa. However, this still leaves room for a
32-bit information channel, 16 bits in each the bid and score, be-
tween the buyer’s code and the seller’s code. Suppose each user is
5.2 Employing Covert Channels assigned a 30-bit 𝑈 𝐼𝐷 in the interest group name. When generating
The more scalable way to circumvent the 𝑘-anonymity check is the bid, the buyer converts the first 15 bits of 𝑈 𝐼𝐷 to floating point
to use covert channels to re-identify the individual 𝑈 𝐼𝐷 without number as a positive bid value to fit within the precision available,
accessing interest group name during the report generation phase puts the whole 30-bit 𝑈 𝐼𝐷 in the ad description field, and returns
since the 𝑈 𝐼 𝐷-specific interest group name will be hidden by the them along with other fields to the browser (Step 1 and 2, Figure 4).
browser. Fortunately (for the attacker, that is), the PrAu protocol When the seller’s code receives the bid, it extracts the 𝑈 𝐼 𝐷 from
offers several potential covert channels to use for this. Figure 4 ad description, converts the latter 15-bits of the 𝑈 𝐼𝐷 to a floating
shows the auction process within the browser and illustrates two point number encoding, and returns this positive value as score
potential covert channels that could be used by the buyer to convey to the browser (Step 3 and 4, Figure 4). For all the bids from other
the 𝑈 𝐼 𝐷 to the seller during the auction, as the buyer has full access buyers, the seller simply returns a negative score so that the score
to the interest group object when generating a bid. By using covert that encodes the 𝑈 𝐼𝐷 is guaranteed to be the highest score and win
channels, the seller can extract the 𝑈 𝐼𝐷 in the ad creative URL or the auction. Then, during reporting time (Step 5 and 6, Figure 4),
reconstruct the 𝑈 𝐼 𝐷 through bid and score values after the failed 𝑘- the seller can reconstruct the 𝑈 𝐼𝐷 by converting the winning bid
anonymity check hides the 𝑈 𝐼𝐷 in the interest group name during and score back to two 15-bit representations and concatenate them
reporting time (Step 5, Figure 4). The attributes with arrows are together to form the 30-bit 𝑈 𝐼𝐷, sufficient for uniquely tracking up
inputs and outputs of pre-defined worklet functions. We discuss to 230 (over 1 billion) distinct users.
two available covert channels below—each is sufficient by itself to
reconstruct the full 𝑈 𝐼𝐷, but they could also be combined if the
amount of information available through each channel were to be
limited by mitigations. 6 COUNTERMEASURES
Based on our analysis, there are two types of potential counter-
Ad creative URLs. The 𝑘-anonymity check is designed to prevent
measures to mitigate the linking attacks. We note, however, that
a unique creative URL from winning an auction since the winning
given the myriad opportunities available for adversaries to obtain
creative URL will be available to the seller during report generation
information through the basic in-browser auction and reporting
phase. However, a single interest group may contain multiple ads
functionalities, it is difficult to have high confidence that any set of
and the buyer’s code chooses which ad to bid on during the auction.
countermeasures, short of reconsidering the design and drastically
This means an adversary could strategically distribute an ad tailored
limiting available communication channels, would be sufficient to
for one user among the ad inventory of another user’s interest
eliminate tracking opportunities.
group, thereby undermining the 𝑘-anonymity threshold. Assuming
an interest group can hold 𝐴 distinct creative URLs (PrAu does not Limit arbitrary code execution within worklets. To re-identify
appear to place any limit on 𝐴; we have tested up to 𝐴 = 200), the a user with the 𝑘-anonymity check in place, the adversary exploits
adversary could segment the total number of tracked users 𝑢 by worklet functions to execute arbitrary code during auctions, using
𝐴, allocating a set of user-specific ads to each segment of users covert channels to exchange information between buyers and sellers
within their interest group. Thus, each user’s interest group has a via function outputs. A potential mitigation strategy would impose
distinct name that includes the 𝑈 𝐼𝐷 and a set of 𝐴 ads, and these stricter controls on the format and content of these outputs. For
ads embed unique IDs within their URLs, one of which matches example, rather than allowing buyers to transmit any ad metadata
the 𝑈 𝐼 𝐷. Given that 𝐴 ≥ 𝑘, the 𝑘-anonymity check at auction to sellers during auctions, browsers could restrict communications
phase will be successful. When generating the bid, the buyer can to a selection of predefined categorical attributes. Similarly, instead
choose to bid exclusively on the ad whose 𝑈 𝐼𝐷 matches that of the of permitting sellers to assign arbitrary scores to ads, browsers
interest group name, and the colluding seller will let this ad win could enable them to evaluate bids and ads using a fixed set of stan-
the auction later. In this way, the seller can directly obtain the 𝑈 𝐼𝐷 dardized rankings. Such measures would complicate adversaries’
in the winning ad creative URL during reporting time and send it efforts to conduct widespread surveillance by limiting the possible
to the buyer (Step 5 and 6, Figure 4). combinations of transmitted values. However, it remains uncer-
tain how these restrictions might affect advertisers, particularly
Bid and score values. As shown in Figure 4 Step 5, the winning
regarding their bidding strategies which may be designed to take
bid and score values are revealed to the seller for use in gener-
advantage of any information available to a bidder.
ating reports. Since the buyer and seller are colluding, the buyer
can generate any positive floating-point number as the bid value, Different aggregate reporting mechanism. In the proposed at-
embed information about the 𝑈 𝐼𝐷 in these bits, and still secure tack, the adversary takes advantage of the expectation linearity
the auction win. The seller can also encode information within within noise addition mechanisms used by the Private Aggregation
the floating-point score value, as long as the score assigned to the Service. To counteract this, PrAu could implement an alternative
colluding buyer’s bid remains the highest among all bids, ensuring method for adding noise that offers increased resistance to such
the buyer’s victory in the auction. To avoid these numbers exfil- exploits. One potential approach is to utilize local differential pri-
trating information from the interest group, PrAu plans to perform vacy (LDP) [14], which introduces noise at the individual data point
902
Evaluating Google’s Protected Audience Protocol Proceedings on Privacy Enhancing Technologies

BROWSER

Buyer's Worklet Browser's Internal Code Seller's Worklet

GenerateBid:
Extract UID from interest 1. send interestGroup
group name and put it in and auctionConfig objects
ad description. Select the
2. send ad description,
creative URL that contains
UID. Encode the first 15-bit bid value, and creative URL
of UID in bid value.
Perform k-anonymity check that
excludes IG name to determine
ad eligibility for winning.
ScoreAd:
3. send values returned
Extract UID from ad
from buyer's worklet
description. Encode
with other auction information
the last 15-bit UID in
4. send score value score value.

Select the ad with highest score

and display it. Perform k-
anonymity check that includes
IG name to determine whether to
send IG name in the next step.
5. send bid, score, and ReportResult:
creative URL of the winner ad Extract UID from the
ReportWin: creative URL.
Extract UID from seller's Reconstruct UID from
message. Generate 6. send message to bid and score value.
7. send message returned from Send UID as message
encrypted report based on the winning buyer
seller's worklet with other to the winning buyer.
UID. winning ad's information

Figure 4: Using Covert Channels to Reconstruct 𝑈 𝐼𝐷 during in-Browser Auctions. Red text represents the way to extract 𝑈 𝐼 𝐷 in
creative URL. Blue text represents the way to reconstruct 𝑈 𝐼𝐷 through bid value and score value.

level before the aggregation process. As each piece of data is in- the CMA and the Information Commissioner’s Office (ICO), blend-
dependently obscured, it will be more difficult for an adversary to ing expertise from privacy and competition regulatory perspectives.
neutralize the noise by aggregating the data. This method ensures Google has responded by offering commitments designed to ensure
that the added noise remains effective in preserving privacy, even that the implementation of the Privacy Sandbox proposals is trans-
when data is combined. The amount of information available to parent, equitable, and does not confer an unfair data advantage to
an adversary could also be limited by substantially reducing the Google’s own advertising services [2]. These commitments include
number of available bucket keys (currently 2128 ) and the maximum engaging in open dialogue with the CMA and the industry, ensuring
value sensitivity (which effectively reduces 𝜖 if it is still set based no preferential treatment for Google’s products, and not using al-
on the original value). Any limits on the information available in a ternative identifiers or Chrome browsing histories for ad targeting.
report, though, reduce the potential value of reports to advertisers. This situation underscores the complex interplay between privacy
and competitive dynamics in digital markets. The CMA’s public
consultation process on these commitments represents a critical
step in addressing these concerns, with the potential to set legally
7 DISCUSSION binding conditions for the design and operation of PrAu and other
Beyond assessing the privacy attributes in the design of PrAu, it components of the Privacy Sandbox.
is essential to contextualize its role within the broader advertising
ecosystem. Our discussion extends to how PrAu influences com- Trusted Third Parties. In PrAu, several servers needs to be trusted
petitive dynamics and the role of trusted third parties within the to prevent information leakage during the auction. To limit expo-
Privacy Sandbox framework. sure through these trusted servers, the service must run in a TEE on
an approved cloud platform and the code implementing the trusted
Market Dynamics. While we focus on privacy aspects of PrAu, server must be approved before deployment. For example, these ser-
there is also a concern among competing ad networks that the vices must not perform event-level logging or log data that would
design of the protocol could diminish their ability to compete ef- potentially identify users such as IP addresses and timestamps, and
fectively. They fear losing access to valuable information that is the auditor must ensure that the set of keys and the way they are
crucial for targeting and measuring ads, which might consolidate updated cannot be used for user tracking or profiling purposes.
Google’s dominance in the online advertising space. The UK’s Com- At least initially, it seems that the only candidate for this auditor
petition and Markets Authority (CMA) has taken an active role in would be Google, although none of the available Privacy Sandbox
scrutinizing the Privacy Sandbox proposals, launching a formal documents acknowledge this.
investigation to understand their implications for competition and
consumer welfare [7]. This process involves collaboration between
903
Proceedings on Privacy Enhancing Technologies Evaluating Google’s Protected Audience Protocol

In addition, the full implementation of 𝑘-anonymity server re- final version of the Privacy Sandbox are clearly defined and its
quires a trusted third-party company that is not affiliated with implementation achieves them as well as possible.
Google to operate a relay server and will not exchange request data
with them. The need for an additional trusted party poses inherent AVAILABILITY
privacy risks, since this server is collecting IP addresses from the Open-source code for producing our simulation results and corre-
browsers submitting these requests, and can also manipulate which sponding graphs (Figure 2, Table 1, and Figure 3) is available as
messages it relays and introduce other timing channels. It is unclear https://github.com/Elena6918/PrAu-Simulation.
from the PrAu documentation what business model would be used
to support the independent relay operators in the protocol. Future ACKNOWLEDGEMENTS
research work might examine the feasibility of this type of business This work was partially supported by a grants from the National
models and measure their effectiveness. Science Foundation (#1804603 and #2229876). The views and con-
Finally, the code running in the web browser that manages the clusions expressed here are solely those of the authors and do not
ad auction, including setting up the worklets for the buyer and necessarily represent those of any other organization or institution.
seller code, implementing the 𝑘-anonymity checks, and controlling
all the information passing between the worklets and external REFERENCES
servers, is also a critical trusted component of the system. Although [1] Jonathan Bannet, David W Price, Algis Rudys, Justin Singer, and Dan S Wallach.
it is possible that the protocol will be standardize to the point 2004. Hack-a-vote: Security issues with electronic voting systems. IEEE Security
where it can be implemented in independent browsers, current & Privacy 2 (2004), 32–37.
[2] Oliver Bethell. 2021. Our commitments for the Privacy Sandbox.
implementation are only in Google’s Chrome browser. https://blog.google/around-the-globe/google-europe/our-commitments-
privacy-sandbox/.
Responsible Disclosure. Since our results concern privacy vulner- [3] Yohan Beugin and Patrick McDaniel. 2024. Interest-disclosing Mechanisms for
abilities in a proposed system that is not yet deployed, there is no Advertising are Privacy-Exposing (not Preserving). In Proceedings on Privacy
Enhancing Technologies (PoPETs).
immediate disclosure risk—the vulnerabilities we discuss are only [4] Burton H Bloom. 1970. Space/time trade-offs in hash coding with allowable
risks in a future world where third-party cookies are blocked so errors. Commun. ACM 13 (1970), 422–426.
the current tracking they enable is no longer possible. The goal of [5] Prosenjit Bose, Hua Guo, Evangelos Kranakis, Anil Maheshwari, Pat Morin, Jason
Morrison, Michiel Smid, and Yihui Tang. 2008. On the false-positive rate of Bloom
PrAu is to support targeted advertising in a world where third-party filters. Inform. Process. Lett. 108 (2008), 210–213.
cookies are no longer available and the essential privacy property [6] Anthony Chavez. 2022. Expanding testing for the Privacy Sandbox for the Web.
PrAu intended to provide is unlinkability of requests, and the focus https://blog.google/products/chrome/update-testing-privacy-sandbox-web/.
[7] Competition and Markets Authority. 2024. Investigation into Google’s ‘Privacy
of our work is analyzing how well the proposed design meets that Sandbox’ browser changes. https://www.gov.uk/cma-cases/investigation-into-
privacy goal in a future where third-party cookies are no longer googles-privacy-sandbox-browser-changes.
[8] Alex Davidson, Ian Goldberg, Nick Sullivan, George Tankersley, and Filippo
supported. Nevertheless, we did share a version of this paper with Valsorda. 2018. Privacy Pass: Bypassing Internet Challenges Anonymously.. In
the team at Google developing PrAu. They expressed appreciation Proceedings on Privacy Enhancing Technologies (PoPETs).
for our work and did not raise any technical objections to our de- [9] Zeyu Ding, Yuxin Wang, Guanhong Wang, Danfeng Zhang, and Daniel Kifer.
2018. Detecting violations of differential privacy. In Proceedings of the 2018 ACM
scription or conclusions, but have not yet shared with us any plans SIGSAC Conference on Computer and Communications Security.
to change the PrAu design to address the issues we have identified. [10] Dun & Bradstreet. 2024. Get a D-U-N-S Number. https://www.dnb.com/duns/get-
a-duns.html.
[11] Sam Dutton. 2021. FLoC. https://developer.chrome.com/docs/privacy-
8 CONCLUSION sandbox/floc/.
[12] Sam Dutton and Kevin Lee. 2022. Protected Audience API. https://developer.ch
Google’s Privacy Sandbox initiative aims to provide a balanced rome.com/docs/privacy-sandbox/fledge/.
solution to address privacy concerns associated with web tracking [13] Sam Dutton and Kevin Lee. 2022. Protected Audience API: developer guide.
https://developer.chrome.com/docs/privacy-sandbox/protected-audience-api/.
while supporting the business of targeted advertising. The core idea [14] Cynthia Dwork. 2008. Differential privacy: A survey of results. In International
behind the Privacy Sandbox is to create a set of APIs that enable conference on theory and applications of models of computation.
targeted advertising through in-browser auctions. [15] Cynthia Dwork, Aaron Roth, et al. 2014. The algorithmic foundations of differ-
ential privacy. Foundations and Trends® in Theoretical Computer Science 9 (2014),
Overall, the Privacy Sandbox represents a step forward in balanc- 211–407.
ing privacy concerns with the needs of advertisers. Google deserves [16] Federal Trade Commission. 2012. Google Will Pay $22.5 Million to Settle FTC
Charges it Misrepresented Privacy Assurances to Users of Apple’s Safari Internet
credit for their relatively transparent process in developing this Browser. https://www.ftc.gov/news-events/news/press-releases/2012/08/google-
initiative, which has involved seeking input from a variety of stake- will-pay-225-million-settle-ftc-charges-it-misrepresented-privacy-assuranc
holders and experts. However, there is still a great deal of uncer- es-users-apples.
[17] Federal Trade Commission. 2023. Lurking Beneath the Surface: Hidden Impacts
tainty surrounding the Privacy Sandbox. While it is already widely of Pixel Tracking. https://www.ftc.gov/policy/advocacy-research/tech-at-
deployed to the general public, essential privacy mechanisms are ftc/2023/03/lurking-beneath-surface-hidden-impacts-pixel-tracking.
not in place. For instance, the auditing process of Trusted Servers [18] Roy Fielding, Jim Gettys, Jeffrey Mogul, Henrik Frystyk, Larry Masinter, Paul
Leach, and Tim Berners-Lee. 1999. RFC2616: Hypertext Transfer Protocol–
has not been determined and event-level clear-text reporting will HTTP/1.1.
be supported until at least 2026, leaving concerns about how the [19] Georgia Franklin. 2023. Developer enrollment for the Privacy Sandbox. https:
//developer.chrome.com/blog/announce-enrollment-privacy-sandbox/.
system will be implemented in its final design and whether it will [20] Vinay Goel. 2021. An updated timeline for Privacy Sandbox milestones. https://
effectively protect user privacy as intended. As such, it is crucial blog.google/products/chrome/updated-timeline-privacy-sandbox-milestones/.
to provide an early analysis of the proposed system. By identify- [21] Vinay Goel. 2022. Get to know the new Topics API for Privacy Sandbox. https:
//blog.google/products/chrome/get-know-new-topics-api-privacy-sandbox/.
ing potential risks and areas for improvement before widespread [22] Google Developers. 2023. K-Anonymity. https://developers.google.com/privacy-
deployment, we hope to ensure that the privacy properties of the sandbox/relevance/protected-audience-api/k-anonymity.
904
Evaluating Google’s Protected Audience Protocol Proceedings on Privacy Enhancing Technologies

[23] Katerina Goseva-Popstojanova and Andrei Perhinschi. 2015. On the capability of [51] Daniel Votipka, Kelsey R Fulton, James Parker, Matthew Hou, Michelle L Mazurek,
static code analysis to detect security vulnerabilities. Information and Software and Michael Hicks. 2020. Understanding security mistakes developers make:
Technology 68 (2015), 18–33. Qualitative analysis from build it, break it, fix it. In USENIX Security Symposium.
[24] Peiwei Hu and Kevin Lee. 2024. Key Value Service Trust Model. https://github.c [52] Web Platform Incubator Community Group. 2022. Extended Private Aggregation
om/privacysandbox/protected-auction-services-docs/blob/main/key_value_ser Reporting in FLEDGE. https://github.com/WICG/turtledove/blob/main/FLEDG
vice_trust_model.md. E_extended_PA_reporting.md.
[25] Nikhil Jha, Martino Trevisan, Emilio Leonardi, and Marco Mellia. [53] Web Platform Incubator Community Group. 2022. TURTLEDOVE. https://gith
2023. On the Robustness of Topics API to a Re-Identification Attack. ub.com/WICG/turtledove.
https://arxiv.org/abs/2306.05094. [54] John Wilander. 2020. Full Third-Party Cookie Blocking and More. https://webkit
[26] Jiankai Jin, Eleanor McMurtry, Benjamin IP Rubinstein, and Olga Ohrimenko. .org/blog/10218/full-third-party-cookie-blocking-and-more/.
2022. Are We There Yet? Timing and Floating-Point Attacks on Differential
Privacy Systems. In IEEE Symposium on Security and Privacy.
[27] Evgeny Karpukhin, Vadim Sharmaev, and Anton Propp. 2022. DE-
ANONYMIZATION OF THE USER OF WEB RESOURCE WITH BROWSER FIN-
GERPRINT TECHNOLOGY. Journal of Theoretical and Applied Information
Technology 100, 14 (2022).
[28] Daniel Kifer, Solomon Messing, Aaron Roth, Abhradeep Thakurta, and Danfeng
Zhang. 2020. Guidelines for Implementing and Auditing Differentially Private
Systems. https://arxiv.org/abs/2002.04049.
[29] David M Kristol. 2001. HTTP Cookies: Standards, privacy, and politics. ACM
Transactions on Internet Technology (TOIT) 1 (2001), 151–198.
[30] Timothy Libert and Rasmus Kleis Nielsen. 2018. Third-party web content on EU
news sites: Potential challenges and paths to privacy improvement. https://timl
ibert.me/pdf/Libert_Nielsen-2018-Third_Party_Content_EU_News_GDPR.pdf.
[31] Jonathan R Mayer and John C Mitchell. 2012. Third-party web tracking: Policy
and technology. In 2012 IEEE symposium on security and privacy.
[32] Rowan Merewood. 2022. Building a more private web: A path towards making
third party cookies obsolete. https://blog.chromium.org/2020/01/building-more-
private-web-path-towards.html.
[33] Vikas Mishra, Pierre Laperdrix, Antoine Vastel, Walter Rudametkin, Romain
Rouvoy, and Martin Lopatka. 2020. Don’t count me out: On the relevance of IP
address in the tracking ecosystem. In Proceedings of The Web Conference 2020.
[34] Fahad Muhammad. 2024. What is Remarketing? https://instapage.com/what-is-
remarketing.
[35] Nick Nguyen. 2018. Changing Our Approach to Anti-tracking. https://blog.moz
illa.org/futurereleases/2018/08/30/changing-our-approach-to-anti-tracking/.
[36] James Parker, Michael Hicks, Andrew Ruef, Michelle L. Mazurek, Dave Levin,
Daniel Votipka, Piotr Mardziel, and Kelsey R. Fulton. 2020. Build It, Break It, Fix
It: Contesting Secure Development. ACM Trans. Priv. Secur. 23 (2020).
[37] Privacy Sandbox Team. 2023. Testing locally using Local Testing Tool. https:
//github.com/privacysandbox/aggregation- service/blob/main/docs/local-
testing-tool.md.
[38] Deepak Ravichandran and Nitish Korula. 2019. Effect of disabling third-party
cookies on publisher revenue. https://services.google.com/fh/files/misc/disablin
g_third-party_cookies_publisher_revenue.pdf.
[39] Joel Reardon, Álvaro Feal, Primal Wijesekera, Amit Elazari Bar On, Narseo Vallina-
Rodriguez, and Serge Egelman. 2019. Fifty ways to leak your data: An exploration
of apps’ circumvention of the Android permissions system. In USENIX Security
Symposium.
[40] Mohamed Sabt, Mohammed Achemlal, and Abdelmadjid Bouabdallah. 2015.
Trusted execution environment: what it is, and what it is not. In 2015 IEEE
Trustcom/BigDataSE/Ispa.
[41] Pierangela Samarati and Latanya Sweeney. 1998. Protecting privacy when dis-
closing information: k-anonymity and its enforcement through generalization and
suppression. Technical Report.
[42] Justin Schuh. 2019. Improving privacy and security on the web. https://blog.goo
gle/products/chrome/update-testing-privacy-sandbox-web/.
[43] Justin Schuh. 2020. Test the Privacy Sandbox ads relevance and measurement
APIs. https://developer.chrome.com/blog/privacy-sandbox-unified-origin-trial/.
[44] Shivani Sharma. 2022. Network side channel. https://github.com/WICG/fenced-
frame/blob/master/explainer/network_side_channel.md.
[45] Dominic Farolino Shivani Sharma. 2022. Fenced Frames. https://github.com/W
ICG/fenced-frame.
[46] Tristram Southey. 2023. Protected Audience API: Our new name for FLEDGE.
https://privacysandbox.com/intl/en_us/news/protected-audience-api-our-
new-name-for-fledge.
[47] The Privacy Sandbox. 2022. The Privacy Sandbox Timeline for the Web. https:
//privacysandbox.com/intl/en_us/open-web/.
[48] Florian Tramèr, Andreas Terzis, Thomas Steinke, Shuang Song, Matthew Jagielski,
and Nicholas Carlini. 2022. Debugging Differential Privacy: A Case Study for
Privacy Auditing. https://arxiv.org/abs/2202.12219.
[49] Alex Turner. 2023. Private Aggregation API Explainer. https://github.com/patcg-
individual-drafts/private-aggregation-api#contributions-limit.
[50] Steven Valdez, David Cleve, Callum May, Charlie Harrison, Sam Dutton, Shigeki
Ohtsu, Mike Taylor, and Eric Trouton. 2019. Private State Token API Explainer.
https://github.com/WICG/trust-token-api/blob/main/README.md.

905
Proceedings on Privacy Enhancing Technologies Evaluating Google’s Protected Audience Protocol

A THE API CALLING SEQUENCE IN FOT ∫ ∞Case 1A. 𝑌 𝑗 > 0. To apply the midpoint rule to approximate
𝜖 𝑒 −𝜖𝑌 𝑗 · (1 − 1 𝑒 −𝜖 (𝑛+𝑌 𝑗 ) )𝑢−1𝑑𝑌 , we first discretize the integral
Figure 5 shows the current design of PrAu in the FOT . 0 2 2 𝑗
by dividing the range [0, ∞) into 𝐿 subintervals of equal width. Let
Buyer Server Browser Seller Server Δ𝑥 be the width of each subinterval: Δ𝑥 = ∞−0 𝐿 , and the midpoints
(2𝑖−1)Δ𝑥
1. visit
of these subintervals are denoted as 𝑥𝑖 = 2 , where 𝑖 =
2. joinAdInterestGroup
1, 2, . . . , 𝐿. For simplicity, let Δ𝑥 = 1, then for each subinterval, we
(interestGroup, time) 3. visit have 𝑓 (𝑥𝑖 ) = 𝜖2 𝑒 −𝜖𝑥𝑖 (1 − 12 𝑒 −𝜖 (𝑛+𝑥𝑖 ) )𝑢−1 .
4. runAdAuction Lastly, we sum up the approximations for all subintervals to
(auctionConfig)
obtain an approximation for the entire integral:
∫ ∞
1 −𝜖 (𝑛+𝑌𝑗 ) 𝑢−1
 
𝜖 −𝜖𝑌𝑗
5a. send bidding 5. Running Auctions with 5c. send scoring 1𝐴 = 𝑒 · 1− 𝑒 𝑑𝑌 𝑗 (3)
signals keys Bidding URL in Bidding signal keys 0 2 2
Worklet and Decision
5b. send bidding URL in Auction Worklet
5d. send scoring
∞
signal values
∑︁ 𝜖 −𝜖 (𝑖− 1 ) 1 −𝜖 (𝑛+𝑖− 1 )) 𝑢−1
signal values
≈ 𝑒 2 · (1 − 𝑒 2 ) (4)
2 2
6. Report Auction 𝑖=1
Outcome with Bidding
6b. sendReportTo(url) 6a. sendReportTo(url)
Worklet and Auction Case 1B. 𝑌 𝑗 < 0. To apply the Midpoint Rule to approximate
Worklet ∫0 𝜖
−𝑛 2
𝑒 −𝜖 |𝑌𝑗 | · (1 − 12 𝑒 −𝜖 (𝑛+𝑌𝑗 ) )𝑢−1𝑑𝑌 𝑗 , we first discretize the in-
tegral by dividing the range [−𝑛, 0] into 𝑛 subintervals of equal
Figure 5: FOT of PrAu with API Calling Sequence among width Δ𝑥 = 1. Then, the midpoints of these subintervals can be
Servers and the Browser. For simplicity, we show a single seller (2𝑖−1)
expressed as 𝑥𝑖 = −𝑛 + 2 , where 𝑖 = 1, 2, . . . , 𝑛. Thus, for each
and buyer (who is also the winner of the auction), although there
would typically be many buyers and sellers. subinterval, we have 𝑓 (𝑥𝑖 ) = 𝜖2 𝑒 −𝜖𝑥𝑖 (1 − 21 𝑒 −𝜖 (𝑛+𝑥𝑖 ) )𝑢−1 .
Lastly, we sum up the approximations for all subintervals to
obtain an approximation for the entire integral:
∫ 0
B PROOF OF THEOREM 4.1 1𝐵 =
𝜖 −𝜖 |𝑌𝑗 |
𝑒
1
· (1 − 𝑒 −𝜖 (𝑛+𝑌𝑗 ) )𝑢−1𝑑𝑌 𝑗 (5)
As all colluding buyers reports full ℓ1 contribution budget when −𝑛 2 2
𝑛
a target user visits the seller site, we can simplify the analysis by ∑︁ 𝜖 𝜖 (−𝑛+𝑖− 1 )) 1 1
≈ 𝑒 2 · (1 − 𝑒 −𝜖 (𝑖− 2 )) )𝑢−1 (6)
dividing ℓ1 in all terms. 2 2
𝑖=1
The adversary implements a simple prediction algorithm: select
the prediction 𝑗ˆ as the index of the value in 𝒙 with the highest value. Case 2: 𝑛 + 𝑌 𝑗 < 0
Then, the expected accuracy of this algorithm can be defined as a Case 2A. 𝑌 𝑗 > 0. Given 𝑛 > 0 and 𝑌 𝑗 > 0, it is impossible that
function 𝐸 (𝜖, 𝑢, 𝑛), which is the probability 𝑃 (𝑥 𝑗 > 𝑥𝑖 , ∀𝑖 ≠ 𝑗). This 𝑌 𝑗 > 0, and thus Case 2A is invalid.
Î
can be further written as 𝑖 ∈ [𝑢 ]−𝑗 𝑃 (𝑌𝑖 < 𝑛 + 𝑌 𝑗 ). Case 2B. 𝑌 𝑗 < 0
Recall the probability density function (PDF) of 𝑌 is 𝑓𝐿𝑎𝑝𝑙𝑎𝑐𝑒 (𝑌 ) = ∫ −𝑛
1 𝑒 −𝜖 |𝑌 | , and the cumulative density function (CDF) is 𝜖 −𝜖 |𝑌𝑗 | 1 𝜖 (𝑛+𝑌𝑗 ) 𝑢−1
2 2𝐵 = 𝑒 ·( 𝑒 ) 𝑑𝑌 𝑗 (7)
( −∞ 2 2
1 𝑒 𝜖𝑌 , ∫ −𝑛
if 𝑌 < 0 𝜖 𝜖𝑌𝑗 1
𝐹𝐿𝑎𝑝𝑙𝑎𝑐𝑒 (𝑌 ) = 2 1 −𝜖𝑌 = 𝑒 · 𝑢−1 𝑒 𝜖 (𝑢−1) (𝑛+𝑌𝑗 ) 𝑑𝑌 𝑗 (8)
1 − 2𝑒 if 𝑌 ≥ 0 −∞ 2 2
𝜖 1
Since each 𝑌𝑖 is drawn independently from Laplace(0, 𝜖1 ), we can = 𝑢 · [ 𝑒 𝜖𝑢𝑌𝑗 +𝜖 (𝑢−1)𝑛 ] −𝑛 −∞ (9)
Î 2 𝜖𝑢
represent 𝑖 ∈ [𝑢 ]−𝑗 𝑃 (𝑌𝑖 < 𝑛 + 𝑌 𝑗 ) as 1
∫ ∫ ∞ = 𝑢 𝑒 −𝜖𝑛 (10)
𝐹𝐿𝑎𝑝𝑙𝑎𝑐𝑒 (𝑛+𝑌 𝑗 )𝑢−1𝑑𝑌 𝑗 = 𝑓𝐿𝑎𝑝𝑙𝑎𝑐𝑒 (𝑌 𝑗 )·𝐹𝐿𝑎𝑝𝑙𝑎𝑐𝑒 (𝑛+𝑌 𝑗 )𝑢−1𝑑𝑌 𝑗 2 ·𝑢
𝑌𝑗 −∞ Lastly, after summing up all 4 cases, we can evaluate the integral
Since 𝐹𝐿𝑎𝑝𝑙𝑎𝑐𝑒 (𝑛 + 𝑌 𝑗 ) has two different forms depending on the as the following form:
sign of 𝑌 𝑗 + 𝑛 and 𝑓𝐿𝑎𝑝𝑙𝑎𝑐𝑒 (𝑌 𝑗 ), we need to split it into two cases ∞
∑︁ 𝜖 −𝜖 (𝑖− 1 ) 1 −𝜖 (𝑛+𝑖− 1 )) 𝑢−1
𝐴𝑐𝑐𝑢𝑟𝑎𝑐𝑦 = 𝑒 2 · (1 − 𝑒 2 ) Case 1A
for calculation: 2 2
𝑖=1
Case 1: 𝑛 + 𝑌 𝑗 ≥ 0 (11)
To solve the following two integrals, we use the midpoint rule
𝑛
method to approximate the value. This divides the interval [𝑎, 𝑏] ∑︁ 𝜖 𝜖 (−𝑛+𝑖− 1 )) 1 1
+ 𝑒 2 · (1 − 𝑒 −𝜖 (𝑖− 2 )) )𝑢−1 Case 1B
into 𝑛 subintervals of equal width, denoted by Δ𝑥. The midpoints 2 2
𝑖=1
of these subintervals are denoted as 𝑥𝑖∗ , where 𝑖 = 1, 2, . . . , 𝑛. The (12)
approximation of the integral using the Midpoint Rule is given by: 1
∫ 𝑏 𝑛 + 𝑒 −𝜖𝑛 Case 2B
∑︁ 𝜖 · 𝑢 · 2𝑢
𝑓 (𝑥) 𝑑𝑥 ≈ 𝑓 (𝑥𝑖∗ )𝑌𝑥 (13)
𝑎 𝑖=1
where Δ𝑥 = 𝑏−𝑎 .
𝑛
906