The COVID-19 pandemic has severely affected daily life and caused a great loss to the global economy. Due to the very urgent need for identifying close contacts of confirmed patients in the current situation, the development of automated contact tracing app for smart devices has attracted more attention all over the world. Compared with expensive manual tracing approach, automated contact tracing apps can offer fast and precise tracing service, however, over-pursing high efficiency would lead to the privacy-leaking issue for app users. By combing with the benign properties (e.g., anonymity, decentralization, and traceability) of blockchain, we propose an efficient privacy-preserving solution in automated tracing scenario. Our main technique is a combination of non-interactive zero-knowledge proof and multi-signature with public key aggregation. By means of aggregating multiple signatures from different contacts at the mutual commitment phase, we only need fewer zero-knowledge proofs to complete the task of identifying contacts. It inherently leads to the benefits of saving storage and consuming less time for running verification algorithm on blockchain. Furthermore, we perform an experimental comparison by timing the execution of signature verification with and without aggregate signature, respectively. It shows that our solution can actually preserve the full-fledged privacy protection property with a lower computational cost.

Keywords: Aggregate Signature; Blockchain; COVID-19; Privacy-preserving contact tracing; Zero-knowledge proof.

© 2022 Elsevier B.V. All rights reserved.