PACIFIC
Privacy-preserving automated contact tracing featuring integrity against cloning
Authors
Scott Griffy, Anna Lysyanskaya
Scott Griffy
Brown University, United States
scott_griffy at brown dot edu
scott_griffy at brown dot edu
Anna Lysyanskaya
Brown University, United States
anna_lysyanskaya at brown dot edu
anna_lysyanskaya at brown dot edu
Abstract
To be useful and widely accepted, automated contact tracing schemes (also called exposure notification) need to solve two seemingly contradictory problems at the same time: they need to protect the anonymity of honest users while also preventing malicious users from creating false alarms. In this paper, we provide, for the first time, an exposure notification construction that guarantees the same levels of privacy and integrity as existing schemes but with a fully malicious database (notably similar to Auerbach et al. CT-RSA 2021) without special restrictions on the adversary. We construct a new definition so that we can formally prove our construction secure. Our definition ensures the following integrity guarantees: no malicious user can cause exposure warnings in two locations at the same time and that any uploaded exposure notifications must be recent and not previously uploaded. Our construction is efficient, requiring only a single message to be broadcast at contact time no matter how many recipients are nearby. To notify contacts of potential infection, an infected user uploads data with size linear in the number of notifications, similar to other schemes. Linear upload complexity is not trivial with our assumptions and guarantees (a naive scheme would be quadratic). This linear complexity is achieved with a new primitive: zero knowledge subset proofs over commitments which is used by our "no cloning" proof protocol. We also introduce another new primitive: set commitments on equivalence classes, which makes each step of our construction more efficient. Both of these new primitives are of independent interest.
References
[ABIV23]
Gennaro Avitabile, Vincenzo Botta, Vincenzo Iovino, and Ivan Visconti. Privacy and Integrity Threats in Contact Tracing Systems and Their Mitigations. IEEE Internet Computing, 27(2):13-19, 2023. Full version: https://eprint.iacr.org/2020/493 DOI: 10.1109/MIC.2022.3213870
[ACK+21]
Benedikt Auerbach, Suvradip Chakraborty, Karen Klein, Guillermo Pascual-Perez, Krzysztof Pietrzak, Michael Walter, and Michelle Yeo. Inverse-Sybil Attacks in Automated Contact Tracing. In Kenneth G. Paterson, editor, CT-RSA 2021, volume 12704 of LNCS, pages 399–421. May 2021. Springer, Heidelberg. DOI: 10.1007/978-3-030-75539-3_17
[AFV21]
Gennaro Avitabile, Daniele Friolo, and Ivan Visconti. Terrorist Attacks for Fake Exposure Notifications in Contact Tracing Systems. In Kazue Sako and Nils Ole Tippenhauer, editors, Applied Cryptography and Network Security, pages 220–247, Cham. 2021. Springer International Publishing. DOI: 10.1007/978-3-030-78372-3_9
[BBB+18]
Benedikt Bünz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille, and Greg Maxwell. Bulletproofs: Short Proofs for Confidential Transactions and More. In 2018 IEEE Symposium on Security and Privacy (SP), pages 315-334. 2018. DOI: 10.1109/SP.2018.00020
[BCK+20]
Jean-François Biasse, Sriram Chellappan, Sherzod Kariev, Noyem Khan, Lynette Menezes, Efe Seyitoglu, Charurut Somboonwit, and Attila Yavuz. Trace-$\Sigma$: a privacy-preserving contact tracing app. https://eprint.iacr.org/2020/792. IACR ePrint. 2020.
[BD19]
Razvan Barbulescu and Sylvain Duquesne. Updating Key Size Estimations for Pairings. Journal of Cryptology, 32(4):1298–1336, October 2019. DOI: 10.1007/s00145-018-9280-5
[BDH+21]
Wasilij Beskorovajnov, Felix Dörre, Gunnar Hartung, Alexander Koch, Jörn Müller-Quade, and Thorsten Strufe. ConTra Corona: Contact Tracing against the Coronavirus by Bridging the Centralized–Decentralized Divide for Stronger Privacy. In Mehdi Tibouchi and Huaxiong Wang, editors, Advances in Cryptology – ASIACRYPT 2021, pages 665–695, Cham. 2021. Springer International Publishing. DOI: 10.1007/978-3-030-92075-3_23
[BLS19]
Johannes K. Becker, David Li, and David Starobinski. Tracking Anonymized Bluetooth Devices. PoPETs, 2019(3):50–65, July 2019. DOI: 10.2478/popets-2019-0036
[BRS20]
Samuel Brack, Leonie Reichert, and Björn Scheuermann. CAUDHT: Decentralized Contact Tracing Using a DHT and Blind Signatures. In 2020 IEEE 45th Conference on Local Computer Networks (LCN), pages 337-340. 2020. DOI: 10.1109/LCN48667.2020.9314850
[CBB+20]
Claude Castelluccia, Nataliia Bielova, Antoine Boutet, Mathieu Cunche, Cédric Lauradoux, Daniel Le Métayer, and Vincent Roca. DESIRE: A Third Way for a European Exposure Notification System Leveraging the best of centralized and decentralized systems. CoRR, abs/2008.01621, 2020.
[CBC+24]
Miranda Christ, Foteini Baldimtsi, Konstantinos Kryptos Chalkias, Deepak Maram, Arnab Roy, and Joy Wang. SoK: Zero-Knowledge Range Proofs. https://eprint.iacr.org/2024/430. Cryptology ePrint Archive, Paper 2024/430. 2024.
[CFG+20]
Justin Chan, Dean Foster, Shyam Gollakota, Eric Horvitz, Joseph Jaeger, Sham Kakade, Tadayoshi Kohno, John Langford, Jonathan Larson, Puneet Sharma, Sudheesh Singanamalla, Jacob Sunshine, and Stefano Tessaro. PACT: Privacy Sensitive Protocols and Mechanisms for Mobile Contact Tracing. 2020.
[CGH+23]
Sofía Celi, Scott Griffy, Lucjan Hanzlik, Octavio Perez Kempner, and Daniel Slamanig. SoK: Signatures With Randomizable Keys. https://eprint.iacr.org/2023/1524. Cryptology ePrint Archive, Paper 2023/1524. 2023.
[Cha81]
David L. Chaum. Untraceable electronic mail, return addresses, and digital pseudonyms. Commun. ACM, 24(2):84–90, February 1981. DOI: 10.1145/358549.358563
[CHK+06]
Jan Camenisch, Susan Hohenberger, Markulf Kohlweiss, Anna Lysyanskaya, and Mira Meyerovich. How to win the clonewars: Efficient periodic n-times anonymous authentication. In Ari Juels, Rebecca N. Wright, and Sabrina De Capitani di Vimercati, editors, ACM CCS 2006, pages 201–210. 2006. ACM Press. DOI: 10.1145/1180405.1180431
[CKL+20]
Ran Canetti, Yael Tauman Kalai, Anna Lysyanskaya, Ronald L. Rivest, Adi Shamir, Emily Shen, Ari Trachtenberg, Mayank Varia, and Daniel J. Weitzner. Privacy-Preserving Automated Exposure Notification. https://eprint.iacr.org/2020/863. Cryptology ePrint Archive, Report 2020/863. 2020.
[CL19]
Elizabeth C. Crites and Anna Lysyanskaya. Delegatable Anonymous Credentials from Mercurial Signatures. In Mitsuru Matsui, editor, CT-RSA 2019, volume 11405 of LNCS, pages 535–555. March 2019. Springer, Heidelberg. DOI: 10.1007/978-3-030-12612-4_27
[Cos12]
Craig Costello. Pairings for beginners. https://www.craigcostello.com.au/s/PairingsForBeginners.pdf. Online. 2012.
[CS97]
Jan Camenisch and Markus Stadler. Proof systems for general statements about discrete logarithms. Technical report, Technical Reports D-INFK.. 1997.
[DY05]
Yevgeniy Dodis and Aleksandr Yampolskiy. A Verifiable Random Function with Short Proofs and Keys. In Serge Vaudenay, editor, PKC 2005, volume 3386 of LNCS, pages 416–431. January 2005. Springer, Heidelberg. DOI: 10.1007/978-3-540-30580-4_28
[FHS19]
Georg Fuchsbauer, Christian Hanser, and Daniel Slamanig. Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials. Journal of Cryptology, 32(2):498–546, April 2019. DOI: 10.1007/s00145-018-9281-4
[GA20]
Google and Apple. Privacy-Preserving Contact Tracing. https://covid19.apple.com/contacttracing. 2020.
[GKK20]
Rosario Gennaro, Adam Krellenstein, and James Krellenstein. Exposure notification system may allow for large-scale voter suppression. Real World Crypto. 2020.
[GMR88]
Shafi Goldwasser, Silvio Micali, and Ronald L. Rivest. A Digital Signature Scheme Secure Against Adaptive Chosen-message Attacks. SIAM Journal on Computing, 17(2):281–308, April 1988.
[GPS08]
Steven D. Galbraith, Kenneth G. Paterson, and Nigel P. Smart. Pairings for cryptographers. Discrete Appl. Math., 156(16):3113–3121, September 2008. DOI: 10.1016/j.dam.2007.12.010
[GVhP+22]
Giuseppe Garofalo, Tim Van hamme, Davy Preuveneers, Wouter Joosen, Aysajan Abidin, and Mustafa A. Mustafa. PIVOT: Private and Effective Contact Tracing. 2022.
[HM20]
Thomas Haines and Johannes Müller. SoK: Techniques for Verifiable Mix Nets. In Limin Jia and Ralf Küsters, editors, CSF 2020 Computer Security Foundations Symposium, pages 49–64. 2020. IEEE Computer Society Press. DOI: 10.1109/CSF49147.2020.00012
[HMM+21]
Katie Hogan, Briana Macedo, Venkata Macha, Arko Barman, and Xiaoqian Jiang. Contact Tracing Apps: Lessons Learned on Privacy, Autonomy, and the Need for Detailed and Thoughtful Implementation. JMIR Med Inform, 9(7):e27449, July 2021. DOI: 10.2196/27449
[KL14]
Jonathan Katz and Yehuda Lindell. Introduction to Modern Cryptography. CRC Press, Second edition. 2014.
[KLN23]
Markulf Kohlweiss, Anna Lysyanskaya, and An Nguyen. Privacy-Preserving Blueprints. In Carmit Hazay and Martijn Stam, editors, EUROCRYPT 2023, Part II, volume 14005 of LNCS, pages 594–625. April 2023. Springer, Heidelberg. DOI: 10.1007/978-3-031-30617-4_20
[MRV99]
Silvio Micali, Michael O. Rabin, and Salil P. Vadhan. Verifiable Random Functions. In 40th FOCS, pages 120–130. October 1999. IEEE Computer Society Press. DOI: 10.1109/SFFCS.1999.814584
[MSBM23]
Omid Mir, Daniel Slamanig, Balthazar Bauer, and Rene Mayrhofer. Practical Delegatable Anonymous Credentials From Equivalence Class Signatures. Proceedings on Privacy Enhancing Technologies, 2023:488–513, June 2023. DOI: 10.56553/popets-2023-0093
[Org24]
World Health Organization. WHO Coronavirus (COVID-19) Dashboard. https://covid19.who.int/. 2024.
[PR21]
Benny Pinkas and Eyal Ronen. Hashomer – Privacy-Preserving Bluetooth Based Contact Tracing Scheme for Hamagen. Proceedings 2021 Innovative Secure IT Technologies against COVID-19 Workshop, 2021. DOI: 10.14722/coronadef.2021.23011
[RAC+20]
Ronald L. Rivest, Hal Abelson, Jon Callas, Ran Canetti, Kevin Esvelt, Daniel Kahn Gillmor, Louise Ivers, Yael Tauman Kalai, Anna Lysyanskaya, Adam Norige, Bobby Pelletier, Ramesh Raskar, Adi Shamir, Emily Shen, Israel Soibelman, Michael Specter, Vanessa Teague, Ari Trachtenberg, Mayank Varia, Marc Viera, Daniel Weitzner, John Wilkinson, and Marc Zissman. The PACT protocol specification. https://pact.mit.edu/wp-content/uploads/2020/11/The-PACT-protocol-specification-2020.pdf. 2020.
[RBS20]
Leonie Reichert, Samuel Brack, and Björn Scheuermann. Privacy-Preserving Contact Tracing of COVID-19 Patients. https://www.ieee-security.org/TC/SP2020/poster-abstracts/hotcrp_sp20posters-final10.pdf. Poster session, IEEE Symposium on Security and Privacy. 2020.
[RBS21]
Leonie Reichert, Samuel Brack, and Björn Scheuermann. Ovid: Message-based Automatic Contact Tracing. https://www.ndss-symposium.org/wp-content/uploads/coronadef2021_23010_paper.pdf. CoronaDef Workshop. 2021.
[TN21]
Cong Duc Tran and Tin Trung Nguyen. Health vs. privacy? The risk-risk tradeoff in using COVID-19 contact-tracing apps. Technol Soc, 67:101755, September 2021. DOI: 10.1016/j.techsoc.2021.101755
[TPH+20]
Carmela Troncoso, Mathias Payer, Jean-Pierre Hubaux, Marcel Salathé, James R. Larus, Edouard Bugnion, Wouter Lueks, Theresa Stadler, Apostolos Pyrgelis, Daniele Antonioli, Ludovic Barman, Sylvain Chatel, Kenneth G. Paterson, Srdjan Capkun, David A. Basin, Jan Beutel, Dennis Jackson, Marc Roeschlin, Patrick Leu, Bart Preneel, Nigel P. Smart, Aysajan Abidin, Seda F. Gürses, Michael Veale, Cas Cremers, Michael Backes, Nils Ole Tippenhauer, Reuben Binns, Ciro Cattuto, Alain Barrat, Dario Fiore, Manuel Barbosa, Rui Oliveira, and José Pereira. Decentralized Privacy-Preserving Proximity Tracing. CoRR, abs/2005.12273, 2020.
[Tra20]
TraceTogether. https://www.tracetogether.gov.sg/. Government of Singapore. 2020.
[TSS+20]
Ni Trieu, Kareem Shehata, Prateek Saxena, Reza Shokri, and Dawn Song. Epione: Lightweight Contact Tracing with Strong Privacy. 2020.
[Vau20a]
Serge Vaudenay. Analysis of DP3T. https://eprint.iacr.org/2020/399. IACR ePrint. 2020.
[Vau20b]
Serge Vaudenay. Centralized or Decentralized? The Contact Tracing Dilemma. https://eprint.iacr.org/2020/531. IACR ePrint. 2020.
[WL20]
Zhiguo Wan and Xiaotong Liu. ContactChaser: A Simple yet Effective Contact Tracing Scheme with Strong Privacy. https://eprint.iacr.org/2020/630. IACR ePrint. 2020.
PDF
History
Submitted: 2024-04-08
Accepted: 2024-06-03
Published: 2024-07-08
Accepted: 2024-06-03
Published: 2024-07-08
How to cite
Scott Griffy and Anna Lysyanskaya, PACIFIC. IACR Communications in Cryptology, vol. 1, no. 2, Jul 08, 2024, doi: 10.62056/ay11fhbmo.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.