key: cord-0486509-gdsuhbf6 authors: Singh, Abhishek; Raskar, Ramesh title: Verifiable Proof of Health using Public Key Cryptography date: 2020-12-04 journal: nan DOI: nan sha: d489ac72f3986e287c7e3839ba592a71b9e43205 doc_id: 486509 cord_uid: gdsuhbf6 In the current pandemic, testing continues to be the most important tool for monitoring and curbing the disease spread and early identification of the disease to perform health-related interventions like quarantine, contact tracing and etc. Therefore, the ability to verify the testing status is pertinent as public places prepare to safely open. Recent advances in cryptographic tools have made it possible to build a secure and resilient digital-id system. In this work, we propose to build an end to end COVID-19 results verification protocol that takes privacy, computation, and other practical concerns into account for designing an inter-operable layer of testing results verification system that could potentially enable less stringent and more selective lockdowns. We also discuss various concerns encompassing the security, privacy, ethics and equity aspect of the proposed system. The economy is one of the sector that has suffered enormous negative impact during this pandemic. One of the major reason for such a disruption is the lockdown policy enforced by governments causing all the public places to shut down. While such a policy is important for curbing the disease spread, its side effects manifest in different forms including financial loss, mental health, economic collapse and etc. In this work, we describe a cryptographic scheme through which citizens, healthcare authorities, and public place owners can work collaboratively by restricting access to infectious individuals for public places. Such a scheme would allow less stringent and more selective lockdowns and a potential reduction in the disease spread by cutting down infection chain at the places of public gathering. Previous works [1, 2] in the analysis of disease spread have shown the possibility of such public places turning into a super spreading zone. Therefore, such a health passport would benefit the current overarching goal of managing the economy and disease spread simultaneously. That being said, it is important to highlight that the design and deployment of such a technique should be done after discussion with various experts including policy makers, epidemiologists, privacy experts, and ethicists. Hence, the scope of this paper is only about the design of the cryptographic scheme and not a final end to end solution. There has been a reasonable number of prior work in this area that aim to build a similar health passport for verified access. A majority of them borrow technology from the blockchain technology and verifiable credentials. However, as we show in our section 3, our proposed protocol does not require any heavyweight computing infrastructure and it requires a minimal communication with the internet for the protocol to operate successfully. One of the drawback of such a design is its limited capability to only verify a testing or immunization result and not support any arbitrary credential verification or transaction, which we consider is sufficient under the scope of the current pandemic. The proposed protocol in this work offers threefold advantage: • It uses simple widely known yet secure cryptographic primitives. • It is designed to be integrated with the existing testing ecosystem in an inter-operable fashion. • The protocol addresses the challenges that are relevant to the practical deployment such as offline verification and health status forgery. There has been a significant work in the domain of verifiable ecosystem of credentials using digital tools. The most notable work is the verifiable credential standard described by W3C [3] . Many existing frameworks utilize the similar setup of verifiable credential [4] . COVID-19 credentials initiative [5] is a consortium of multiple big companies and groups working in the domain of verifiable credential working towards building technology around addressing some of the use-cases for COVID-19. There are many other frameworks proposed recently [6] [7] [8] [9] [10] [11] . However, this line of work also comes with criticism [12] . While our work is inspired by all of these initiatives, the key difference is the underlying protocol used in our work that does not require any distributed ledger or a verifiable credential type of setup but simply relies on public key cryptography. Furthermore, we aim to address some of the practical problems associated with these verifiers in a realistic setting such as offline verification, integration with testing site and the PHA server for a given jurisdiction. We are able to obtain such advantages without using any sophisticated cryptographic primitives because of the assumption of tightly couple ecosystem which these verifiable credentials based work do not assume. This paper draws some of the ideas from the work done in cryptography for message authentication and signatures [13] [14] [15] . There are several protocols that allow designing authentication to message and signature schemes such as HMACs [16] . However, these works do not suffice for preventing forgery while also performing offline verification. Here, by forgery, we refer to the situation where multiple users carry same verified information and show the same verifiable proof even though it does not belong to them. Either forgery is resolved by exchanging message with the issuer or by offline authentication algorithms where message. We solve both of the problem in our protocol by allowing the server to embed user identifier (user's public key) in the signed copy of result. This prevents the forgery of the message as long as the private key of the user is not leaked. At a high level, a health based verification system involves three parties issuer, holder, and verifier. For the use-case of COVID-19, the issuer is a public healthcare authority (PHA) that usually sets up a testing site and issues the test results to individuals. The individuals here act as holder of the result and want the access to public places based on their health status. Finally, the verifier verifies the health status of the holder by inspecting the health status of the individuals. The goal of the verifier is to only authorize access to those individual who satisfy the following requirements - • Carry a health status that belongs to holder • The health status should be authorized by issuer • The health status contains appropriate result(ex -negative test in the last 7 days). We use ⊕ to denote the XOR operation. Whenever a tuple of data is exchanged, all of the elements of the tuple are in the format (x, y, z) where x, y and z are separate messages to be exchanged. Under the given setup we refer the holder as A and issuer as PHA. • F1: The verifier should be able to verify the health status without requiring an internet connection. • F2: The holder should be able to present the health status without requiring an internet connection. • F3: The verification process should be quick and computationally efficient. • F4: No two users should be able to share the health status with each other and gain the access through verifier fraudulently. • P1: The verifier should only be able to query the health status of an individual that presents health status with consent. • P2: The verifier should not be able to learn any other information about the holder except their health status. • P3: Any individual should not be able to query the health status of any arbitrary user except only the user who queries its own entry. • P4: Existence of an individual on the public health database should not be identifiable. There are two categories of threat at a high level in this proposed protocol. The first category refers to forgery where a user attempts to bypass the verification. This could happen by either altering the content in result status R (modifying positive test as a negative test or changing the last tested timestamp to a permissible one). This can also happen if user can obtain someone else's R. The second category is associated with privacy. Under this threat model the verifier acts as a semi-honest adversary attempting to reveal more information about the holder. This could either happen through revealing more information during verification stage or post verification stage where the verifier attempts to query the data on server through information learned during verification. Under our threat model, no two parties are colluding with each other at any point of time. However, any arbitrary number of verifiers or holders can collude among each other to leak additional information holder or to bypass verifier respectively. Furthermore, in this proposed protocol, the issuer is a trusted entity which is an obvious assumption to make because the issuer knows the result and identity of every holder from the beginning of the testing phase and for the scope of this paper, issuer is Public Healthcare Authority. In line with that, the protocol assumes that issuer's public key PHA pk is known to everyone. While the proposed protocol is agnostic to the underlying encryption algorithm as long as it supports public and private key cryptography. For the sake of description, we base our system on el-gamal [17] which is a well known public key crypto system. We define the protocol as follows: • KeyGen(G, q, g) → sk, pk: Construct group G of order q with generator g. The private key is an integer e randomly sampled from the group G. The public key is g e and the group G. • Encrypt(m, sk) → (c 1 , c 2 ): a third party can encrypt a message m by first sampling random d from the group G and computing c 1 ≡ g d and c 2 ≡ m · (g e ) d . • Decrypt((c 1 , c 2 ), pk) → m: is performed by the receiving party only if they know the private key e as m ≡ (c 2 ) · ((c 1 ) e ) −1 (mod(n)). The inverse can be easily computed by using the value of q. The User downloads the data by querying PHA server with sess_id. The PHA server downloads C from the server which contains the health status in encrypted format The User shows QR code which has C multiplied by current timestamp and also provide its own public key and ot_id. The verifier decrypts Q, verifies timestamp and then decrypts C and then verify A_pk The User sets up a public and private key in the beginning and then uses one time id (ot_id) for every visit to the testing site. The testing site scans the tuple and provides sess_id A Figure 1 : Protocol description: The above user journey diagram illustrates the protocol and message exchanges. Note that the protocol assumes that the testing site and the PHA server coordinate together to obtain every tested user's information and process it accordingly. While the above definition suits well for the protocol, there are known issues with the plain El-gamal system [17] for which it could be substituted with secure and more efficient public key based protocols. Setup phase • The issuer PHA performs KeyGen operation to obtain PHA pk and PHA sk . PHA pk can be released publicly or given to business owners in a secure manner based on the access control policy on who can do verification. • The holder A performs KeyGen operation to gather A pk and A sk . A sk is securely stored in a trusted enclave which even A can not access through system layer security but can only be used by authorized app to perform encryption. • A goes to a testing station and generates a one time identifier ot_id and provides a QR-code containing information (ot_id, A pk ) • Testing site generates a unique sess_id for A and provide it to them through QR-code or any other message exchange service. The testing site locally stores the tuple (ot_id, A pk , sess_id). • This sess_id is used to carry the testing specimen around and used as the primary identifier for the testing result as well as specimen. • Once the testing result data R is ready for the user A the testing site sends (sess_id, ot_id, A pk , R) to the PHA. Based on the result, the PHA can take additional action like contact tracing and etc. or upload the result to the PHA server described as follows. • The PHA uploads the following encrypted result C = Encrypt(PHA sk ⊕ ot_id, (R, A pk )) and hosts it as a tuple (sess_id, C). • A downloads C by sending sess_id to the server. • A performs the following computation to decrypt the result R, A pk = Decrypt(PHA pk ⊕ ot_id, C) • A verifies A pk received from the server and interprets the result. • A computes time based signature S by performing S = encrypt(C · t, A sk ) where t is the current timestamp, rounded off to account for clock drift. • A computes QR code as follows Q = (S, ot_id, A pk ) and shows it to the verifier V • V generates t locally and computes its multiplicative inverse t −1 to obtain C • V verifies the identity of A by verifying the signature S = Decrypt(A pk , C × t) The overall security of the protocol not only depends on the security offered by the cryptographic mechanisms but also on the assumption that a user A can not share its secret key sk with other users otherwise other users can use the same key to use A's health status. This is a reasonable assumption given that key management can be performed these days on smartphone using secure enclaves [18] . In the Section 3.3 we discuss various functional and privacy requirements of the protocol. P1 and P3 are enforced by making sure that C is not known to any curious user unless they hold A pk as well as ot_id for the given record. P2 requirement is met by ensuring that the health status R is not tied to any other additional health of the user. For practical purposes, the issuer might want to communicate more health information to the user which could be performed by appending an additional layer of encryption to sensitive set of health information that does not need to be shared with the verifier. P4 requirement is attained through the secrecy and ephemeral nature of the ot_id and sess_id. The computation in this protocol does not involve any heavyweight computation and only relies on a single public key encryption decryption by the holder for every verification round. Since the verification is supposed to happen only when a user visits a public place or business, two subsequent computation will have a sufficient time window between them making it practically possible. For n users the issuer has to perform n encryption that requires two exponentiation operation for el-gamal [17] and decryption requires one exponentiation. Exponentiation operation for m bits of data requires complexity of O(m log23 ) under Karatsuba algorithm. Furthermore, some of this exponentiation operations could be pre-computed because of the el-gamal algorithm and all n encryptions are independent of each other making the protocol parallelize at a linear scale. For m bits of information, the key expansion of el-gamal [17] algorithm used in the proposed protocol would introduce the message complexity of 2 · m. As shown in the Figure 1 , message exchange mostly involves exchange of identifiers and ciphertext, hence, communication is always linear with the size of message m and small enough to be communicated with a single QR-code. In the message exchange performed in the verification phase, the total bits required for messaging can be given as 2 · m + |A pk | + |ot_id| where |A pk | refers to the size of the public key which is typically 2048 bits and |ot_id| refers to the one time identifier which is usually 256 bits. Overall, this information can fit within a QR-code and hence can be communicated from holder to verifier in a single round. In addition to this, our protocol requires minimum interaction with an online server by mandating functional requirements F1 and F2. The idea of restricted access based on either a negative test result or . The letter [19, 20] from EFF and ACLU California highlights several criticism for the California's bill [21] for the use of verifiable credential technology [3] to develop immunity passport. Privacy leakage Most of the privacy concerns have been discussed in the section 4 and one of the central point for leaking privacy and bypassing the verification security is the secrecy of the secret key of the holder. This is possible to obtain if the phone is jailbroken or rooted which might be the case for some of the phones especially the ones with old unupdated operating systems. Furthermore, this could encourage the work in attacking the system layer of security, however, it has been becoming increasingly difficult with the latest operating systems and the app can enforce a minimum version of operating system to enforce higher security. The other possibility with this protocol is that the result R of a user is shared permanently with the verifier which might not be a good idea if the result R contains other sensitive information about the user as well. Hence, in our proposed protocol, we keep it limited to only the test result of a user that does not hold much of significance once the pandemic is over. Equity The proposed protocol relies on the smartphones that inevitably would lead to equity concerns. This would be even more substantiated in the developing countries. Hence we want the stakeholders to be cognizant of this aspect of the proposed protocol. The ongoing direction of this work is to adjust the verification scheme such that it is supported by a paper based QR-code which can be given to the users who do not have access to the smartphones. Behavioral changes One of the major unintended consequence of a health status based access could be to attain immunity through risky pathways. Such a behavioral change could lead to more infection spread and fatalities due to more number of people exposing themselves in order to get access to public places for their own self-interest or financial reasons. This is one of the unintended consequence of the restricted access control that can not be addressed entirely by the proposed technology. Notwithstanding the above mentioned points, this work does not advocate for restricting access to individuals who are not able to present their testing results due to different reasons. Rather, such a system could be used for data collection and retrospective analysis for future interventions. One such example is public places increasing their risk level if the total percentage of people entering the venue and showing the digital passport decline. A majority of the community discussion around the restricted access has been on a binary level of whether to use it completely or not at all. We hope that such systems can be introduced gradually and mindfully to the existing ecosystem such that it allows decision making in data-driven manner and allow the technology to mature. In this work, we present a protocol for testing verification for curbing the COVID-19 disease spread by restricting the access to only recently tested individuals. The focus of this work is not on the actual deployment but rather protocol design that circumvents some of the practical issues which existing systems have. We also discuss various unintended consequences of such a platform and in what ways it can be addressed. This work does not advocate for immunity passports but rather verification of testing results that would encourage testing and reduce the chance of infectious individuals entering a public place. Mobility network models of COVID-19 explain inequities and inform reopening Indoor transmission of SARS-CoV-2. medRxiv W3C. Verifiable Credentials Data Model Digital Health Passports Using Blockchain -Use case on international tourism during the COVID-19 pandemic. en CCI. COVID-19 Credentials initiative Differentially Private Health Tokens for Estimating COVID-19 Risk Framework for a DLT Based COVID-19 Passport Secure AntiBody Certificates for COVID-19 Digital Health Passports Using Blockchain -Use case on international tourism during the COVID-19 pandemic COVID-19 Antibody Test / Vaccination Certification: There's an app for that Vision: A Critique of Immunity Passports and W3C Decentralized Identifiers | SpringerLink Rsa Signature: Behind The Scenes Message recovery for signature schemes based on the discrete logarithm problem in Workshop on the Theory and Application of of Cryptographic Techniques Deterministic usage of the digital signature algorithm (DSA) and elliptic curve digital signature algorithm (ECDSA) HMAC: Keyed-hashing for message authentication A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms in Advances in Cryptology Storing Keys in the Secure Enclave | Apple Developer Documentation https://developer. apple . com / documentation / security / certificate _ key _ and _ trust _ services / keys / storing _ keys_in_the_secure_enclave 2020-05-13 -letter from EFF and ACLU re AB No to California Bill on Verified Credentials of COVID-19 Test Results en Califronia Bill Text -AB-2004 Medical test results: verification credentials