{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T21:38:52Z","timestamp":1775943532499,"version":"3.50.1"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,6,13]],"date-time":"2023-06-13T00:00:00Z","timestamp":1686614400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,6,13]]},"abstract":"<jats:p>Compact user representations (such as embeddings) form the backbone of personalization services. In this work, we present a new theoretical framework to measure re-identification risk in such user representations. Our framework, based on hypothesis testing, formally bounds the probability that an attacker may be able to obtain the identity of a user from their representation. As an application, we show how our framework is general enough to model important real-world applications such as the Chrome's Topics API for interest-based advertising. We complement our theoretical bounds by showing provably good attack algorithms for re-identification that we use to estimate the re-identification risk in the Topics API. We believe this work provides a rigorous and interpretable notion of re-identification risk and a framework to measure it that can be used to inform real-world applications.<\/jats:p>","DOI":"10.1145\/3589294","type":"journal-article","created":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T20:26:45Z","timestamp":1687292805000},"page":"1-26","source":"Crossref","is-referenced-by-count":17,"title":["Measuring Re-identification Risk"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-9812-0177","authenticated-orcid":false,"given":"CJ","family":"Carey","sequence":"first","affiliation":[{"name":"Google, New York, NY, USA"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-1271-307X","authenticated-orcid":false,"given":"Travis","family":"Dick","sequence":"additional","affiliation":[{"name":"Google, New York, NY, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0456-3217","authenticated-orcid":false,"given":"Alessandro","family":"Epasto","sequence":"additional","affiliation":[{"name":"Google, New York, NY, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1934-8747","authenticated-orcid":false,"given":"Adel","family":"Javanmard","sequence":"additional","affiliation":[{"name":"USC and Google, New York, NY, USA"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-7018-3509","authenticated-orcid":false,"given":"Josh","family":"Karlin","sequence":"additional","affiliation":[{"name":"Google, Cambridge, MA, USA"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-4307-8102","authenticated-orcid":false,"given":"Shankar","family":"Kumar","sequence":"additional","affiliation":[{"name":"Google, New York, NY, USA"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-5520-4916","authenticated-orcid":false,"given":"Andres","family":"Mu\u00f1oz Medina","sequence":"additional","affiliation":[{"name":"Google, New York, NY, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6705-5629","authenticated-orcid":false,"given":"Vahab","family":"Mirrokni","sequence":"additional","affiliation":[{"name":"Google, New York, NY, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7823-3061","authenticated-orcid":false,"given":"Gabriel Henrique","family":"Nunes","sequence":"additional","affiliation":[{"name":"UFMG and Google, New York, NY, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0235-1624","authenticated-orcid":false,"given":"Sergei","family":"Vassilvitskii","sequence":"additional","affiliation":[{"name":"Google, New York, NY, USA"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-1136-9538","authenticated-orcid":false,"given":"Peilin","family":"Zhong","sequence":"additional","affiliation":[{"name":"Google, New York, NY, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,6,20]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978318"},{"key":"e_1_2_2_2_1","volume-title":"Proceedings of the International Conference on Database Theory (ICDT","author":"Aggarwal Gagan","year":"2005","unstructured":"Gagan Aggarwal, Tomas Feder, Krishnaram Kenthapadi, Rajeev Motwani, Rina Panigrahy, Dilys Thomas, and An Zhu. 2005. Approximation Algorithms for k-Anonymity, In Proceedings of the International Conference on Database Theory (ICDT 2005). Journal of Privacy Technology (JOPT). http:\/\/ilpubs.stanford.edu:8090\/645\/"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335438"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--319--96131--6"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35326-0_52"},{"key":"e_1_2_2_6_1","volume-title":"Kyung Hyun Cho, and Yoshua Bengio","author":"Bahdanau Dzmitry","year":"2015","unstructured":"Dzmitry Bahdanau, Kyung Hyun Cho, and Yoshua Bengio. 2015. Neural machine translation by jointly learning to align and translate. In ICLR."},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1515\/popets-2018-0033"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2013.50"},{"key":"e_1_2_2_9_1","volume-title":"The Million Song Dataset. In 12th International Society for Music Information Retrieval Conference (ISMIR","author":"Bertin-Mahieux Thierry","year":"2011","unstructured":"Thierry Bertin-Mahieux, Daniel P.W. Ellis, Brian Whitman, and Paul Lamere. 2011. The Million Song Dataset. In 12th International Society for Music Information Retrieval Conference (ISMIR 2011)."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1974.1055254"},{"key":"e_1_2_2_11_1","article-title":"Differentially private empirical risk minimization","volume":"12","author":"Chaudhuri Kamalika","year":"2011","unstructured":"Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. 2011. Differentially private empirical risk minimization. Journal of Machine Learning Research, Vol. 12, 3 (2011).","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.18653\/v1"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1914598117"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3197390"},{"key":"e_1_2_2_15_1","volume-title":"Thomas","author":"Cover Thomas M.","year":"2001","unstructured":"Thomas M. Cover and Joy A. Thomas. 2001. Elements of Information Theory. Wiley."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2019.2939472"},{"key":"e_1_2_2_17_1","volume-title":"5th International Conference, TAMC 2008, Xi'an, China, April 25--29, 2008. Proceedings (Lecture Notes in Computer Science","volume":"19","author":"Dwork Cynthia","year":"2008","unstructured":"Cynthia Dwork. 2008. Differential Privacy: A Survey of Results. In Theory and Applications of Models of Computation, 5th International Conference, TAMC 2008, Xi'an, China, April 25--29, 2008. Proceedings (Lecture Notes in Computer Science, Vol. 4978), Manindra Agrawal, Ding-Zhu Du, Zhenhua Duan, and Angsheng Li (Eds.). Springer, 1--19."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3294052.3322188"},{"key":"e_1_2_2_19_1","volume-title":"Theory of cryptography conference","author":"Dwork Cynthia","unstructured":"Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. 2006. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference. Springer, 265--284."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1881151.1881152"},{"key":"e_1_2_2_21_1","volume-title":"Clustering for Private Interest-based Advertising. In KDD '21: The 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining","author":"Epasto Alessandro","year":"2021","unstructured":"Alessandro Epasto, Andr\u00e9 s Mu n oz Medina, Steven Avery, Yijian Bai, R\u00f3 bert Busa-Fekete, C. J. Carey, Ya Gao, David Guthrie, Subham Ghosh, James Ioannidis, Junyi Jiao, Jakub Lacki, Jason Lee, Arne Mauser, Brian Milch, Vahab S. Mirrokni, Deepak Ravichandran, Wei Shi, Max Spero, Yunting Sun, Umar Syed, Sergei Vassilvitskii, and Shuo Wang. 2021. Clustering for Private Interest-based Advertising. In KDD '21: The 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, Singapore, August 14--18, 2021, Feida Zhu, Beng Chin Ooi, and Chunyan Miao (Eds.). ACM, 2802--2810."},{"key":"e_1_2_2_22_1","volume-title":"Christina Ilvento, and Josh Karlin.","author":"Epasto Alessandro","year":"2022","unstructured":"Alessandro Epasto, Andres Munoz Medina, Christina Ilvento, and Josh Karlin. 2022. Measures of Cross-Site Re-Identification Risk: an Analysis of the Topics API Proposal. https:\/\/github.com\/patcg-individual-drafts\/topics\/blob\/main\/topics_analysis.pdf."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773174"},{"key":"e_1_2_2_24_1","volume-title":"Proceedings of the 2018 World Wide Web Conference on World Wide Web, WWW 2018","author":"Boix Alejandro G\u00f3","year":"2018","unstructured":"Alejandro G\u00f3 mez-Boix, Pierre Laperdrix, and Benoit Baudry. 2018. Hiding in the Crowd: an Analysis of the Effectiveness of Browser Fingerprinting at Large Scale. In Proceedings of the 2018 World Wide Web Conference on World Wide Web, WWW 2018, Lyon, France, April 23--27, 2019, Pierre-Antoine Champin, Fabien Gandon, Mounia Lalmas, and Panagiotis G. Ipeirotis (Eds.). ACM, 309--318."},{"key":"e_1_2_2_25_1","volume-title":"The Privacy Sandbox.","year":"2022","unstructured":"Google. 2022a. The Privacy Sandbox. Available at https:\/\/privacysandbox.com\/intl\/en_us\/ (Accessed October 15, 2022) (2022)."},{"key":"e_1_2_2_26_1","volume-title":"The Topics API.","year":"2022","unstructured":"Google. 2022b. The Topics API. Available at https:\/\/github.com\/patcg-individual-drafts\/topics (Accessed October 15, 2022) (2022)."},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403302"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/MBITS.2021.3108124"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/COMST.2016.2633620"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-011-0235-9"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3386040"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.101"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3054779"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.66"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055591"},{"key":"e_1_2_2_36_1","volume-title":"Data Privacy Management, and Security Assurance","author":"Acar Gunes","unstructured":"?ukasz Olejnik, Gunes Acar, Claude Castelluccia, and Claudia Diaz. 2015. The leaking battery. In Data Privacy Management, and Security Assurance. Springer, 254--263."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2010.06.002"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380596"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2017.41"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00596-1_21"},{"key":"e_1_2_2_41_1","unstructured":"Ilya Sutskever Oriol Vinyals and Quoc V Le. 2014. Sequence to sequence learning with neural networks. In Advances in neural information processing systems. 3104--3112."},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218488502001648"},{"key":"e_1_2_2_43_1","first-page":"I","article-title":"Attention is All you Need","volume":"30","author":"Vaswani Ashish","year":"2017","unstructured":"Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, ?ukasz Kaiser, and Illia Polosukhin. 2017. Attention is All you Need. In Advances in Neural Information Processing Systems 30, I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Eds.). Curran Associates, Inc., 5998--6008. http:\/\/papers.nips.cc\/paper\/7181-attention-is-all-you-need.pdf","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/ITA.2015.7308959"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/974121.974131"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2016.2584610"},{"key":"e_1_2_2_47_1","volume-title":"Extending Differential Privacy for Treating Dependent Records via Information Theory. CoRR","author":"Wu Genqiang","year":"2017","unstructured":"Genqiang Wu, Xianyao Xia, and Yeping He. 2017. Extending Differential Privacy for Treating Dependent Records via Information Theory. CoRR, Vol. abs\/1703.07474 (2017). http:\/\/arxiv.org\/abs\/1703.07474"},{"key":"e_1_2_2_48_1","volume-title":"Local Differential Privacy and Its Applications: A Comprehensive Survey. CoRR","author":"Yang Mengmeng","year":"2020","unstructured":"Mengmeng Yang, Lingjuan Lyu, Jun Zhao, Tianqing Zhu, and Kwok-Yan Lam. 2020. Local Differential Privacy and Its Applications: A Comprehensive Survey. CoRR, Vol. abs\/2008.03686 (2020). https:\/\/arxiv.org\/abs\/2008.03686"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3589294","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3589294","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:13Z","timestamp":1750178773000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3589294"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,13]]},"references-count":48,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6,13]]}},"alternative-id":["10.1145\/3589294"],"URL":"https:\/\/doi.org\/10.1145\/3589294","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,13]]}}}