{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T17:05:05Z","timestamp":1753895105845,"version":"3.41.2"},"reference-count":44,"publisher":"International Association for Cryptologic Research","license":[{"start":{"date-parts":[[2024,4,8]],"date-time":"2024-04-08T00:00:00Z","timestamp":1712534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2024,6,3]]},"abstract":"<jats:p>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. <\/jats:p>","DOI":"10.62056\/ay11fhbmo","type":"journal-article","created":{"date-parts":[[2024,7,8]],"date-time":"2024-07-08T15:52:04Z","timestamp":1720453924000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":0,"title":["PACIFIC"],"prefix":"10.62056","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-6016-5163","authenticated-orcid":false,"given":"Scott","family":"Griffy","sequence":"first","affiliation":[{"name":"Brown University","place":["United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3567-3550","authenticated-orcid":false,"given":"Anna","family":"Lysyanskaya","sequence":"additional","affiliation":[{"name":"Brown University","place":["United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"48349","published-online":{"date-parts":[[2024,7,8]]},"reference":[{"key":"ref1:RSA:ACKPPWY21","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/978-3-030-75539-3_17","article-title":"Inverse-Sybil Attacks in Automated Contact Tracing","volume-title":"CT-RSA\u00a02021","volume":"12704","author":"Benedikt Auerbach","year":"2021"},{"article-title":"WHO Coronavirus (COVID-19) Dashboard","year":"2024","author":"World Health Organization","key":"ref2:whoStats"},{"key":"ref3:Hogan2021-ku","doi-asserted-by":"publisher","DOI":"10.2196\/27449","article-title":"Contact Tracing Apps: Lessons Learned on Privacy, Autonomy,\n  and the Need for Detailed and Thoughtful Implementation","volume":"9","author":"Katie Hogan","year":"2021","journal-title":"JMIR Med Inform"},{"key":"ref4:Tran2021-al","doi-asserted-by":"publisher","first-page":"101755","DOI":"10.1016\/j.techsoc.2021.101755","article-title":"Health vs. privacy? The risk-risk tradeoff in using\n  COVID-19 contact-tracing apps","volume":"67","author":"Cong Duc Tran","year":"2021","journal-title":"Technol Soc"},{"key":"ref5:DP3T","article-title":"Decentralized Privacy-Preserving Proximity Tracing","volume":"abs\/2005.12273","author":"Carmela Troncoso","year":"2020","journal-title":"CoRR"},{"article-title":"Privacy-Preserving Contact Tracing","year":"2020","author":"Google","key":"ref6:GAPPLE"},{"article-title":"Privacy-Preserving Automated Exposure Notification","year":"2020","author":"Ran Canetti","key":"ref7:EPRINT:CKLRSSTVW20"},{"article-title":"Exposure notification system may allow for large-scale voter\n  suppression","year":"2020","author":"Rosario Gennaro","key":"ref8:voterSuppression"},{"article-title":"The PACT protocol specification","year":"2020","author":"Ronald L. Rivest","key":"ref9:pact"},{"article-title":"PACT: Privacy Sensitive Protocols and Mechanisms for Mobile\n  Contact Tracing","year":"2020","author":"Justin Chan","key":"ref10:PAndCT"},{"key":"ref11:caudht","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1109\/LCN48667.2020.9314850","article-title":"CAUDHT: Decentralized Contact Tracing Using a DHT and Blind\n  Signatures","volume-title":"2020 IEEE 45th Conference on Local Computer Networks (LCN)","author":"Samuel Brack","year":"2020"},{"key":"ref12:contra","isbn-type":"print","doi-asserted-by":"publisher","first-page":"665","DOI":"10.1007\/978-3-030-92075-3_23","article-title":"ConTra Corona: Contact Tracing against the Coronavirus by\n  Bridging the Centralized\u2013Decentralized Divide for Stronger Privacy","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2021","author":"Wasilij Beskorovajnov","year":"2021","ISBN":"https:\/\/id.crossref.org\/isbn\/9783030920753"},{"key":"ref13:hashomer","doi-asserted-by":"publisher","DOI":"10.14722\/coronadef.2021.23011","article-title":"Hashomer \u2013 Privacy-Preserving Bluetooth Based Contact\n  Tracing Scheme for Hamagen","author":"Benny Pinkas","year":"2021","journal-title":"Proceedings 2021 Innovative Secure IT Technologies against\n  COVID-19 Workshop"},{"key":"ref14:ProntoC2","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1109\/MIC.2022.3213870","article-title":"Privacy and Integrity Threats in Contact Tracing Systems and\n  Their Mitigations","volume":"27","author":"Gennaro Avitabile","year":"2023","journal-title":"IEEE Internet Computing"},{"article-title":"Centralized or Decentralized? The Contact Tracing Dilemma","year":"2020","author":"Serge Vaudenay","key":"ref15:CentralDecentral"},{"article-title":"Ovid: Message-based Automatic Contact Tracing","year":"2021","author":"Leonie Reichert","key":"ref16:ovid"},{"article-title":"ContactChaser: A Simple yet Effective Contact Tracing Scheme\n  with Strong Privacy","year":"2020","author":"Zhiguo Wan","key":"ref17:ContactChaser"},{"key":"ref18:desire","article-title":"DESIRE: A Third Way for a European Exposure Notification\n  System Leveraging the best of centralized and decentralized systems","volume":"abs\/2008.01621","author":"Claude Castelluccia","year":"2020","journal-title":"CoRR"},{"key":"ref19:pivot","doi-asserted-by":"publisher","first-page":"22466","DOI":"10.1109\/JIOT.2021.3138694","article-title":"PIVOT: Private and Effective Contact Tracing","volume":"9","author":"Giuseppe Garofalo","year":"2022","journal-title":"IEEE Internet of Things Journal"},{"article-title":"Privacy-Preserving Contact Tracing of COVID-19 Patients","year":"2020","author":"Leonie Reichert","key":"ref20:ppactParients"},{"key":"ref21:epione","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2004.13293","article-title":"Epione: Lightweight Contact Tracing with Strong Privacy","author":"Ni Trieu","year":"2020"},{"year":"2020","key":"ref22:TraceTogether","article-title":"TraceTogether"},{"article-title":"Analysis of DP3T","year":"2020","author":"Serge Vaudenay","key":"ref23:Vau20"},{"key":"ref24:terroristAttacks","isbn-type":"print","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1007\/978-3-030-78372-3_9","article-title":"Terrorist Attacks for Fake Exposure Notifications in Contact\n  Tracing Systems","volume-title":"Applied Cryptography and Network Security","author":"Gennaro Avitabile","year":"2021","ISBN":"https:\/\/id.crossref.org\/isbn\/9783030783723"},{"article-title":"Trace-$\\Sigma$: a privacy-preserving contact tracing app","year":"2020","author":"Jean-Fran\u00e7ois Biasse","key":"ref25:yavuzACT"},{"key":"ref26:CCS:CHKLM06","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1145\/1180405.1180431","article-title":"How to win the clonewars: Efficient periodic n-times\n  anonymous authentication","volume-title":"ACM CCS 2006","author":"Jan Camenisch","year":"2006"},{"key":"ref27:mixNets","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1145\/358549.358563","article-title":"Untraceable electronic mail, return addresses, and digital\n  pseudonyms","volume":"24","author":"David L. Chaum","year":"1981","journal-title":"Commun. ACM","ISSN":"https:\/\/id.crossref.org\/issn\/0001-0782","issn-type":"electronic"},{"key":"ref28:CSF:HaiMul20","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1109\/CSF49147.2020.00012","article-title":"SoK: Techniques for Verifiable Mix Nets","volume-title":"CSF 2020 Computer Security Foundations Symposium","author":"Thomas Haines","year":"2020"},{"key":"ref29:PoPETS:BecLiSta19","doi-asserted-by":"publisher","first-page":"50","DOI":"10.2478\/popets-2019-0036","article-title":"Tracking Anonymized Bluetooth Devices","volume":"2019","author":"Johannes K. Becker","year":"2019","journal-title":"PoPETs"},{"key":"ref30:RSA:CriLys19","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1007\/978-3-030-12612-4_27","article-title":"Delegatable Anonymous Credentials from Mercurial\n  Signatures","volume-title":"CT-RSA\u00a02019","volume":"11405","author":"Elizabeth C. Crites","year":"2019"},{"key":"ref31:JC:FucHanSla19","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1007\/s00145-018-9281-4","article-title":"Structure-Preserving Signatures on Equivalence Classes and\n  Constant-Size Anonymous Credentials","volume":"32","author":"Georg Fuchsbauer","year":"2019","journal-title":"Journal of Cryptology"},{"key":"ref32:GPS06","doi-asserted-by":"publisher","first-page":"3113","DOI":"10.1016\/j.dam.2007.12.010","article-title":"Pairings for cryptographers","volume":"156","author":"Steven D. Galbraith","year":"2008","journal-title":"Discrete Appl. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0166-218X","issn-type":"electronic"},{"article-title":"Introduction to Modern Cryptography","year":"2014","author":"Jonathan Katz","key":"ref33:KatLin14"},{"key":"ref34:GolMicRiv88","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1137\/0217017","article-title":"A Digital Signature Scheme Secure Against Adaptive\n  Chosen-message Attacks","volume":"17","author":"Shafi Goldwasser","year":"1988","journal-title":"SIAM Journal on Computing"},{"key":"ref35:FOCS:MicRabVad99","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1109\/SFFCS.1999.814584","article-title":"Verifiable Random Functions","volume-title":"40th FOCS","author":"Silvio Micali","year":"1999"},{"key":"ref36:PKC:DodYam05","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1007\/978-3-540-30580-4_28","article-title":"A Verifiable Random Function with Short Proofs and Keys","volume-title":"PKC\u00a02005","volume":"3386","author":"Yevgeniy Dodis","year":"2005"},{"article-title":"Pairings for beginners","year":"2012","author":"Craig Costello","key":"ref37:costelloPairings"},{"key":"ref38:CamStad97ProofSystems","doi-asserted-by":"publisher","DOI":"10.3929\/ethz-a-006651937","article-title":"Proof systems for general statements about discrete\n  logarithms","volume":"260","author":"Jan Camenisch","year":"1997","journal-title":"Technical Report \/ ETH Zurich, Department of Computer\n  Science"},{"key":"ref39:EC:KohLysNgu23","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"594","DOI":"10.1007\/978-3-031-30617-4_20","article-title":"Privacy-Preserving Blueprints","volume-title":"EUROCRYPT\u00a02023, Part\u00a0II","volume":"14005","author":"Markulf Kohlweiss","year":"2023"},{"article-title":"SoK: Signatures With Randomizable Keys","year":"2023","author":"Sof\u00eda Celi","key":"ref40:sok-rand-keys"},{"key":"ref41:PDAC","doi-asserted-by":"publisher","first-page":"488","DOI":"10.56553\/popets-2023-0093","article-title":"Practical Delegatable Anonymous Credentials From Equivalence\n  Class Signatures","volume":"2023","author":"Omid Mir","year":"2023","journal-title":"Proceedings on Privacy Enhancing Technologies"},{"key":"ref42:bulletproofs","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1109\/SP.2018.00020","article-title":"Bulletproofs: Short Proofs for Confidential Transactions and\n  More","volume-title":"2018 IEEE Symposium on Security and Privacy (SP)","author":"Benedikt B\u00fcnz","year":"2018"},{"article-title":"SoK: Zero-Knowledge Range Proofs","year":"2024","author":"Miranda Christ","key":"ref43:sokRange"},{"key":"ref44:JC:BarDuq19","doi-asserted-by":"publisher","first-page":"1298","DOI":"10.1007\/s00145-018-9280-5","article-title":"Updating Key Size Estimations for Pairings","volume":"32","author":"Razvan Barbulescu","year":"2019","journal-title":"Journal of Cryptology"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T21:26:55Z","timestamp":1733866015000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/1\/2\/12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,8]]},"references-count":44,"URL":"https:\/\/doi.org\/10.62056\/ay11fhbmo","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"type":"electronic","value":"3006-5496"}],"subject":[],"published":{"date-parts":[[2024,7,8]]},"assertion":[{"value":"2024-04-08","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-06-03","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc1-2-36"}}