  The ongoing deprecation of third-party cookies by web browser vendors has
sparked the proposal of alternative methods to support more privacy-preserving
personalized advertising on web browsers and applications. The Topics API is
being proposed by Google to provide third-parties with "coarse-grained
advertising topics that the page visitor might currently be interested in". In
this paper, we analyze the re-identification risks for individual Internet
users and the utility provided to advertising companies by the Topics API, i.e.
learning the most popular topics and distinguishing between real and random
topics. We provide theoretical results dependent only on the API parameters
that can be readily applied to evaluate the privacy and utility implications of
future API updates, including novel general upper-bounds that account for
adversaries with access to unknown, arbitrary side information, the value of
the differential privacy parameter $\epsilon$, and experimental results on
real-world data that validate our theoretical model.
