Abstract
In this paper, we propose a privacy-preserving contact tracing protocol for smart phones, and more specifically Android and iOS phones. The protocol allows users to be notified, if they have been a close contact of a confirmed patient. The protocol is designed to strike a balance between privacy, security, and scalability. Specifically, the app allows all users to hide their past location(s) and contact history from the Government, without affecting their ability to determine whether they have close contact with a confirmed patient whose identity will not be revealed. A zero-knowledge protocol is used to achieve such a user privacy functionality. In terms of security, no user can send fake messages to the system to launch a false positive attack. We present a security model and formally prove the security of the protocol. To demonstrate scalability, we evaluate an Android and an iOS implementation of our protocol. A comparative summary shows that our protocol is the most comprehensive and balanced privacy-preserving contact tracing solution to-date.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
https://www.technologyreview.com/2021/01/05/1015734/singapore-contact-tracing-police-data-covid/, last accessed January 13, 2021.
- 2.
\(\mathcal {GV}\) may record the related identification information (e.g., name, phone, email)of the user if this is a first-time registration.
References
Apple Inc and Google Inc., Contact tracing Bluetooth specification v1.1 (2020). https://www.blog.google/documents/58/Contact_Tracing_-_Bluetooth_Specification_v1.1_RYGZbKW.pdf. Accessed 30 Apr 2020
Apple Inc and Google Inc., Contact tracing cryptography specification (2020). https://www.blog.google/documents/56/Contact_Tracing_-_Cryptography_Specification.pdf. Accessed 30 Apr 2020
Au, M.H., et al.: A general framework for secure sharing of personal health records in cloud system. J. Comput. Syst. Sci. 90, 46–62 (2017)
Avitabile, G., Friolo, D., Visconti, I.: TEnK-U: terrorist attacks for fake exposure notifications in contact tracing systems. Cryptology ePrint Archive, Report 2020/1150 (2020). https://eprint.iacr.org/2020/1150
Bellare, M., Micciancio, D., Warinschi, B.: Foundations of group signatures: formal definitions, simplified requirements, and a construction based on general assumptions. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 614–629. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-39200-9_38
Boneh, D., Boyen, X.: Short signatures without random oracles. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 56–73. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24676-3_4
Chan, J., et al.: PACT: privacy sensitive protocols and mechanisms for mobile contact tracing (2020)
Chen, Z., et al.: Verifiable keyword search for secure big data-based mobile healthcare networks with fine-grained authorization control. Future Gener. Comput. Syst. 87, 712–724 (2018)
Chetty, R., Friedman, J.N., Hendren, N., Stepner, M., et al.: How did COVID-19 and stabilization policies affect spending and employment? A new real-time economic tracker based on private sector data. Technical report, National Bureau of Economic Research (2020)
Danz, N., Derwisch, O., Lehmann, A., Puenter, W., Stolle, M., Ziemann, J.: Security and privacy of decentralized cryptographic contact tracing. Cryptology ePrint Archive, Report 2020/1309 (2020). https://eprint.iacr.org/2020/1309
Dawsey, J., Dawsey, J., Abutaleb, Y., Stanley-Becker, I., Achenbach, J.: Little evidence that White House has offered contact tracing, guidance to hundreds potentially exposed (2020). https://www.washingtonpost.com/health/white-house-covid-contact-tracing/2020/10/03/2a6b8e2a-05a1-11eb-897d-3a6201d6643f_story.html. Accessed 5 Oct 2020
Ferretti, L., et al.: Quantifying SARS-CoV-2 transmission suggests epidemic control with digital contact tracing. Science 368(6491) (2020)
Gentry, C.: Practical identity-based encryption without random oracles. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 445–464. Springer, Heidelberg (2006). https://doi.org/10.1007/11761679_27
Goldwasser, S., Micali, S., Rivest, R.L.: A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput. 17(2), 281–308 (1988)
Gvili, Y.: Security analysis of the COVID-19 contact tracing specifications by Apple Inc. and Google Inc. Cryptology ePrint Archive, Report 2020/428 (2020). https://eprint.iacr.org/2020/428
He, K., Weng, J., Liu, J.K., Zhou, W., Liu, J.-N.: Efficient fine-grained access control for secure personal health records in cloud computing. In: Chen, J., Piuri, V., Su, C., Yung, M. (eds.) NSS 2016. LNCS, vol. 9955, pp. 65–79. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-46298-1_5
Hellewell, J., et al.: Feasibility of controlling COVID-19 outbreaks by isolation of cases and contacts. Lancet Glob. Health 8(4), e488–e496 (2020)
Liu, J., Huang, X., Liu, J.K.: Secure sharing of personal health records in cloud computing: ciphertext-policy attribute-based signcryption. Future Gener. Comput. Syst. 52, 67–76 (2015)
Liu, J.K., et al.: Privacy-preserving COVID-19 contact tracing app: a zero-knowledge proof approach. Cryptology ePrint Archive, Report 2020/528 (2020). https://eprint.iacr.org/2020/528
Pietrzak, K.: Delayed authentication: preventing replay and relay attacks in private contact tracing. Cryptology ePrint Archive, Report 2020/418 (2020). https://eprint.iacr.org/2020/418
Rivest, R., et al.: The pact protocol specification (2020). https://pact.mit.edu/wp-content/uploads/2020/04/The-PACT-protocol-specification-ver-0.1.pdf
Salathé, M., et al.: COVID-19 epidemic in Switzerland: on the importance of testing, contact tracing and isolation. Swiss Med. Weekly 150(11–12), w20225 (2020)
Troncoso, C., et al.: Decentralized privacy-preserving proximity tracing (2020). https://github.com/DP-3T/documents/blob/master/DP3T20%White%20Paper.pdf. Accessed 30 Apr 2020
Vaudenay, S.: Analysis of DP3T. Cryptology ePrint Archive, Report 2020/399 (2020). https://eprint.iacr.org/2020/399
Warren, M., Liptak, K., Shallwani, P.: White House’s inept ‘contact tracing’ effort leaves the work to others (2020). https://www.cnn.com/2020/10/04/politics/white-house-contact-tracing-covid/index.html. Accessed 5 Oct 2020
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Liu, J.K. et al. (2021). Privacy-Preserving Contact Tracing Protocol for Mobile Devices: A Zero-Knowledge Proof Approach. In: Deng, R., et al. Information Security Practice and Experience. ISPEC 2021. Lecture Notes in Computer Science(), vol 13107. Springer, Cham. https://doi.org/10.1007/978-3-030-93206-0_20
Download citation
DOI: https://doi.org/10.1007/978-3-030-93206-0_20
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-93205-3
Online ISBN: 978-3-030-93206-0
eBook Packages: Computer ScienceComputer Science (R0)