- Name: Anonymous Credential Protocol
- Author: Mike Lodder and Brent Zundel
- Start Date: January 25, 2019

# Summary¶

Anonymous credentials form the heart of Indy’s identity capabilities. This document describes the protocol for Camenisch-Lysyanskaya signatures and the anonymous credentials they enable.

This document is a markdown-formatted version of work by Dmitry Khovratovich, which is based on CL signatures. The latex source used for the equations in this version may be found here.

# Motivation¶

This HIPE is intended as a publication of the protocol behind the code that has already been implemented in indy-crypto.

# Tutorial¶

## Introduction¶

### Concept¶

*Anonymous credentials* allow an identity owner to prove certain properties
about their identity an uncorrelatable way without revealing other identity
details. The properties can be raw identity attributes such as a birth date or
address, or more sophisticated predicates such as “A is older than 20 years
old”.

We assume three parties: *issuer*, *holder*, and *verifier*. From the functional
perspective:

- the issuer gives a credential
*C*based on identity schema*X*, which asserts certain properties 𝒫 about*X*, to the holder. - The credential consists of attributes represented by integers
*m*._{1}, m_{2},…, m_{l} - The holder then presents (𝒫,
*C*) to the verifier, which can verify that the issuer has asserted property 𝒫.

### Properties¶

- Credentials are
*unforgeable*in the sense that no one can fool the verifier with a credential not prepared by the issuer. - Credentials are
*unlinkable*in the sense that it is impossible to correlate the presented credential across multiple presentations. This is implemented by the holder*proving*with a zero-knowledge proof*that he has a credential*rather than showing the credential. Unlinkability can be simulated by the issuer generating a sufficient number of ordinary unrelated credentials.

Note: unlinkability may be turned off to make credentials *one-time use* so that
second and later presentations are detected.

## Generic notation¶

Attribute *m* is a *l _{a}*-bit unsigned integer. Technically it is
possible to support credentials with different

*l*, but in Sovrin it is set

_{a}*l*=256.

_{a}## Protocol Overview¶

The described protocol supports anonymous credentials given to multiple holders by various issuers, which are presented to various relying parties.

Various types of anonymous credentials can be supported. In this section, the combination of CL-based credentials and pairing-based revocation is described.

The simplest credential lifecycle, with one credential, single issuer, holder, and verifier is as follows:

- Issuer determines a credential schema 𝒮: the type of cryptographic signatures
used to sign the credentials, the number
*l*of attributes in a credential, the indices*A*of hidden attributes, the public key_{h}⊂ {1,2,…,l}*P*, the non-revocation credential attribute number_{k}*l*and non-revocation public key_{r}*P*(Section~\ref{sec:iss-setup}). Then he publishes it on the ledger and announces the attribute semantics._{r} - Holder retrieves the credential schema from the ledger and sets the hidden attributes.
- Holder requests a credential from issuer. He sends hidden attributes in a
blinded form to issuer and agrees on the values of known attributes
*A*._{k}= {1,2,…,l} \ A_{h} - Issuer returns a credential pair
*(C*to holder. The first credential contains the requested_{p}, C_{NR})*l*attributes. The second credential asserts the non-revocation status of the first one. Issuer publishes the non-revoked status of the credential on the ledger. - Holder approaches verifier. Verifier sends the Proof Request ℰ to holder. The
Proof Request contains the credential schema
*𝒮*and disclosure predicates 𝒟. The predicates for attribute_{E}*m*and value*V*can be of form*m=V*,*m<V*, or*m>V*. Some attributes may be asserted to be the same:*m*._{i}=m_{j} - Holder checks that the credential pair he holds satisfies the schema
*𝒮*. He retrieves the non-revocation witness from the ledger._{E} - Holder creates a proof
*P*that he has a non-revoked credential satisfying the proof request ℰ and sends it to verifier. - Verifier verifies the proof.

If there are multiple issuers, the holder obtains credentials from them
independently. To allow credential chaining, issuers reserve one attribute
(usually *m _{1}*) for a secret value hidden by holder. The holder is
supposed then to set it to the same hidden value in all issued credentials.
Relying Parties require them to be the same in all credentials. A proof request
should specify the list of schemas that credentials should satisfy in.

## Schema preparation¶

Credentials may have limited use to only authorized holder entities called
agents. Agents can prove authorization to use a credential by the holder
including a policy address ** I** in primary credentials as attribute

*m*.

_{3}### Attributes¶

Issuer defines the primary credential schema 𝒮 with *l* attributes
*m _{1},m_{2},…, m_{l}* and the set of hidden
attributes

*A*.

_{h}⊂ {1,2,…,l}By default, *{1,3} ⊂ A _{h}* whereas

*2 ∉ A*

_{h}Issuer defines the non-revocation credential with *2* attributes
*m _{1},m_{2}*.

In Sovrin:

*A*and_{h}= {1}*m*is reserved for the link secret of the holder,_{1}*m*is reserved for the context – the enumerator for the holders,_{2}*m*is reserved for the policy address_{3}.*I*

## Primary Credential Cryptographic Setup¶

In Sovrin, issuers use CL-signatures for primary credentials.

For the CL-signature, the issuer generates:

- Random 1536-bit primes
*p’,q’*such that*p ← 2p’+1*and*q ← 2q’+1*are also prime. Then computes*n ← pq*. - A random quadratic residue
*S mod n*; - Random
*x*_{Z}, x_{R1},…,x_{Rl}∈ [2; p’q’-1]

Issuer computes:
*Z ← S ^{xZ}(mod n); {R_{i} ← S^{xRi}(mod n)}_{1 ≤ i ≤ l};*

The issuer’s public key is
*P _{k} = (n, S,Z,{R_{i}}_{1 ≤ i ≤ l})*
and the private key is

*s*.

_{k}= (p, q)### Issuer Setup Correctness Proof¶

Issuer generates random

*x~*_{Z}, x!_{R1},…,x~_{Rl}∈ [2; p’q’-1]Computes:

Eq1

Here *H _{I}* is the issuer-defined hash function, by default SHA2-256.

- Proof
*𝒫*of correctness is Eq6_{I}

### Non-revocation Credential Cryptographic Setup¶

In Sovrin, issuers use CKS accumulators and signatures to
track revocation status of primary credentials, although other signature types
will be supported too. Each primary credential is given an index from 1 to *L*.

The CKS accumulator is used to track revoked primary credentials, or
equivalently, their indices. The accumulator contains up to *L* indices of
credentials. If issuer has to issue more credentials, another accumulator is
prepared, and so on. Each accumulator *A* has an identifier *I _{A}*.

Issuer chooses:

- Groups
*𝔾*of prime order_{1},𝔾_{2},𝔾_{T}*q* - Type-3 pairing operation
*e: 𝔾*._{1}x 𝔾_{2}→ 𝔾_{T} - Generators:
*g*for*𝔾*,_{1}*g’*for*𝔾*._{2}

Issuer:

- Generates
- Random Eq7
- Random Eq8
- Random
*sk, x (mod q)*.

- Computes Eq9

The revocation public key is
Eq10 and the secret key is *(x,sk)*.

#### New Accumulator Setup¶

To create a new accumulator *A*, issuer:

- Generates random
*γ (mod q)*. - Computes
- Eq11
- Eq12
- Eq13

- Set
*V ← ∅, acc ← 1*

The accumulator public key is *P _{a} = z* and secret key is

*γ*.

Issuer publishes *(P _{a},V)* on the ledger.
The accumulator identifier is

*ID*.

_{a}= z## Issuance of Credentials¶

### Holder Setup¶

Holder:

- Loads credential schema
*𝒮*. - Sets hidden attributes
*{ m*._{i}}_{{i ∈ Ah}} - Establishes a connection with issuer and gets nonce
*n*either from issuer or as a precomputed value. Holder is known to issuer with identifier_{0}*ℋ*.

Holder prepares data for primary credential:

Generate random 3152-bit

*v’*.Generate random 593-bit

*{m̃*, and random 3488-bit_{i}}_{{i ∈ Ah}}*ṽ’*.Compute, taking

*S,Z,R*from_{i}*P*:_{k}Eq14

Compute

Eq15

Generate random 80-bit nonce

*n*_{1}Send to the issuer:

Eq16

Holder prepares for non-revocation credential:

- Load issuer’s revocation key
*P*and generate random_{R}*s’*._{R}mod q - Compute
*U*taking_{R}← h_{2}^{s’R}*h*from_{2}*P*._{R} - Send
*U*to the issuer._{R}

#### Issuer Proof of Setup Correctness¶

To verify the proof *𝒫 _{i}* of correctness, holder computes:

Eq17

and verifies

Eq18

### Primary Credential Issuance¶

Issuer verifies the correctness of holder’s input:

Compute

Eq19

Verify

*c = H( U || Û || n*_{0})Verify that

*v̂’*is a 673-bit number,*{m̂*are 594-bit numbers._{i}r̂_{i}}_{i ∈ 𝒜c}

Issuer prepares the credential:

Assigns index

*i<L*to holder, which is one of not yet taken indices for the issuer’s current accumulator*A*. Compute*m*and store information about holder and the value_{2}← H(i||ℋ)*i*in a local database.Set, possibly in agreement with holder, the values of disclosed attributes, i.e. with indices from

*A*._{k}Generate random 2724-bit number

*v’’*with most significant bit equal 1 and random prime*e*such that*2*^{596}≤ e ≤ 2^{596}+ 2^{119}Compute

Eq20

Generate random

*r < p’q’*;Compute

Eq21

Send the primary pre-credential

*( {m*to the holder._{i}}_{i ∈ Ak}, A, e, v’’, s_{e}, c’ )

### Non-Revocation Credential Issuance¶

Issuer:

Generate random numbers

*s’’, c mod q*.Take

*m*from the primary credential he is preparing for holder._{2}Take

*A*as the accumulator value for which index*i*was taken. Retrieve current set of non-revoked indices*V*.Compute:

Eq22

Send the non-revocation pre-credential

*( I*to holder._{A}, σ, c, s’’, wit_{i}, g_{i}, g_{i}’, i )Publish updated

*V, A*on the ledger.

### Storing Credentials¶

Holder works with the primary pre-credential:

Compute

*v ← v’+v’’*.Verify

*e*is prime and satisfies*2*^{596}≤ e ≤ 2^{596}+ 2^{119}Compute

Eq23

Verify

*Q = A*^{e}mod nCompute

*Â ← A ^{c’ + se * e}mod n*

- Verify
*c’ = H( Q || A || Â || n*_{2}). - Store
**primary credential***C*._{p}= ( { m_{i}}_{i ∈ Cs}, A, e, v )

Holder takes the non-revocation pre-credential
*( I _{A}, σ, c, s’’, wit_{i}, g_{i}, g_{i}’, i)*
computes

*s*and stores the non-revocation credential

_{R}← s’+s’’*C*

_{NR}← ( I_{A}, σ, c, s, wit_{i}, g_{i},*g*.

_{i}’, i)## Revocation¶

Issuer identifies a credential to be revoked in the database and retrieves its
index *i*, the accumulator value *A*, and valid index set *V*. Then he
proceeds:

- Set
*V ← V \ {i}*; - Compute
*A ← A/g’*_{L+1-i} - Publish
*{V,A}*.

## Presentation¶

### Proof Request¶

Verifier sends a proof request, where it specifies the ordered set of *d*
credential schemas *{ 𝒮 _{1}, 𝒮_{2}, …, 𝒮_{d} }*,
so that the holder should provide a set of

*d*credential pairs

*( C*that correspond to these schemas.

_{p}, C_{NR})Let credentials in these schemas contain *X* attributes in total.
Suppose that the request is made:

- to reveal
*x*attributes,_{1} - to prove
*x*equalities_{2}*m*(from possibly distinct schemas)_{i}= m_{j} - to prove
*x*predicates of form_{3}*m*._{i}> ≥ ≤ < z

Then effectively *X - x _{1}* attributes remain hidden (denoted

*A*), which form

_{h}*x*

_{4}= (X - x_{1}*- x*equivalence classes.

_{2})- Let ϕ map
*A*to_{h}*{ 1, 2, …, x*according to this equivalence._{4}} - Let
*A*denote the set of indices of_{v}*x*attributes that are disclosed._{1}

The proof request also specifies *A _{h}, ϕ, A_{v}* and the set
𝒟 of predicates. Along with a proof request, the verifier also generates and
sends an 80-bit nonce

*n*.

_{1}### Proof Preparation¶

Holder prepares all credential pairs Credential pairs to submit:

- Generates
*x*random 592-bit values_{4}*$ỹ*_{1},*ỹ*and set Eq25 for Eq26._{2},…,ỹ_{x4} - Create empty sets 𝓣 and 𝓒.
- For all credential pairs Credential pairs execute Proof Preparation.
- Executes hashing once.
- For all credential pairs Credential pairs execute Final Preparation.
- Executes Final Preparation once.

Verifier:

- For all credential pairs Credential pairs executes Verification.
- Executes final hashing once.

#### Non-revocation proof¶

Holder:

Load issuer’s public revocation key issuer's public revocation key.

Load the non-revocation credential non-revocation credential;

Obtain recent

*V, acc*(from verifier, Sovrin link, or elsewhere).Update non-revocation credential:

Eq27

Here

*V*is taken from wit_{old}_{i}and updated there.Select random Eq28;

Compute

Eq29

and adds these values to 𝓒.

Compute

Eq30

and adds these values to 𝓒.

Generate random Eq31

Compute

T1 and T2

T3

T4 through T8

and add these values to 𝓣.

#### Validity proof¶

Holder:

Generate a random 592-bit number widetilde{m_j} for each j \in \mathcal{A}_{\overline{r}}.

For each credential C_p = ({m_j},A,e,v) and issuer’s public key pk_I:

Choose random 3152-bit r.

Take $n,S$ from pk_I compute

Eq32

and add to 𝓒.

Compute $e' \leftarrow e - 2^{596}$.

Generate random 456-bit number e-tilde.

Generate random 3748-bit number v-tilde.

Compute

T \leftarrow (A')^{\widetilde{e}}\left(\prod_{j\in \mathcal{A}_{\overline{r}}} R_j^{\widetilde{m_j}}\right)(S^{\widetilde{v}})\pmod{n}

and add to 𝓣.

Load

*Z,S*from issuer’s public key.For each predicate

*p*where the operator * is one of >, \geq, <, \leq.Calculate delta such that:

delta-cases

Calculate

*a*such that:a cases

Find (possibly by exhaustive search) u1 through u4 such that:

delta equation

- Generate random 2128-bit numbers r1 through r_delta.
- Compute

T equations and add these values to 𝓒 in the order T1 through T_delta.

- Generate random 592-bit numbers u1-tilde through u4-tilde.
- Generate random 672-bit numbers r1 through u_delta-tilde.
- Generate random 2787-bit number alpha-tilde
- Compute

T-bar and Q equations

and add these values to 𝓣 in the order T1-bar through Tdelta-bar.

#### Final preparation¶

Holder:

For non-revocation credential

*C*compute:_{NR}Eq33

and add them to 𝓧.

For primary credential

*C*compute:_{p}Eq34

The values Eq35 are the

*sub-proof*for credential*C*._{p}For each predicate

*p*compute:Eq36

The values Eq37 are the

*sub-proof*for predicate*p*.

#### Sending¶

Holder sends (*c*,𝓧, *{Pr _{C}}*,

*{Pr*, 𝓒) to the verifier.

_{p}}### Verification¶

For the credential pair (*C _{p}, C_{NR}*), verifier retrieves
relevant variables from 𝓧,

*{Pr*,

_{C}}*{Pr*, 𝓒.

_{p}}#### Validity¶

Verifier uses all issuer public key pk_I involved into the credential generation and the received Eq41. He also uses revealed Revealed attributes. He initiates widehat script T as an empty set.

For each credential

*C*, take each sub-proof_{p}*Pr*and compute:_{C}Eq42

Add widehat{T} to widehat script T.

For each predicate

*p*:Eq43

Eq44

- Using
*Pr*and 𝓒 compute_{p}

Eq45

and add these values to widehat script T in the order Eq46.

- Using

#### Final hashing¶

Verifier computes

Eq47

If c = c-widehat output VERIFIED else FAIL.

## A Note About Encoding Attributes¶

The above protocol shows how a credential issuer may sign an array of attributes, which are defined as 256-bit integers. In order for the protocol to be used for credentials that contain attributes which are not integers, such as strings, it is necessary to encode those attributes as integers.

The current implementation of Indy-SDK allows for two types of values as attributes in credentials: integers and strings. The integers are used as is. The strings are hashed using SHA-256, and the resulting 256-bit integers are signed. While the protocol described in this paper is sufficient to prove that the integer presented to a verifier is the same one that an issuer signed, it is left to Indy-SDK to prove that the strings presented to a verifier, when hashed using SHA-256, are the same as the 256-bit integers which the issuer signed.

# Drawbacks¶

One drawback to this approach is that the signatures for the primary credential are RSA-based. This results in keys and proofs that are much larger than other signature schemes would require for similar levels of expected security.

Another drawback is that revocation is handled using a different, elliptic-curve based signature that allows the use of the more-efficient set-membership proofs and accumulators required by that part of the protocol.

This dual-credential model provides all of the functionality required by the protocol, but uses two different signature schemes to accomplish it, one of which is based in outdated technology that requires very large keys and proofs. Using two signature types results in a more unwieldy protocol.

# Rationale and alternatives¶

As this protocol is describes the current implementation, rationale and alternatives point necessarily to potential future work.

The dual-credential model is not ideal, so possible future anonymous credential schemes should strive to find a data structure and proof scheme that meets the required characteristics of selective disclosure of attributes, predicate proofs, and set membership proofs. It is outside of the scope of this document to speculate on what form those structures and proofs may take.

# Prior art¶

It is the understanding of the authors that few production quality implementations of anonymous credential signature schemes exist.

Two implementations we are aware of are Idemix, implemented by IBM, and IRMA, implemented by The Privacy by Design Foundation.

# Unresolved questions¶

This protocol is already implemented in indy-crypto.