During the pandemic, the limited functionality of existing privacy-preserving contact tracing systems highlights the need for new designs. Wang et al. proposed an environmental-adaptive framework (CSS ’21) but failed to formalize the security. The similarity between their framework and attribute-based credentials (ABC) inspires us to reconsider contact tracing from the perspective of ABC schemes. In such schemes, users can obtain credentials on attributes from issuers and prove the credentials anonymously (i.e., hiding sensitive information of both user and issuer). This work first extends ABC schemes with auditability, which enables designated auditing authorities to revoke the anonymity of particularissuers. For this purpose, we propose an “auditable public key (APK)” mechanism that extends the updatable public key by Fauzi et al. (AsiaCrypt ’19). We provide formal security definitions regarding auditability and build our auditable ABC scheme by adding a DDH-based APK to Connolly et al.’s ABC construction (PKC ’22). Note that the APK mechanism can be used as a plug-in for other cryptographic primitives and may be of independent interest. Finally, regarding contact tracing, we refine Wang et al.’s framework and present a formal treatment that includes security definitions and protocol construction. An implementation is provided to showcase the practicality of our design.

1. 1.

   Silde and Strand [36] proposed a contact tracing system based on anonymous tokens,i.e., an anonymous credential variant that does not support attributes.

2. 2.

   Notably, game-based and simulation-based security definitions of contact tracing systems have been proposed in [4,18], respectively. This work will focus on the game-based ones because we proceed from the perspective of ABC schemes with game-based definitions.

3. 3.

   We will also give a DDH-based construction in Appendix C. There, we show an example that utilizes the DDH-based APK to extend the famous B(G)LS signature scheme [7,8].

4. 4.

   Users are required to report necessary data to decide if they are closed enough to be considered involved in a contact. The reveal of such data may also have privacy impacts. However, we found it hard to quantify such impacts and left this problem for further consideration.

Authors and Affiliations

1. Department of Mathematical and Computing Science, School of Computing, Tokyo Institute of Technology, W8-55, 2-12-1 Oookayama, Meguro-ku, Tokyo-to, Japan

   Pengfei Wang, Xiangyu Su, Mario Larangeira & Keisuke Tanaka

2. Input Output, Global, Singapore, Singapore

   Mario Larangeira

Corresponding authors

Correspondence toPengfei Wang orXiangyu Su.

Editors and Affiliations

1. New York University Abu Dhabi, Abu Dhabi, United Arab Emirates

   Christina Pöpper

2. Radboud University Nijmegen, Nijmegen, The Netherlands

   Lejla Batina

A The Necessity of Enhancing Contact Tracing Systems

This work considers the enhancement of contact tracing systems due to the following two epidemiology findings: (1) modes of transmission (droplet and airborne); (2) environmental factors (temperature, humidity, air velocity, etc.).

Droplet transmission refers to the infections caused by viruses ejected with droplets by sneezes or coughs; whereas, airborne transmission means that infections are caused by floating liquid drops carrying viruses suspended in the air [20]. Hence, “close contact” should be defined differently in the two transmission modes,i.e., droplet transmissible viruses require face-to-face contact; whereas, airborne transmissible viruses only require people to come into the region of the floating virus during their lifespan. Conventional contact tracing systems utilize Bluetooth Low Energy (BLE) technology to trace face-to-face contact. In contrast, to the best of our knowledge, only Wang et al. [37] considered the airborne transmission with their discrete-location-tracing setting (DLT). Intuitively, the DLT setting records users’ relative and absolute positions to decide close contact. However, due to the inherent decentralization of their system (i.e., users are designed to issue their own contact records), they failed to achieve meaningful integrity guarantees for the DLT setting.

As mentioned above, virus distribution,e.g., lifespan and region size, affects the infectiousness of viruses. Epidemiology research [15,19,30] concludes that virus distribution depends on environmental factors, including temperature, humidity, air velocity, etc. However, in conventional contact tracing systems, BLE usually scans according to predetermined parameters,e.g., interval and radius. The mismatch between virus distribution and scan parameters may cause overwhelmingly false-positive records, burdening the medical system in real-life. Therefore, we consider that it is necessary to filter records according to environmental factors for practical contact tracing systems.

A problem caused by including more data (i.e., position and environmental factors) is that revealing these data may result in the identification of users. Therefore, this work embeds them into the attributes of an attribute-based credentials (ABC) scheme. Anonymity and selective showing capability of ABC schemes (from [17,25] and our Construction 2) empower users to reveal only necessary attributes to verifiers while keeping other attributes secret,i.e., medical agencies and other users (including the issuer) cannot learn more than what is revealed duringthe showing of credentials^Footnote4. Potentially, we can further tweak the set-commitment scheme [25] (mentioned in Sect. 2) to enable the proof of knowledge of the commitment content, hence, achieving blind issuance as shown in [9]. The blind issuance capability can prevent issuers from learning users’ attributes duringthe issuance of credentials.

B The SPS-EQ Scheme from [17]

We show the SPS-EQ scheme given by [17] with respect to a fully adaptive NIZK argument\(\textsf{NIZK}\overset{\varDelta }{=}(\textsf{PGen},\textsf{PPro},\textsf{PSim},\textsf{PRVer},\textsf{PVer},\textsf{ZKEval})\). It satisfies correctness, the EUF-CMA, and the property of Perfect Adaption of Signatures with respect to Message Space.

Construction 4

(SPS-EQ Scheme\(\textsf{SPSEQ}\)). The algorithms are as follows.

• \(\textsf{Setup}(1^\lambda )\). Run\(\textsf{BG}\leftarrow \textsf{BGGen}(1^\lambda )\) and sample matrices\(\textbf{A},\textbf{A}_0,\textbf{A}_1\overset{\$}{\leftarrow }\mathcal {D}_1\) from matrix distribution. Generate a common reference string and trapdoor for the malleable NIZK argument with\((\textsf{crs},\textsf{td})\leftarrow \textsf{NIZK}.\textsf{PGen}(1^\lambda ,\textsf{BG})\). Return\(\textsf{pp}=(\textsf{BG},[\textbf{A}]_2,[\textbf{A}_0]_1,[\textbf{A}_1]_1,\textsf{crs},\ell )\);

• \(\textsf{KGen}(\textsf{pp})\). Sample\(\textbf{K}_0\overset{\$}{\leftarrow }\mathbb {Z}_p^{2\times 2},\textbf{K}\overset{\$}{\leftarrow }\mathbb {Z}_p^{\ell \times 2}\). Compute\([\textbf{B}]_2=[\textbf{K}_0]_2[\textbf{A}]_2\) and\([\textbf{C}]_2=[\textbf{K}]_2[\textbf{A}]_2\). Set\(\textsf{sk}=(\textbf{K}_0,\textbf{K})\) and\(\textsf{pk}=([\textbf{B}]_2,[\textbf{C}]_2)\). Return\((\textsf{sk},\textsf{pk})\);

• \(\textsf{Sign}(\textsf{pp},\textsf{sk},[\textbf{m}]_1)\). Sample\(r_1,r_2\overset{\$}{\leftarrow }\mathbb {Z}_p\). Compute\([\textbf{t}]_1={[\textbf{A}_0]_1}{r_1}\) and\([\textbf{w}]_1={[\textbf{A}_0]_1}{r_2}\). Compute\(\textbf{u}_1={\textbf{K}_0^\top }[\textbf{t}]_1+{\textbf{K}^\top }[\textbf{m}]_1\) and\(\textbf{u}_2={\textbf{K}_0^\top }[\textbf{w}]_1\). Generate proof with\((\varOmega _1,\varOmega _2,[z_0]_2,[z_1]_2,Z_1)\leftarrow \textsf{NIZK}.\textsf{PPro}(\textsf{crs},[\textbf{t}]_1,r_1,[\textbf{w}]_1,r_2)\). Set\(\sigma =([\textbf{u}_1]_1, [\textbf{t}]_1,\varOmega _1,[z_0]_2,[z_1]_2,Z_1)\) and\(\tau =([\textbf{u}_2]_1, [\mathbf {u_2}]_1,[\textbf{w}]_1,\varOmega _2)\). Return\((\sigma ,\tau )\);

• \(\textsf{ChgRep}(\textsf{pp},[\textbf{m}]_1,(\sigma ,\tau ),\mu ,\rho ,\textsf{pk})\). Parse\(\sigma =([\textbf{u}_1]_1, [\textbf{t}]_1,\varOmega _1,[z_0]_2,[z_1]_2,Z_1)\) and\(\tau \in \{([\textbf{u}_2]_1, [\textbf{w}]_1,\varOmega _2),\perp \}\). Let\(\varOmega =(\varOmega _1,\varOmega _2,[z_0]_2,[z_1]_2,Z_1)\). Check proof with\(\textsf{NIZK}.\textsf{PVer}(\textsf{crs},[\textbf{t}]_1,[\textbf{w}]_1,\varOmega )\). Check if\(e([\textbf{u}_2]_1^\top ,\textbf{A}]_2)=e([\textbf{w}]_1^\top ,\textbf{B}]_2)\) and\(e([\textbf{u}_1]_1^\top ,\textbf{A}]_2)=e([\textbf{t}]_1^\top ,\textbf{B}]_2)+e([\textbf{m}]_1^\top ,\textbf{C}]_2)\). Sample\(\alpha ,\beta \overset{\$}{\leftarrow }\mathbb {Z}_p^*\). Compute\([\mathbf {u^\prime }_1]_1=\rho (\mu [\textbf{u}_1]_1+\beta [\textbf{u}_2]_1)\) and\([\mathbf {t^\prime }]_1=\mu [\textbf{t}]_1+\beta [\textbf{w}]_1=[\textbf{A}_0]_1(\mu r_1+\beta r_2)\). And for\(i\in \{0,1\}\), compute\([z_i^\prime ]_2=\alpha [z_i]_2, [\mathbf {a^\prime }_i]_1=\alpha \mu [\textbf{a}_i^1]_1+\alpha \beta [\textbf{a}_i^2]_1, [d_i^\prime ]_2=\alpha \mu [d_i^1]_2+\alpha \beta [d_i^2]_2\). Set\(\varOmega ^\prime =(([\mathbf {a^\prime }_i]_1, [d_i^\prime ]_2, [z_i^\prime ]_2)_{i\in \{0,1\}},\alpha Z_1)\). Set\(\sigma ^\prime =([\mathbf {u^\prime }_1]_1,[\mathbf {t^\prime }]_1,\varOmega ^\prime )\). Return\((\mu [\textbf{m}]_1,\sigma ^\prime )\);

• \(\textsf{Verify}(\textsf{pp},(\rho ,\textsf{pk}),[\textbf{m}]_1,(\sigma ,\tau ))\). Parse\(\sigma =([\textbf{u}_1]_1, [\textbf{t}]_1,\varOmega _1,[z_0]_2,[z_1]_2,Z_1)\) and\(\tau \in \{([\textbf{u}_2]_1, [\textbf{w}]_1,\varOmega _2),\perp \}\). Check proof\(\varOmega _1\) with\(\textsf{NIZK}.\textsf{PRVer}(\textsf{crs},[\textbf{t}]_1,\varOmega _1,[z_0]_2,[z_1]_2,Z_1)\) and check if\(e([\textbf{u}_1]_1^\top ,\textbf{A}]_2)=e([\textbf{t}]_1^\top ,\textbf{B}]_2)+e([\textbf{m}]_1^\top ,\textbf{C}]_2)\). If\(\tau \ne \perp \), then check proof\(\varOmega _2\) with\(\textsf{NIZK}.\textsf{PRVer}(\textsf{crs},[\textbf{w}]_1,\varOmega _2,[z_0]_2,[z_1]_2,Z_1)\) and check if\(e([\textbf{u}_2]_1^\top ,\textbf{A}]_2)=e([\textbf{w}]_1^\top ,\textbf{B}]_2)\).

Definition 17 (Correctness)

An SPS-EQ scheme satisfies correctness, if for any\(\lambda >0,\ell >1\),\(\textsf{pp}\leftarrow \textsf{Setup}(1^\lambda )\), and\((\textsf{sk},\textsf{pk})\leftarrow \textsf{KGen}(\textsf{pp})\):

Definition 18 (EUF-CMA)

An SPS-EQ scheme satisfies EUF-CMA, if for any adversary that has access to a signing oracle\(\mathcal {O}_\textsf{Sign}(\textsf{sk},\cdot )\) with queries\([\textbf{m}]_i\in \textsf{Q}\), the following probability is negligible of\(\lambda \) for any\(\lambda >0,\ell >1\) and\(\textsf{pp}\leftarrow \textsf{Setup}(1^\lambda )\):

Definition 19 (Perfect Adaption of Signatures with respect to Message Space (under Malicious Keys in the Honest Parameters Model))

An SPS-EQ scheme over a message space\(\mathcal {S}_\textbf{m}\subseteq (\mathbb {G}_i^*)^\ell \) perfectly adapts signatures with respect to the message space, if for all tuples\((\textsf{pp},[\textsf{pk}]_j,[\textbf{m}]_i,(\sigma ,\tau ),\mu ,\rho )\) such that\(\textsf{pp}\leftarrow \textsf{Setup}(1^\lambda ),[\textbf{m}]_i\in \mathcal {S}_\textbf{m}\),\(\mu ,\rho \in \mathbb {Z}_p^*\), and\(\textsf{Verify}(\textsf{pk},[\textbf{m}]_i,(\sigma ,\tau ))=1\), we have the output\(([\mu \cdot \textbf{m}]_i,\sigma ^*)\leftarrow \textsf{ChgRep}([\textbf{m}]_i,(\sigma ,\tau ),\mu ,\rho ,[\textsf{pk}]_j)\) where\(\sigma ^*\) is arandom element in the signature space such that\(\textsf{Verify}([\rho \cdot \textsf{pk},\mu \cdot \textbf{m}]_i,\sigma ^*)=1\).

C Extending the BLS Signature [8] with APK

This section shows an example that utilizes a DDH-based APK construction as a plug-in pool in the BLS signature scheme [8]. Let\(\textsf{BGGen}(1^\lambda )\) be the bilinear group generator that outputs\(\textsf{BG}=(p,\mathbb {G}_1,\mathbb {G}_2,\mathbb {G}_T,P_1,P_2,e)\) as shown in Sect. 2. The DDH problem (in group\(\mathbb {G}_2\))-based APK construction is as follows.

Construction 5

(DDH-Based APK\(\textsf{APK}_\textrm{DDH}\)). Let\(\textsf{BG}=(p,\mathbb {G}_1,\mathbb {G}_2,\mathbb {G}_T,P_1,P_2,e)\) be the output of the bilinear group generator\(\textsf{BGGen}(1^\lambda )\). The algorithms of APK are as follows.

• \(\textsf{KGen}(\textsf{BG})\): Sample\(\textsf{ak},\textsf{sk}_0\overset{\$}{\leftarrow }\mathbb {Z}_p\). Set\(\textsf{sk}_1=\textsf{ak}\cdot \textsf{sk}_0\). Then, compute\(\textsf{pk}_0=\textsf{sk}_0\cdot P_2\) and\(\textsf{pk}_1=\textsf{sk}_1\cdot P_2\). Finally, set\(\textsf{sk}=(\textsf{sk}_0,\textsf{sk}_1),\textsf{pk}=(\textsf{pk}_0,\textsf{pk}_1)\) and output\((\textsf{sk},\textsf{ak},\textsf{pk})\);

• \(\textsf{Update}(\textsf{pk};r)\): Parse\(\textsf{pk}=(\textsf{pk}_0,\textsf{pk}_1)\). Sample\(r\overset{\$}{\leftarrow }\mathbb {Z}_p\) and compute\(\textsf{pk}_0^\prime =r\cdot \textsf{pk}_0,\textsf{pk}_1^\prime =r\cdot \textsf{pk}_1\). Output\(\textsf{pk}^\prime =(\textsf{pk}_0^\prime ,\textsf{pk}_1^\prime )\);

• \(\textsf{VerifyKP}(\textsf{sk},\textsf{pk}^\prime ,r)\): Parse\(\textsf{sk}=(\textsf{sk}_0,\textsf{sk}_1)\) and\(\textsf{pk}^\prime =(\textsf{pk}_0^\prime ,\textsf{pk}_1^\prime )\). Output 1 if\(\textsf{pk}_0^\prime =r\cdot \textsf{sk}_0\cdot P_2\wedge \textsf{pk}_1^\prime =r\cdot \textsf{sk}_1\cdot P_2\), or 0 otherwise;

• \(\textsf{VerifyAK}(\textsf{sk},\textsf{ak})\): Parse\(\textsf{sk}=(\textsf{sk}_0,\textsf{sk}_1)\). Output 1 if\(\textsf{sk}_1 = \textsf{ak}\cdot \textsf{sk}_0\), or 0 otherwise;

• \(\textsf{Audit}(\textsf{ak},\textsf{pk}^\prime ,\textsf{pk})\): Parse\(\textsf{pk}^\prime =(\textsf{pk}_0^\prime ,\textsf{pk}_1^\prime ),\textsf{pk}=(\textsf{pk}_0,\textsf{pk}_1)\). Output 1 if\(\textsf{pk}_1=\textsf{ak}\cdot \textsf{pk}_0\wedge \textsf{pk}_1^\prime =\textsf{ak}\cdot \textsf{pk}_0^\prime \), or 0 otherwise.

Recall the BLS signatures [8], let\(\textsf{H}: \mathcal {S}_\textbf{m}\rightarrow \mathbb {G}_1\) be a cryptographic hash function where\(\mathcal {S}_\textbf{m}\) denotes the message space. For simplicity, we omit the algorithms for aggregation to focus on auditability. The integration works as follows.

Construction 6

(BLS with APK). Let\(\textsf{BG}=(p,\mathbb {G}_1,\mathbb {G}_2,\mathbb {G}_T,P_1,P_2,e)\) be the output of the bilinear group generator\(\textsf{BGGen}(1^\lambda )\). Let\(\textsf{H}: \mathcal {S}_\textbf{m}\rightarrow \mathbb {G}_1\) be a cryptographic hash function where\(\mathcal {S}_\textbf{m}\) denotes the message space. Let\(\textsf{APK}_\textrm{DDH}=(\textsf{KGen},\textsf{Update},\textsf{VerifyKP},\textsf{VerifyAK},\textsf{Audit})\) be a DDH-based APK mechanism. The algorithms of BLS with APK are as follows.

• \(\textsf{KGen},\textsf{VerifyKP},\textsf{VerifyAK},\textsf{Audit}\) are the same as in\(\textsf{APK}_\textrm{DDH}\);

• \(\textsf{Sign}(\textsf{sk},m)\): Parse\(\textsf{sk}=(\textsf{sk}_0,\textsf{sk}_1)\) and output\(\sigma =\textsf{sk}_1\cdot \textsf{H}(m)\in \mathbb {G}_1\);

• \(\textsf{Verify}(\textsf{pk},m,\sigma )\): Parse\(\textsf{pk}=(\textsf{pk}_0,\textsf{pk}_1)\) and output 1 if\(e(\sigma ,P_2)=e(\textsf{H}(m),\textsf{pk}_1)\), or 0 otherwise;

• \(\textsf{Update}(\textsf{pk},\sigma ;r)\): Output\((\textsf{pk}^\prime ,\sigma ^\prime )\overset{\varDelta }{=}(\textsf{APK}_\textrm{DDH}.\textsf{Update}(\textsf{pk};r),r{\cdot } \sigma )\).

Since the EUF-CMA security of the (type-3) BLS signature is proven under the co-CDH assumption [7], and the APK given in Construction 5 considers the DDH problem in\(\mathbb {G}_2\), it is convenient to assume the SXDH assumption [2] to hold for\(\textsf{BGGen}\) to prove the EUF-CMA security of our extended BLS construction (Construction 6).

Reprints and permissions

© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG

Policies and ethics