Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

PPCT: Privacy-Preserving Contact Tracing Using Concise Private Set Intersection Cardinality

  • Published:
Journal of Network and Systems Management Aims and scope Submit manuscript

Abstract

Contact tracing (CT) is an indispensable tool in controlling infectious disease outbreaks, which is regarded as the most effective weapon for curbing the spread of viruses. Due to the emergence of infectious diseases, many countries have implemented CT systems to mitigate the spread of the virus. Nevertheless, existing systems are either insufficiently secure or have high computational requirements for resource-constrained client devices. Thus, in this paper, we propose PPCT, an efficient and privacy-preserving CT system that prevents all significant attacks present in most CT systems. Our system ensures that the personal information of diagnosed users remains private from both the server and other users. Specifically, by employing our new and concise private set intersection cardinality (CPSI-CA) protocol, PPCT can efficiently answer user queries while preserving the privacy of personal information and query results. Furthermore, we conducted extensive experiments, and the results show that PPCT outperforms most existing systems in terms of computational cost and communication overhead, which demonstrates the feasibility of PPCT. More specifically, our scheme has improved a hundred times on client runtime.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

Data Availability

No datasets were generated or analysed during the current study.

References

  1. Ahmed, N., Michelin, R.A., Xue, W., Putra, G.D., Ruj, S., Kanhere, S.S., Jha, S.: DIMY: enabling privacy-preserving contact tracing. J. Netw. Comput. Appl. 202, 103356 (2022). https://doi.org/10.1016/j.jnca.2022.103356

    Article  Google Scholar 

  2. Bautista, O.G., Manshaei, M.H., Hernandez, R., Akkaya, K., Homsi, S., Uluagac, S.: MPC-ABC: blockchain-based network communication for efficiently secure multiparty computation. J. Netw. Syst. Manage. 31(4), 68 (2023)

    Article  Google Scholar 

  3. Brack, S., Reichert, L., Scheuermann, B.: Caudht: decentralized contact tracing using a DHT and blind signatures. In: 2020 IEEE 45th Conference on Local Computer Networks (LCN), pp. 337–340. IEEE (2020)

  4. Canetti, R., Kalai, Y.T., Lysyanskaya, A., Rivest, R.L., Shamir, A., Shen, E., Trachtenberg, A., Varia, M., Weitzner, D.J.: Privacy-preserving automated exposure notification. Cryptology ePrint Archive (2020). https://eprint.iacr.org/2020/863

  5. Chan, J., Foster, D., Gollakota, S., Horvitz, E., Jaeger, J., Kakade, S., Kohno, T., Langford, J., Larson, J., Sharma, P., et al.: Pact: Privacy sensitive protocols and mechanisms for mobile contact tracing. arXiv preprint (2020). arXiv:2004.03544

  6. Chen, H., Yang, Y., Wu, Y.: Invalid message risks and analysis of laws to restrict cyber crime in social applications. In: Proceedings of the 2022 11th International Conference on Networks, Communication and Computing, pp. 341–347 (2022)

  7. Chen, X., Xu, S., Cao, Y., He, Y., Xiao, K.: AQRS: anti-quantum ring signature scheme for secure epidemic control with blockchain. Comput. Netw. 224, 109595 (2023)

    Article  Google Scholar 

  8. Chen, X., Xu, S., He, Y., Cui, Y., He, J., Gao, S.: LFS-AS: lightweight forward secure aggregate signature for e-health scenarios. In: ICC 2022-IEEE International Conference on Communications, pp. 1239–1244. IEEE (2022)

  9. Chen, X., Xu, S., Qin, T., Cui, Y., Gao, S., Kong, W.: AQ-ABS: anti-quantum attribute-based signature for EMRS sharing with blockchain. In: 2022 IEEE Wireless Communications and Networking Conference (WCNC), pp. 1176–1181. IEEE (2022)

  10. Debnath, S.K., Dutta, R.: Secure and efficient private set intersection cardinality using bloom filter. In: Proceedings of the 18th International Conference on Information Security, ISC 2015, vol. 9290, pp. 209–226. Springer, Berlin (2015). https://doi.org/10.1007/978-3-319-23318-5_12

  11. Dittmer, S., Ishai, Y., Lu, S., Ostrovsky, R., Elsabagh, M., Kiourtis, N., Schulte, B., Stavrou, A.: Function secret sharing for PSI-CA: with applications to private contact tracing. arXiv preprint (2020). arXiv:2012.13053

  12. Duong, T., Phan, D.H., Trieu, N.: Catalic: delegated psi cardinality with applications to contact tracing. In: International Conference on the Theory and Application of Cryptology and Information Security, pp. 870–899. Springer (2020)

  13. Feng, R., Chen, S., Xie, X., Ma, L., Meng, G., Liu, Y., Lin, S.W.: MobiDroid: a performance-sensitive malware detection system on mobile platform. In: 2019 24th International Conference on Engineering of Complex Computer Systems (ICECCS), pp. 61–70. IEEE (2019)

  14. Feng, R., Chen, S., Xie, X., Meng, G., Lin, S.W., Liu, Y.: A performance-sensitive malware detection system using deep learning on mobile devices. IEEE Trans. Inf. Forensics Secur. 16, 1563–1578 (2020)

    Article  Google Scholar 

  15. Ferretti, L., Wymant, C., Kendall, M., Zhao, L., Nurtay, A., Abeler-Dörner, L., Parker, M., Bonsall, D., Fraser, C.: Quantifying SARS-CoV-2 transmission suggests epidemic control with digital contact tracing. Science 368(6491), eabb6936 (2020)

    Article  Google Scholar 

  16. Gao, J., Surana, C., Trieu, N.: Secure contact tracing platform from simplest private set intersection cardinality. IET Inf. Secur. 16(5), 346–361 (2022)

    Article  Google Scholar 

  17. Garimella, G., Pinkas, B., Rosulek, M., Trieu, N., Yanai, A.: Oblivious key-value stores and amplification for private set intersection. In: Annual International Cryptology Conference, pp. 395–425. Springer (2021)

  18. Jhanwar, M.P., Sarkar, S.: PHYCT: Privacy preserving hybrid contact tracing. Cryptology ePrint Archive (2020)

  19. Jia, Y., Sun, S.F., Zhou, H.S., Du, J., Gu, D.: Shuffle-based private set union: faster and more secure. In: 31st USENIX Security Symposium (USENIX Security 22), pp. 2947–2964 (2022)

  20. Klinkenberg, D., Fraser, C., Heesterbeek, H.: The effectiveness of contact tracing in emerging epidemics. PLoS ONE 1(1), e12 (2006)

    Article  Google Scholar 

  21. Liu, J.K., Au, M.H., Yuen, T.H., Zuo, C., Wang, J., Sakzad, A., Luo, X., Li, L., Choo, K.K.R.: Privacy-preserving covid-19 contact tracing app: a zero-knowledge proof approach. Cryptology ePrint Archive (2020)

  22. Madhusudan, P., Ren, L., Venkatakrishnan, V.: Privacy-preserving secure contact tracing (2020). https://github.com/ConTraILProtocols/documents/blob/master/ContrailWhitePaper.pdf

  23. Michael, K., Abbas, R.: Behind covid-19 contact trace apps: the Google–Apple partnership. IEEE Consum. Electron. Mag. 9(5), 71–76 (2020)

    Article  Google Scholar 

  24. Mueller, U.E., Omosehin, O., Akinkunmi, A.E., Ayanbadejo, J.O., Somefun, E.O., Momah-Haruna, A.P.: Contact tracing in an African megacity during covid 19: lessons learned. Afr. J. Reprod. Health 24(2), 27–31 (2020)

    Google Scholar 

  25. Pagh, R., Rodler, F.F.: Cuckoo hashing. In: auf der Heide, F.M. (ed.) Algorithms—ESA 2001, pp. 121–133. Springer, Berlin (2001)

  26. Pinkas, B., Rosulek, M., Trieu, N., Yanai, A.: Spot-light: lightweight private set intersection from sparse OT extension. In: Annual International Cryptology Conference, pp. 401–431. Springer (2019)

  27. Pinkas, B., Rosulek, M., Trieu, N., Yanai, A.: PSI from PAXOS: fast, malicious private set intersection. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 739–767. Springer (2020)

  28. Pinkas, B., Schneider, T., Zohner, M.: Scalable private set intersection based on OT extension. ACM Trans. Privacy Secur. (TOPS) 21(2), 1–35 (2018)

    Article  Google Scholar 

  29. Rabin, M.O.: How to exchange secrets with oblivious transfer. Cryptology ePrint Archive (2005)

  30. Raskar, R., Pahwa, D., Beaudry, R.: Contact tracing: Holistic solution beyond Bluetooth. IEEE Data Eng. Bull. 43(2), 67–70 (2020)

    Google Scholar 

  31. Reichert, L., Brack, S., Scheuermann, B.: Privacy-preserving contact tracing of covid-19 patients. Cryptology ePrint Archive (2020)

  32. Shamir, A.: How to share a secret. Commun. ACM 22(11), 612–613 (1979). https://doi.org/10.1145/359168.359176

    Article  MathSciNet  Google Scholar 

  33. Tang, Q.: Privacy-preserving contact tracing: current solutions and open questions. arXiv preprint (2020). arXiv:2004.06818

  34. Tracetogether: (2021). https://www.tracetogether.gov.sg/. Accessed 2 Feb 2021

  35. Trieu, N., Shehata, K., Saxena, P., Shokri, R., Song, D.: Epione: lightweight contact tracing with strong privacy. arXiv preprint (2020). arXiv:2004.13293

  36. Troncoso, C., Payer, M., Hubaux, J.P., Salathé, M., Larus, J., Bugnion, E., Lueks, W., Stadler, T., Pyrgelis, A., Antonioli, D., et al.: Decentralized privacy-preserving proximity tracing. arXiv preprint (2020). arXiv:2005.12273

  37. Von Arx, S., Becker-Mayer, I., Blank, D., Colligan, J., Fenwick, R., Hittle, M., Ingle, M., Nash, O., Nguyen, V., Petrie, J., et al.: Slowing the spread of infectious diseases using crowdsourced data. IEEE Data Eng. Bull. 43(2), 71–82 (2020)

    Google Scholar 

  38. Wan, Z., Liu, X.: ContactChaser: a simple yet effective contact tracing scheme with strong privacy. Cryptology ePrint Archive (2020)

  39. Wang, X., Lin, Y., Yang, Y., Xu, H., Luo, Z.: A secure physical health test data sharing scheme based on token distribution and programmable blockchains. Comput. Commun. 209, 444–454 (2023)

    Article  Google Scholar 

  40. Xia, Z., Gu, Q., Xiong, L., Zhou, W., Weng, J.: Privacy-preserving image retrieval based on additive secret sharing. arXiv Preprint (2020). arXiv:2009.06893

  41. Yang, Y., Lin, Y., Li, Z., Zhao, L., Yao, M., Lai, Y., Li, P.: GOOSEBT: a programmable malware detection framework based on process, file, registry, and com monitoring. Comput. Commun. 204, 24–32 (2023)

    Article  Google Scholar 

Download references

Acknowledgements

We extend our deepest gratitude to everyone who has been and continues to be involved in CT research. The research is supported by the National Natural Science Foundation of China (Grant Nos. 62272199).

Author information

Authors and Affiliations

  1. College of Cyber Security, Jinan University, Guangzhou, 510632, China

    Qianheng Yang, Yuer Yang, Rongrong Guo, Huiguang Xian, Yifeng Lin & Wuzheng Tan

  2. Department of Computer Science, The University of Hong Kong, Pok Fu Lam, Hong Kong

    Yuer Yang, Shiyuan Xu, Yifeng Lin, Xue Chen & Siu-Ming Yiu

Authors
  1. Qianheng Yang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yuer Yang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Shiyuan Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Rongrong Guo
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Huiguang Xian
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Yifeng Lin
    View author publications

    You can also search for this author in PubMed Google Scholar

  7. Xue Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  8. Wuzheng Tan
    View author publications

    You can also search for this author in PubMed Google Scholar

  9. Siu-Ming Yiu
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

Q. Y., Y. Y., and S. X. wrote the main manuscript. R. G., H. X., Y. L., and X. C. prepared figures and tables. Q. Y. and Y. Y. conducted the experiments. Q. Y., Y. Y., and Y.L. revised the manuscript in the first revision round. W. T. and S.M. Y. supervised the whole team. All authors reviewed the manuscript.

Corresponding authors

Correspondence to Wuzheng Tan or Siu-Ming Yiu.

Ethics declarations

Competing interests

The authors declare no competing interests.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Yang, Q., Yang, Y., Xu, S. et al. PPCT: Privacy-Preserving Contact Tracing Using Concise Private Set Intersection Cardinality. J Netw Syst Manage 32, 97 (2024). https://doi.org/10.1007/s10922-024-09865-1

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s10922-024-09865-1

Keywords

Search

Navigation