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

Status

  • Status: ADOPTED
  • Status Date: implemented in mid 2018
  • Status Note: implemented in libindy

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 m1, m2,…, ml.
  • 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 la-bit unsigned integer. Technically it is possible to support credentials with different la, but in Sovrin it is set la=256.

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:

  1. 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 Ah ⊂ {1,2,…,l} of hidden attributes, the public key Pk, the non-revocation credential attribute number lr and non-revocation public key Pr (Section~\ref{sec:iss-setup}). Then he publishes it on the ledger and announces the attribute semantics.
  2. Holder retrieves the credential schema from the ledger and sets the hidden attributes.
  3. Holder requests a credential from issuer. He sends hidden attributes in a blinded form to issuer and agrees on the values of known attributes Ak = {1,2,…,l} \ Ah.
  4. Issuer returns a credential pair (Cp, CNR) to holder. The first credential contains the requested 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.
  5. Holder approaches verifier. Verifier sends the Proof Request ℰ to holder. The Proof Request contains the credential schema 𝒮E and disclosure predicates 𝒟. The predicates for attribute m and value V can be of form m=V, m<V, or m>V. Some attributes may be asserted to be the same: mi=mj.
  6. Holder checks that the credential pair he holds satisfies the schema 𝒮E. He retrieves the non-revocation witness from the ledger.
  7. Holder creates a proof P that he has a non-revoked credential satisfying the proof request ℰ and sends it to verifier.
  8. 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 m1) 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 m3.

Attributes

Issuer defines the primary credential schema 𝒮 with l attributes m1,m2,…, ml and the set of hidden attributes Ah ⊂ {1,2,…,l}.

By default, {1,3} ⊂ Ah whereas 2 ∉ Ah

Issuer defines the non-revocation credential with 2 attributes m1,m2.

In Sovrin:

  • Ah = {1} and m1 is reserved for the link secret of the holder,
  • m2 is reserved for the context – the enumerator for the holders,
  • m3 is reserved for the policy address I.

Primary Credential Cryptographic Setup

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

For the CL-signature, the issuer generates:

  1. Random 1536-bit primes p’,q’ such that p ← 2p’+1 and q ← 2q’+1 are also prime. Then computes n ← pq.
  2. A random quadratic residue S mod n;
  3. Random ../../_images/Eq1.pngxZ, xR1,…,xRl ∈ [2; p’q’-1]

Issuer computes: ../../_images/Eq2.pngZ ← SxZ(mod n); {Ri ← SxRi(mod n)}1 ≤ i ≤ l;

The issuer’s public key is ../../_images/iss-pub-key-full.pngPk = (n, S,Z,{Ri}1 ≤ i ≤ l) and the private key is sk = (p, q).

Issuer Setup Correctness Proof

  1. Issuer generates random ../../_images/Eq4.pngx~Z, x!R1,…,x~Rl ∈ [2; p’q’-1]

  2. Computes:

    ../../_images/Eq5.pngEq1

Here HI is the issuer-defined hash function, by default SHA2-256.

  1. Proof 𝒫I of correctness is ../../_images/Eq6.pngEq6

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 IA.

Issuer chooses:

  • Groups 𝔾1,𝔾2,𝔾T of prime order q
  • Type-3 pairing operation e: 𝔾1 x 𝔾2 → 𝔾T.
  • Generators: g for 𝔾1, g’ for 𝔾2.

Issuer:

  1. Generates
    1. Random ../../_images/Eq7.pngEq7
    2. Random ../../_images/Eq8.pngEq8
    3. Random sk, x (mod q).
  2. Computes ../../_images/Eq9.pngEq9

The revocation public key is ../../_images/Eq10.pngEq10 and the secret key is (x,sk).

New Accumulator Setup

To create a new accumulator A, issuer:

  1. Generates random γ (mod q).
  2. Computes
    1. ../../_images/Eq11.pngEq11
    2. ../../_images/Eq12.pngEq12
    3. ../../_images/Eq13.pngEq13
  3. Set V ← ∅, acc ← 1

The accumulator public key is Pa = z and secret key is γ.

Issuer publishes (Pa,V) on the ledger. The accumulator identifier is IDa = z.

Issuance of Credentials

Holder Setup

Holder:

  • Loads credential schema 𝒮.
  • Sets hidden attributes { mi }{i ∈ Ah}.
  • Establishes a connection with issuer and gets nonce n0 either from issuer or as a precomputed value. Holder is known to issuer with identifier .

Holder prepares data for primary credential:

  1. Generate random 3152-bit v’.

  2. Generate random 593-bit {m̃i}{i ∈ Ah}, and random 3488-bit ṽ’.

  3. Compute, taking S,Z,Ri from Pk:

    ../../_images/Eq14.pngEq14

  4. Compute

    ../../_images/Eq15.pngEq15

  5. Generate random 80-bit nonce n1

  6. Send to the issuer:

    ../../_images/Eq16.pngEq16

Holder prepares for non-revocation credential:

  1. Load issuer’s revocation key PR and generate random s’Rmod q.
  2. Compute UR ← h2s’R taking h2 from PR.
  3. Send UR to the issuer.

Issuer Proof of Setup Correctness

To verify the proof 𝒫i of correctness, holder computes:

../../_images/Eq17.pngEq17

and verifies

../../_images/Eq18.pngEq18

Primary Credential Issuance

Issuer verifies the correctness of holder’s input:

  1. Compute

    ../../_images/Eq19.pngEq19

  2. Verify c = H( U || Û || n0 )

  3. Verify that v̂’ is a 673-bit number, {m̂ii}i ∈ 𝒜c are 594-bit numbers.

Issuer prepares the credential:

  1. Assigns index i<L to holder, which is one of not yet taken indices for the issuer’s current accumulator A. Compute m2← H(i||ℋ) and store information about holder and the value i in a local database.

  2. Set, possibly in agreement with holder, the values of disclosed attributes, i.e. with indices from Ak.

  3. Generate random 2724-bit number v’’ with most significant bit equal 1 and random prime e such that 2596≤ e ≤ 2596 + 2119

  4. Compute

    ../../_images/Eq20.pngEq20

  5. Generate random r < p’q’;

  6. Compute

    ../../_images/Eq21.pngEq21

  7. Send the primary pre-credential ( {mi}i ∈ Ak, A, e, v’’, se, c’ ) to the holder.

Non-Revocation Credential Issuance

Issuer:

  1. Generate random numbers s’’, c mod q.

  2. Take m2 from the primary credential he is preparing for holder.

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

  4. Compute:

    ../../_images/Eq22.pngEq22

  5. Send the non-revocation pre-credential ( IA, σ, c, s’’, witi, gi, gi’, i ) to holder.

  6. Publish updated V, A on the ledger.

Storing Credentials

Holder works with the primary pre-credential:

  1. Compute v ← v’+v’’.

  2. Verify e is prime and satisfies 2596≤ e ≤ 2596 + 2119

  3. Compute

    ../../_images/Eq23.pngEq23

  4. Verify Q = Ae mod n

  5. Compute

 ← Ac’ + se * emod n

  1. Verify c’ = H( Q || A || Â || n2 ).
  2. Store primary credential Cp = ( { mi }i ∈ Cs, A, e, v ).

Holder takes the non-revocation pre-credential ( IA, σ, c, s’’, witi, gi, gi’, i) computes sR ← s’+s’’ and stores the non-revocation credential CNR ← ( IA, σ, c, s, witi, gi, gi’, i).

Non revocation proof of correctness

Holder computes:

../../_images/Eq24.pngEq24

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:

  1. Set V ← V \ {i};
  2. Compute A ← A/g’L+1-i
  3. 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 ( Cp, CNR ) that correspond to these schemas.

Let credentials in these schemas contain X attributes in total. Suppose that the request is made:

  • to reveal x1 attributes,
  • to prove x2 equalities mi = mj (from possibly distinct schemas)
  • to prove x3 predicates of form mi > ≥ ≤ < z.

Then effectively X - x1 attributes remain hidden (denoted Ah), which form x4 = (X - x1 - x2) equivalence classes.

  • Let ϕ map Ah to { 1, 2, …, x4 } according to this equivalence.
  • Let Av denote the set of indices of x1 attributes that are disclosed.

The proof request also specifies Ah, ϕ, Av and the set 𝒟 of predicates. Along with a proof request, the verifier also generates and sends an 80-bit nonce n1.

Proof Preparation

Holder prepares all credential pairs ../../_images/cred-pairs.pngCredential pairs to submit:

  1. Generates x4 random 592-bit values $ỹ1, 2,…,ỹx4 and set ../../_images/Eq25.pngEq25 for ../../_images/Eq26.pngEq26.
  2. Create empty sets 𝓣 and 𝓒.
  3. For all credential pairs ../../_images/cred-pairs.pngCredential pairs execute Proof Preparation.
  4. Executes hashing once.
  5. For all credential pairs ../../_images/cred-pairs.pngCredential pairs execute Final Preparation.
  6. Executes Final Preparation once.

Verifier:

  1. For all credential pairs ../../_images/cred-pairs.pngCredential pairs executes Verification.
  2. Executes final hashing once.

Non-revocation proof

Holder:

  1. Load issuer’s public revocation key ../../_images/issuer-pub-rev-key.pngissuer's public revocation key.

  2. Load the non-revocation credential ../../_images/non-rev-cred-full.pngnon-revocation credential;

  3. Obtain recent V, acc (from verifier, Sovrin link, or elsewhere).

  4. Update ../../_images/non-rev-cred.pngnon-revocation credential:

    ../../_images/Eq27.pngEq27

    Here Vold is taken from witi and updated there.

  5. Select random ../../_images/Eq28.pngEq28;

  6. Compute

    ../../_images/Eq29.pngEq29

    and adds these values to 𝓒.

  7. Compute

    ../../_images/Eq30.pngEq30

    and adds these values to 𝓒.

  8. Generate random ../../_images/Eq31.pngEq31

  9. Compute

    ../../_images/T1-T2.pngT1 and T2

    ../../_images/T3.pngT3

    ../../_images/T4-T8.pngT4 through T8

    and add these values to 𝓣.

Validity proof

Holder:

  1. Generate a random 592-bit number text/0109-anoncreds-protocol/supporting-docs/widetilde%7Bm_j%7D.pngwidetilde{m_j} for each ../../_images/j-in-A_r-bar.pngj \in \mathcal{A}_{\overline{r}}.

  2. For each credential ../../_images/p-cred.pngC_p = ({m_j},A,e,v) and issuer’s public key ../../_images/pk_I.pngpk_I:

    1. Choose random 3152-bit r.

    2. Take ../../_images/n-S.png$n,S$ from ../../_images/pk_I.pngpk_I compute

      ../../_images/Eq32.pngEq32

      and add to 𝓒.

    3. Compute text/0109-anoncreds-protocol/supporting-docs/e%27-full.png$e' \leftarrow e - 2^{596}$.

    4. Generate random 456-bit number ../../_images/e-tilde.pnge-tilde.

    5. Generate random 3748-bit number ../../_images/v-tilde.pngv-tilde.

    6. Compute

    ../../_images/T-full.pngT \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 𝓣.

  3. Load Z,S from issuer’s public key.

  4. For each predicate p where the operator * is one of ../../_images/inequality-symbols.png>, \geq, <, \leq.

    1. Calculate ../../_images/delta.pngdelta such that:

      ../../_images/delta-cases.pngdelta-cases

    2. Calculate a such that:

      ../../_images/a-cases.pnga cases

    3. Find (possibly by exhaustive search) ../../_images/u1-u4.pngu1 through u4 such that:

    ../../_images/delta-full.pngdelta equation

    1. Generate random 2128-bit numbers ../../_images/r1-r_delta.pngr1 through r_delta.
    2. Compute

    ../../_images/T-equations.pngT equations and add these values to 𝓒 in the order ../../_images/T1-T_delta.pngT1 through T_delta.

    1. Generate random 592-bit numbers ../../_images/u1-u4-tilde.pngu1-tilde through u4-tilde.
    2. Generate random 672-bit numbers ../../_images/r1-r_delta-tilde.pngr1 through u_delta-tilde.
    3. Generate random 2787-bit number ../../_images/alpha-tilde.pngalpha-tilde
    4. Compute

    ../../_images/T-bar-and-Q-equations.pngT-bar and Q equations

    and add these values to 𝓣 in the order ../../_images/T1-T_delta-bar.pngT1-bar through Tdelta-bar.

Hashing

Holder computes challenge hash

../../_images/challenge-hash.pngchallenge hash

and sends cH to verifier.

Final preparation

Holder:

  1. For non-revocation credential CNR compute:

    ../../_images/Eq33.pngEq33

    and add them to 𝓧.

  2. For primary credential Cp compute:

    ../../_images/Eq34.pngEq34

    The values ../../_images/Eq35.pngEq35 are the sub-proof for credential Cp.

  3. For each predicate p compute:

    ../../_images/Eq36.pngEq36

    The values ../../_images/Eq37.pngEq37 are the sub-proof for predicate p.

Sending

Holder sends (c,𝓧, {PrC}, {Prp}, 𝓒) to the verifier.

Verification

For the credential pair (Cp, CNR), verifier retrieves relevant variables from 𝓧, {PrC}, {Prp}, 𝓒.

Non-revocation check

Verifier computes:

../../_images/Eq38.pngEq38

../../_images/Eq39.pngEq39

../../_images/Eq40.pngEq40

and adds these values to ../../_images/widehat-T.pngwidehat{T}.

Validity

Verifier uses all issuer public key ../../_images/pk_I.pngpk_I involved into the credential generation and the received ../../_images/Eq41.pngEq41. He also uses revealed ../../_images/rev-attrib.pngRevealed attributes. He initiates ../../_images/widehat-script-T.pngwidehat script T as an empty set.

  1. For each credential Cp, take each sub-proof PrC and compute:

    ../../_images/Eq42.pngEq42

    Add ../../_images/widehat-T.pngwidehat{T} to ../../_images/widehat-script-T.pngwidehat script T.

  2. For each predicate p:

    ../../_images/Eq43.pngEq43

    ../../_images/Eq44.pngEq44

    1. Using Prp and 𝓒 compute

    ../../_images/Eq45.pngEq45

    and add these values to ../../_images/widehat-script-T.pngwidehat script T in the order ../../_images/Eq46.pngEq46.

Final hashing

  1. Verifier computes

    ../../_images/Eq47.pngEq47

  2. If ../../_images/c-eq-c-widehat.pngc = 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.