Building a Privacy-preserving COVID-19 Vaccine Passport
This blog post is written in cooperation with Harry Lee.
Suppose that you are going to buy a train ticket to Neverland, a country free from COVID-19. Neverland requires every traveler to be vaccine injected. How do you prove to a travel agency that you have taken the vaccine for COVID-19? You are aware of the identity theft that happened recently, due to personal information being revealed to untrusted parties. Unfortunately, it is difficult to convince that one has injected a vaccine without showing personal identifying information, such as the identity number issued by the government, the name, etc.
It is intuitive to show the agent the paper vaccination record card while covering the name. The agent, however, may not be convinced that the card is ours. Another way is to request the hospital to issue a certificate for us, claiming that we have the vaccine injected. This does not even hide our personal identifying information. Alas, we have also told the hospital that we are going to the neverland.
Is there an method to show the travel agent that we have taken the vaccine, without showing any of the identifying attributes? Indeed. Here cryptography, in particular, zero-knowledge proof come into play.
A privacy-preserving vaccine record card
In this section, we will be building a digital record card for vaccine injections. The objective here is to show the interested parties that the owner has already had the vaccine injected without showing any personal identifiable information. We will first go through the cryptographic primitives: signature proof of knowledge and Camenisch-Lysyanskaya signature.
Zero-knowledge proof (ZKP) and Signature Proof-of-Knowledge (SPK)
To begin with, let’s discuss what is a zero-knowledge proof. Assume that there are two parties, Peggy (the prover) and Victor (the verifier). Peggy wants to convince Victor that she has the knowledge of something, without revealing extra information to Victor.
For example, Peggy wants to show Victor that she is capable of solving Rubik’s cube. Victor can scramble a Rubik’s cube and give it to Peggy. If Peggy could unscramble the cube, then it is convincing for Victor that she knows how to solve Rubik’s cube. In this way, Victor does not need to know how Peggy did it, but just the fact that Peggy did it.
One mathematical example is a proof of knowledge for discrete logarithm called Schnorr’s identification scheme [1]. Owing to the discrete logarithm assumption, if we are given integers y, g and prime p such that y ≡ gˣ (mod p), it is difficult to recover the corresponding integer x. Multiple cryptographic systems make use of this fact and respectively use x and y to be the secret key and public key. In our case, Peggy wants to convince Victor that she does have a specific secret key. She and Victor will be using the following strategy to convince Victor, without actually revealing her secret key:
- Peggy picks a random integer v and sends t ≡ gᵛ (mod p) to Victor.
- Victor picks a random integer c, as a challenge, and sends it to Peggy.
- Peggy computes r = v − cx and sends to Victor.
- Victor verifies if t ≡ gʳyᶜ (mod p).
If it holds, then Victor is convinced that Peggy has the secret x, while Victor does not know anything about x at all. The proof of discrete logarithm could be mathematically written as PK{(x): y ≡ gˣ (mod p)}.
Signature Proof-of-Knowledge (SPK) is an extension of zero-knowledge proofs. It employs a Fiat-Shamir heuristic [2] to make the above interactive proof into non-interactive. In this way, Peggy can convince Victor in one single message. To achieve this, the challenge c is no longer generated by Victor. It is decided by Peggy in a way that she has actually nothing up her sleeves. This can be written as SPK{(x): y ≡ gˣ (mod p)}(m), where m is a message that the prover wants to sign.
Camenisch-Lysyanskaya (CL) signature
To achieve the privacy-preserving goal, we need a signature scheme that supports SPK. CL signature [3] is one of the candidates and it is a group signature scheme which supports the following operations:
- [Join] Members to be admitted to the group,
- [Sign] Members should be able to sign messages,
- [Verify] Verifiers should be able to verify signatures are valid.
This can be linked to the public-key infrastructure — but the root certificate issuer signs attributes of an entity, rather than signing the entity itself.
For simplicity, we will only convey the main idea and omit minor mathematical checks. Readers should be aware that every single check is crucial in the implementation and they shall not be skipped. Suppose that we want to sign messages consisting of two attributes. A message is represented as (m₁, m₂).
To generate a public key, two large primes p and q are being selected and compute n to be the multiple of the two primes. R₁, R₂, S, Z are integers picked randomly. The public key is defined by (n, R₁, R₂, S, Z) and the secret key is p.
To sign a message (m₁, m₂), pick a random prime e and a random integer v. Compute A such that the below congruence holds, and the signature would be (A, e, v). To verify if (A, e, v) is a correct signature for (m₁, m₂), it is also suffice to check whether the same congruence holds.
In contrast to the CL signature scheme, there are more recent solutions. For example, BBS+ signature scheme [4] uses a smaller key size and is considered more efficient. Those are out of scope of this article.
ProofCL — Proving a valid signature without revealing the message
As mentioned before, CL signature supports signature proof of knowledge. In our scenario, we would like to show that we have a valid signature without showing the whole message. This can come in handy if I want to show part of the message while hiding the rest. In the following scenario, assume that we have a signature of message (m₁, m₂). Here we will be revealing only m₂ to the verifier. This can be achieved by adopting SPK in CL signature.
To prove the signature (A, e, v) while hiding m₁, the verifier need to generate a nonce η for prover to show that SPK{(e, m₁, v): “the signature is valid”}(η).
We need to first randomize our signature to unlink multiple ProofCL attempts. We can generate a signature (B, e, w) for the same message, with randomness r, as below:
Let H be a cryptographic hash function and ║ as concatenation. We can generate random e′, w′ and m₁′ and compute the challenge c by:
The proof is (e′′, w′′, m₁′′), where:
The prover then reveal m₂, along with the challenge c and the proof (e′′, w′′, m₁′′) to the verifier, so that the verifier can derive the expected challenge c′ and accept the proof if c and c′ checks out.
Combining the building blocks
We are now ready to build an anonymous vaccine identity system from the primitives. Let’s define the list of required attributes:
- a master secret key for identification,
- a list of vaccines that the owner has injected, and
- the time of injection for vaccination.
To preserve privacy, the secret key is never revealed to any verifier and only used to confirm different attributes are indeed in the same signature.
A hospital can issue CL signatures after one has injected vaccines which signs the aforementioned attributes. With a valid signature, we can generate a valid proof for her vaccine status and show it to the travel agencies. This is privacy-preserving as the recipient could hide other attributes, while still able to convince verifiers. In that way, we can still keep personal identifiable information unrevealed. Since the verification can be done remotely, this suits the current situation that social distancing is preferred.
Since SPK uses an unpredictable nonce every time, malicious parties could not eavesdrop on our proof and reuse it anywhere else. Also, since the proof requires knowledge of the private attributes, it is impossible for the others to forge a proof for you. Another property for the signature is unlinkability. Simply put, the verifiers could not cooperate to identify any of the provers.
Further applications
The privacy-preserving property can be widely adopted in applications. We will be using election and age-verification as examples.
Election
We would like to achieve the following properties for a privacy-preserving election:
- Voters need to sign up for voting.
- Voters should not be able to vote twice in an election.
- Voters should be able to remain anonymous and should not be traced in different elections.
- Adversaries should not be able to cast a ballot as another voter.
We can derive a pseudonym (a unique virtual identity) from the master secret key and the election identifier. The pseudonym is certified by the authority as it is linked to the master secret key and thus the CL signature. It can be used in an election and protect the voters’ actual identity. For the same voter, the pseudonyms used differs in different elections, which makes the ballots unlinkable. Lastly, since the master secret key is only known to the user, no one else can forge an identity.
Age verification
This can also be used to certify other attributes such as one’s age. For instance, there are age-related legislation, such as legal drinking age, in most countries. There are also online streaming services with explicit content which required the viewers to be an adult. With the above construction, we can now remotely verify users are adults without checking their identity cards. Compared to the existing methods like displaying a content warning prompt, this can better protect underage users from explicit contents.
Real-life usage
Privacy-preserving technology does not belong solely in an ivory tower. There are real-life projects that make use of it in large-scale systems. Similar concepts have been standardized into protocols, such as the IBM Identity Mixer (idemix) which is used in Hyperledger Fabric, or Direct Anonymous Attestation (DAA) which is being drafted in Fast IDentity Online (FIDO) [5] and have been used in Intel Enhanced Privacy ID (EPID) and used extensively in Intel processors for enclave attestation.
Conclusion
Privacy is not necessarily a trade-off for convenience. We have gone through the security primitives for building privacy-preserving systems and described how the technology can be used in real-life scenarios. As people are increasingly aware of security and privacy, it is confident that will be more and more privacy-preserving applications available to protect in every aspect of our lives.
Reference
- F. Hao, Ed. (2017) “RFC 8235 — Schnorr Non-Interactive Zero-knowledge Proof”
https://tools.ietf.org/html/rfc8235#section-2.2 - Amos Fiat, Adi Shimir (2000) “How To Prove Yourself: Practical Solutions to Identification and Signature Problems”
https://link.springer.com/chapter/10.1007%2F3-540-47721-7_12 - Jan Camenisch, Anna Lysyanskaya (2004) “Signature Schemes and Anonymous Credentials from Bilinear Maps”
https://www.iacr.org/archive/crypto2004/31520055/cl04.pdf - Man Ho Au, Willy Susio, Yi Mu (2008) “Constant-Size Dynamic k-TAA”
https://eprint.iacr.org/2008/136.pdf - FIDO Alliance (2018) “FIDO ECDAA Algorithm”
https://fidoalliance.org/specs/fido-v2.0-id-20180227/fido-ecdaa-algorithm-v2.0-id-20180227.html - The Associated Press (2020) “Wisconsin Won’t Get As Much COVID-19 Vaccine As Promised”
https://www.wpr.org/wisconsin-wont-get-much-covid-19-vaccine-promised
