# Privacy Preserving Revocation Proposal

*By: Mike Lodder*
*Date: 2021-07-31*

This proposal discusses the various tradeoffs and possible implementations for handling revocation checking with Verifiable Credentials, cryptographic keys, or any data while minimizing any metadata disclosed by the protocol.

## The Problem

Digital signatures are useful for proving the signer and the integrity over the messages signed. However, once generated, there is no method of *revoking* or *undoing* the signature. Instead other methods must be used.

Public Key Infrastructure (PKI) uses revocation lists where no privacy exists and all signatures and keys are checked in the clear.

Private Information Retrieval (PIR) offers a little more privacy. Instead of disclosing the single value being checked to everyone, the verifier downloads the entire list or a large subset such that an observer doesn't know exactly which value is checked. However, the actual value to check is still disclosed to a verifier.

EPID^{[1](https://eprint.iacr.org/2009/095.pdf)} maintains a list of revoked signature list that can be used to check signatures or zero-knowledge proofs (ZKPs) of signatures.

However, all of these solutions have some weaknesses.

For one thing verification is fast but to provide privacy, a large number of entries must exist and a substantial amount of entries must be retrieved (if not all of them) so that checks are oblivious to attackers and multiple presentations are linkable to verifiers.

## How things can go wrong

The goal with revocation is limit information disclosure to deter abuse. For one thing, data collectors often fail to protect the information. Second, information gets abused for inappropriate purposes. Third, information is shared without permission or with unauthorized or unvetted third parties. Even though this information isn't obviously valuable, almost all information can be useful. Companies with privacy teams also cannot monitor all possible ways information can be breached or abused.

## Metadata leaks

There are two types of data: *linked* and *linkable*. *Linked* data consists of unique identifiers or names that can be used to identify a single individual with little to no additional information. *Linkable* data can be used to identify a single individual when combined with other pieces of data like race, gender, age, job, ip address, etc. Metadata is *linkable* data about behavior and can be more valuable than personal information, but must usually be combined with lots of other *linkable* data to identify a single individual or a single *linked* datum.

With this in mind, all these approaches disclose a unique identifier with each presentation which allows verifiers to track the prover's behavior, thus *linked* data. The very act of checking for revocation yields behavioral data about themselves that individuals may not want shared.

## Prior art

Privacy preserving revocation checks are not something new.

Forward revocation lists^{[2](https://eprint.iacr.org/2016/217)} are a method where the registry owner publishes a revocation entry for each revoked element. A User presents a non-revocation proof to a Verifier who then tests the proof against every item in the list. If all matches fail, the check is deemed valid. This method requires significant computational resources from the Verifier. Implementations can require using homomorphic encryption which can require groups of unknown order.

Cryptographic Accumulators are used to prove a given element *x* belongs to some set *S* in constant time without exposing the value of *x*. To prove *x* is in set *S*, the Prover generates a membership witness *u*. Membership witness proofs are short and fast to verify and computationally infeasible to generate a false proof. Accumulator alternatives to proving set membership (or non-membership) all reveal which value is being checked in the set and thus rely on other protocols to protect *x*. Accumulators provide a simple and efficient solution to solve this problem. *x* is added to (or removed from) a constant-size accumulator *A* and proves that membership witness *u* with *x* equals accumulator *A*. A dynamic accumulator is one which allows insertion and deletion of elements, whereas a static accumulator supports neither operation (the set is fixed at the start). A universal accumulator is one which also supports proofs of non-membership. Accumulators also represent the entire set of elements as a fixed size value which enables efficient storage and proofs for verifying parties. The biggest drawback to accumulators happens when an accumulator is updated. Prover's must update their witnesses to be able to produce valid proofs. Witness updates come in two forms: applying deltas or petitioning the accumulator manager for a new witness. Applying deltas leaks some privacy because the holder must disclose the last time they updated and is penalized for not updating often enough by the need to apply more deltas. Petitioning the manager for a new witness also leaks some privacy using existing methods because the holder discloses their set element for an update granting the issuer knowledge of this update. Aside from this, accumulators provide most of the desired privacy requirements.

Hyperledger Indy is solution that uses a cryptographic accumulator^{[3](https://eprint.iacr.org/2008/539.pdf)} where set elements are Boneh Boyen Shacham (BBS+) signatures^{[4](https://eprint.iacr.org/2016/663.pdf)}. This accumulator is quite efficient because the holder only needs to hold a single BBS+ credential for both VC presentations and revocation checks and the accumulator size is only 64 bytes in size. Even so, the benefits end there. The accumulator requires two sets of keys. The credential public key is 480 bytes and private key is 64 bytes. The accumulator public key is 384 bytes and private key is 32 bytes. Set element delta is 192 bytes. Accumulator signature credentials are 324 bytes aka an accumulator witness. Indy uses the accumulator mostly in a static sense by allocating elements upfront and only publishing deletions as integers. The entire element set list is static and served in a *tails file*. Witness updates are only available by applying deltas. The problem with this approach is provers that remain offline and do not update often are punished with higher bandwidth downloads, more registry queries, and computationally to bring their witness current.

This proposal addresses these shortcomings while maintaining the desired privacy.

## Requirements

This document proposes the use of cryptographic accumulator(s) as revocation registries. Before describing the layout, this section introduces the security requirements a revocation registry needs to minimize or eliminate *linked* and *linkable* data leaks. These requirements are listed according to three roles an anonymous credential system has namely a *issuer*, *holder*, and *verifier*.

**Issuer**

1. Must be able to choose the registry elements
1. Only she can add or remove registry elements
1. Only she can publish a new registry
1. Must not be able to know directly when a Holder presents a proof to another party i.e. the revocation registry must not allow an issuer to track in any way a holder's use patterns
1. Should not be able to know if a given holder is requesting an updated witness from them, or if the holder is updating their witness
1. Should not be able to know how long its been since a holder last updated

Issuers that collude with other parties to track a holder is a separate problem that will be discussed later.

**Holder**

1. Proving non-revocation status must be unlinkable i.e. proof A is indistinguishable from proof B, C, etc.
2. Non-revocation status can be completed either as a membership or non-membership proofs.
3. Should not be penalized for updating regardless of the last time they updated.
5. Should remain anonymous when updating their witness.
6. Proof computation time must be < 1s.

**Verifier**

1. Must only learn the non-revocation status from a proof i.e. proving non-revocation status doesn't reveal any *linked* or *linkable* data.
2. Must only be required to use registry data to verify a proof from a specific epoch i.e. the verifier shouldn't have to perform multiple lookups from multiple registries to verify a proof. One epoch must be sufficient.
3. Proof verification time must be < 1s.
4. Must only trust non-revocation proofs when combined with another proof such as a signature proof. This requirement stems from in the case of this proposal, anyone can obtain a valid witness which means anyone even non-credential holders can generate valid proofs. Without this requirement, non-revocation proofs could be used by anyone to mean anything.

## Proposal

This proposal uses two cryptographic accumulators, one based on groups of unknown order and the other based on elliptic curve pairings. However any accumulator that satisfies the previously mentioned properties also works such as those based on hyperelliptic curves, lattices, or zkSNARKS.

### Primitives

The first accumulator is based on pairings^{[7](https://eprint.iacr.org/2020/777.pdf)} and is used for membership proofs. Recent findings show even though this accumulator supports non-membership proofs, witness holder's can collude for forgery attacks^{[8](https://eprint.iacr.org/2020/598.pdf)} and thus is not recommended for general non-membership proofs. Used correctly and with extreme care, non-membership proofs could be implemented. This accumulator shall be referred to as *VB20*. *VB20* characteristics include:

- Field elements in the curve sub-group Fq
- Curve points in G1
- Curve points in G2
- Set elements are field elements.
- A single secret key **x** is a field element.
- A single public key **Q** is a curve point in G2.
- The accumulator value **V** is a curve point in G1.
- A membership witness **W** is a curve point in G1.
- Non-membership witness **N** is a curve point in G1 and a field element.
- Membership proof **M** is 3 curve points in G1 and 5 field elements.
- Non-membership proof **R** is 5 curve points in G1 and 8 field elements.

The current recommended curve for pairings is [BLS12-381](https://hackmd.io/@benjaminion/bls12-381). Using this curve yields the following results:

- Set elements are 32 bytes
- Secret key is 32 bytes
- Public key is 96 bytes
- Accumulator is 48 bytes
- Membership witness is 48 bytes.
- Non-membership witness is 80 bytes.
- Membership proofs are 304 bytes.
- Non-membership proofs are 496 bytes.

The second accumulator is used instead for non-membership proofs which is based on groups of unknown-order^{[5](https://eprint.iacr.org/2018/1188.pdf)}. This accumulator's security can potentially be made stronger using hyperelliptic curves^{[6](https://eprint.iacr.org/2020/289.pdf)} instead of using groups based on two safe primes but this proposal uses the product of two safe primes. This accumulator shall be referred to as *BBF18*. Set elements are prime numbers. *BBF18* characteristics include

- Set elements are prime numbers of sufficient size either generated at random, or from hashes using a secure collision-resistent technique.
- Modulus elements are numbers the size of the modulus.
- A single secret key **{p, q}** where **p = 2p'+1** and **q = 2q'+1** where **p, q, p', q'** are prime numbers. Primes of the form **p = 2p'+1** are called safe primes and **p'** is called a Sophie-German prime^{[11](https://en.wikipedia.org/wiki/Safe_and_Sophie_Germain_primes)}.
- A single public key **{g, Q}** where **Q = p·q** and **g** is a random quadratic residue^{[12](https://en.wikipedia.org/wiki/Quadratic_residue)} < **Q** and > 1, both are modulus elements.
- The accumulator value **V** is a modulus element.
- A membership witness **W** is a modulus element.
- Non-membership witness **N** is a set element and a modulus element.
- Membership proof **M** is 2 set elements and 3 modulus elements.
- Non-membership proof **R** is 4 set elements 5 modulus elements.

The current recommendation for unknown order modulus sizes is 2048-bits (256 bytes) and 256-bit (32-byte) primes. Using these recommendations yields the following results:

- Set elements are 32 bytes
- Secret key is 256 bytes
- Public key is 512 bytes
- Accumulator is 256 bytes
- Membership witness is 256 bytes.
- Non-membership witness is 288 bytes.
- Membership proofs are 864 bytes.
- Non-membership proofs are 1408 bytes.

## Processes

**Issuer**

### Setup

1. Generates a pair of keys and creates an empty accumuator. The keys should be stored preferrably in secure enclaves or cryptographic specific hardware or environments.
1. Allocates a prefined number of set elements are stores this list somewhere safe from tampering.
1. Computes (non-)membership witnesses for each set element.
2. Computes the accumulator value with all the set elements.
3. Publishes the list of witness/set element pairs, the accumulator, and public key to a registry (Blockchain, CDN, Cloud Server).

### Add/Revoke

1. Add/Delete set elements to/from the set and publish an updated list of witness/set element pairs and accumulator to the registry.

**Holder**

### Obtain Credential

1. Receives credential from issuer that includes the witness/set element that pertains to them. The set element is signed as part of the credential whereas the witness is not.

### Witness Update

This can be completed two ways, the first involves downloading the registry, the second involves interacting with the issuer.

#### Registry Download

The holder downloads the list of witness/set element pairs and selects the witness that pertains to them. This functions in a similar manner to PIR such that an observer cannot determine in which witness the holder is interested. This approach is simple and the lookup is quick to perform but can be costly to download as the size of grows. The issuer also never has to interact with any holders using this method and thus has no indication as to who has updated their witness or not.

**NOTE**
The registry download list should NOT include every valid set element when using *VB20*. If the entire list is known, an attacker can construct log\(p\) non-membership witnesses and launch a witness forgery attack thus leaking the secret key \[see 8\]. To avoid this, a certain number of elements should be kept private along with the secret key.

#### Return to Issuer

The holder and issuer engage in a two party computation to produce the holder's updated witness without the holder disclosing their set element and the issuer disclosing the secret key. The holder creates a constant size polynomial blinded commitment^{[13](https://www.iacr.org/archive/asiacrypt2010/6477178/6477178.pdf)} to their set element and sends that to the issuer. The issuer evaluates the polynomial using their secret key and the existing list of set elements and sends the result back to the holder. The result is a blinded witness. The holder unblinds the witness and checks it for accuracy. If the holder's set element is absent from the accumulator, the witness will not verify. This approach trades lower bandwidth for higher computational burden by the holder. The downside here is any metadata leaked associated with communicating with the issuer directly.

### Present Credential

A verifier specifies to which accumulator version the holder should present. The verifier should pick a version that is recent enough so she knows whether the holder is revoked or not. The holder obtains an updated witness for a specific accumulator to prove against if they do not have one.

A holder takes their signature and accumulator witness and produces a proof that shows their possession of a valid credential and the registry element in the credential is still a set member or nonmember. The two proofs are linked together with a schnorr proof showing proof of discrete log equality.

To produce these three proofs, the holder must have knowledge of all signed messages, the credential signature, and a witness that pertains to the specified accumulator the verifier requests proof against.

**Verifier**

### Verify Presentation

The verifier selects a specific accumulator version to which the holder must prove their revocation status. The verifier could select multiple depending on her security tolerance. For example, she could select any accumulator within the past week as valid if the situation allows for lower security. Higher security usually requires the most recent version.

The verifier and sends the accumulator version(s) as part of a
sigma protocol that yields the zero-knowledge proofs. The verifier learns nothing but the fact that the holder has a current valid credential.

## Protocols

### Notation

| Name | Description |
| -------- | -------- |
| **C** | A pairing friendly curve |
| **p** | The field modulus of **C** |
| **q** | The subgroup order of **C** |
| **G1** | Points in the cyclic group 1 of order **p** |
| **G2** | Points in the multiplicative group of order **p²** |
| **GT** | Result group of order **p** from computing a pairing on two points |
| **P** | The base point in **G1** |
| **P~** | The base point in **G2** |
| **e(P, P~)** | The type-3 ate pairing function on points **P** and **P~** whose output is in **GT** |
| **1_G1** | The point at infinity in **G1** |
| **1_G2** | The point at infinity in **G2** |
| **1_Gt** | The point at infinity in **GT** |
| **rand(ℤq)** | Draw a uniformly distributed random value in ℤq |
| **a \|\| b** | Byte concatenation of two elements a, b |
| **H_q(bytes)** | Hash **bytes** into a field element in ℤq |
| **(·)** | Elliptic curve scalar multiplication |

### Functions

#### Key Gen

Input: **C**
Output: A secret key **k**, public key **K~**

Steps:

1. k = rand(C.q)
2. K~ = k · P~
3. return k, K~

#### Create Accumulator Element

Use rand(ℤq)

#### Initialize Accumulator

Input: **C**, **k**, **[s]**, an array of accumulator elements
Output: **A0**, a point in **G1**

Steps:

1. A0 = ∏_i (s_i + k) · P

#### Create Membership Witness

Input: **At**, **[s]**, **k**, **j**, the index for which to create the witness
Output: **U**

Steps:

1. if j > len([s]); abort
2. U = (s[j] + k)^-1 · At

#### Proof Gen

Input: **At**, **K~**, **U**, **sj**, **n** a proof nonce as an arbitrary byte sequence with at least 16 bytes

## Conclusion

This proposal shows how a privacy preserving revocation solution can be constructed from cryptographic accumulators and signatures that limits or eliminates *linked* data from being disclosed which also limits or eliminates *linkable* data from being created about a holder.

## References

1. [Enhanced Privacy ID from Bilinear Pairing](https://eprint.iacr.org/2009/095.pdf)
2. [Practical Backward Unlinkable Revocation in Fido, Germane-ID, Idemix and U-Prove](https://eprint.iacr.org/2016/217)
3. [An Accumulator Based on Bilinear Maps and
Efficient Revocation for Anonymous Credentials](https://eprint.iacr.org/2008/539.pdf)
4. [Anonymous Attestation Using the Strong Diffie
Hellman Assumption Revisited](https://eprint.iacr.org/2016/663.pdf)
5. [Batching Techniques for Accumulators
with Applications to IOPs and
Stateless Blockchains](https://eprint.iacr.org/2018/1188.pdf)
6. [The security of Groups of Unknown Order based on Jacobians of Hyperelliptic Curves](https://eprint.iacr.org/2020/289.pdf)
7. [Dynamic Universal Accumulator with Batch Update over Bilinear Groups](https://eprint.iacr.org/2020/777.pdf)
8. [Cryptanalysis of Au et al. Dynamic Universal Accumulator](https://eprint.iacr.org/2020/598.pdf)
9. [Zero-Knowledge Proofs for Set Membership: Efficient, Succinct, Modular](https://eprint.iacr.org/2019/1255.pdf)
10. [BLS12-381 For The Rest Of Us](https://hackmd.io/@benjaminion/bls12-381)
11. [Safe and Sophie-Germain Primes](https://en.wikipedia.org/wiki/Safe_and_Sophie_Germain_primes)
12. [Quadratic Residue](https://en.wikipedia.org/wiki/Quadratic_residue)
13. [Constant-Size Commitments to Polynomials and
Their Applications](https://www.iacr.org/archive/asiacrypt2010/6477178/6477178.pdf)