v2.5

Decentralized Identity and Data

ONTOLOGY ELEMENTS

GUIDES & TUTORIALS

SUPPORT

Anonymous Credentials

A zero knowledge proof signature algorithm

The anonymous credential scheme is a part of the Ontology Crypto library that provides several cryptography related utilities for the Ontology network. The main features provided by the crypto library basically revolve around digital signature. It provides general APIs for processing digital signatures and keys.

Abstract

There are **three **parties involved in an anonymous credential scheme, namely the **issuer**, the **user **(prover), and the **verifier**.

The issuer provides a certificate to the user. This certificate contains a list of the user's attributes and the issuer's signature (using BBS+signature). This protocol is formally called **credential issuance protocol. **The user who is in possession of the credentials can selectively disclose some parts to a verifier. This protocol is formally called **credential presentation protocol**.

Background

BBS + Signature

$G_1, G_2$

and $G_t\ .$

Pairing function $e: G_1*G_2 \rightarrow G_t \ ,$

where $G_1$

and $G_2$

are both of order $p$

.
Common parameters: - â€‹$g_1$is the generator of$G_1$
- â€‹$g_2$is the generator of$G_2$
- â€‹$H_{rand} \ , h_1, ... \ , h_L$are elements from$G_1$

$x$

from uniform distribution on $Z_p$

, output $s_k = x \ ,\ p_k = {g_2}^x$

$(s_k, m_1, ... \ , m_L)$

$E$

and $s$

are selected from $Z_p$

. First$B = g_1 * {H_{Rand}}^s * ({h_1}^{m_1} * ... * {h_L}^{m_L})$

is calculated, and then $A = B^{1/(E+x)}$

is computed. The signature is $(A, B, E, s)$

$(p_k, m_1, ...\ ,m_L, sig)$

$sig$

as $(A, B, E, s)$

, and check if $e(A, {g_2}^E * p_k) == e(B, g_2)$

and whether $B == g_1 * {H_{Rand}}^s * ({h_1}^{m_1} * ... * {h_L}^{m_L})$

Non-Interactive Proof of Knowledge (PoK) protocol

In this subsection, we will look at an example of the non-interactive proof of knowledge protocol which proves that the public key is generated as specified in the BBS + signature scheme. That is,

$\pi = PoK \{ x : w = {g_2}^x \ \&\& \ \_g_2 = \_{g_1}^x\}$

. This means the prover proves the knowledge of $x$

such that ${g_2}^x = w$

and $\_g_2 = \_{g_1}^x$

. It is assumed that $w, g_2, \_g_1, \_g_2$

are all public.The protocol that we provide is a standard sigma protocol. It involves three steps, which are commit, challenge, and response. Sigma protocol is an interactive protocol and can be modified to be a non-interactive zero knowledge proof by using the well-known **Fiat-Shamir heuristic**. The proof

$\pi = \{ C, S\}.$

1. Commitment (Prover)

1

r = rand(Zp)

2

â€‹

3

t1 = g2^r

4

â€‹

5

t2 = _g1^r

Copied!

2. Proof (Prover)

1

P = t1 || t2 || g2 || _g1 || w || _g2 //join them together in binary format

2

â€‹

3

C = hash_to_int(P) //C is challenge

4

â€‹

5

S = (r + C * x) mod p //response to verifier

Copied!

3. Verify (Verifier)

1

_t1 = g2^S * w^(-c)

2

â€‹

3

_t2 = _g1^S * _g2^(-c)

4

â€‹

5

_P = _t1 || _t2 || g2 || _g1 || w || _g2

6

â€‹

7

_C = hash_to_int(_P)

8

â€‹

9

// use C to compare with _C, which was calculated just now

10

if C == _C {

11

return true

12

} else {

13

return false

14

}

Copied!

Setup of the Issuer's key pair

Given an array of the attribute names

`AttributeNames`

, the issuer's key pair is generated in the following manner:- 1.Select a random element$x$from$Z_p$, and compute$w = {g_2}^x$â€‹
- 2.Select a random element$\_g_1$from$G_1$, and compute$\_g_2 = \_{g_1}^x$â€‹
- 3.Generate non-interactive proof of knowledge$\pi = PoK\{ x: w = {g_2}^x \ \&\& \ {\_g_1}^x \} = (C, S)$Here,

`r`

**:**A random element$r$from$Z_p$`t1`

**:**Computed as$t_1 = {g_2}^r$`t2`

**:**Computed as$t_2 = \_{g_1}^r$`C`

**:**$C = H(t_1 || t_2 || g_2 || \_g_1||w||\_g_2)$`s`

**:**$S = (r + C *x) \bmod p$

4. Select an array of elements from

$G_1$

from `AttributeNames`

. Next, calculate `HAttrs[i] = random(G1)`

for each attribute in `AttributeNames`

5. Select two random elements

`HRand`

And `HSk`

from $G_1$

6. The issuer's public key is set to `ipk = (w, _g1, _g2, Ï€, HAttrs, AttributeNames, HRand, HSk)`

, and the private key is set to `isk = x`

7. Return `isk`

and `ipk`

The following are the reference data structures for the issuer's key pair:

1

type IssuerSecretKey struct {

2

x BigNum

3

}

Copied!

1

type IssuerPublicKey struct {

2

AttributeNames []string

3

HAttrs []G1Point // one G1-element for one attribute

4

HRand G1Point // a random G1 point

5

HSk G1Point // a random G1 point to encode user's secret key

6

â€‹

7

w G2Point // element from G2

8

_g1 G1Point // point of G1

9

_g2 G1Point // point of G1

10

â€‹

11

//PoK{x: w = g2^x && _g2 = _g1^x}

12

C BigNum // challenge

13

S BigNum // response

14

}

Copied!

Issuance Protocol

Issuance protocol is an interactive protocol that consists of the following steps:

- 1.
- 2.The user creates a
**credential request**using the public key, the secret, and the nonce. This request consists of a commitment to the user secret (can be seen as a public key), and a zero-knowledge proof of the knowledge of the user secret key. The user**sends**this credential request to the issuer - 3.The
**issuer verifies**the credential request by verifying the zero-knowledge proof If the request is**valid**, the issuer issues a credential to the user by**signing**the**commitment**to the secret key along with the attribute values and then**sends**the credential back to the user - 4.The
**user verifies**the issuer's**signature**and**stores**the**credential**that consists of the signature value, a randomness used to create the signature, the user secret, and the attribute values

The following diagram represents the interaction between the user and the issuer:

- The credential request CredRequest contains a commitment$N_{ym}$to user's secret key which is of the form${H_{Sk}}^{sk}$and a
`zk-PoK`

of the$N_{ym}$ - Credential contains the
`BBS+signature`

on the attributes and the`Nym`

Generating credential request

The user generates the credential request using the attribute values and the nonce as input. The process is as follows:

- 1.Select a random element
**sk**from$Z_p$as the user's master secret key - 2.Calculate$N_{ym} = {H_{Sk}}^{sk}$, which represents the commitment to the user's master secret
- 3.Generate the zero knowledge proof$\pi = PoK \{ sk : N_{ym} = {H_{Sk}}^{sk} \} = (C, S)$in the following manner-

- Select a random element$sk$from$Z_p$which acts as the user's master secret
- Calculate$t_1 = {H_{Sk}}^r$
- Compute the challenge$C = H(t_1 || H_{Sk}||N_{ym}||nonce)$
- Compute the response$S = (r+C*sk) \bmod p$

The data structure of the credential request is of the following manner:

1

type CredRequest struct {

2

Nym G1Point //commitment to user's master secret

3

IssuerNonce BigNum //nonce

4

Attrs []BigNum //user's attributes

5

â€‹

6

//PoK that Nym is constructed as in the issuance protocol

7

// i.e. PoK{(sk): HSk^sk = Nym }

8

C BigNum //challenge in Sigma-protocol

9

S BigNum //response in Sigma-protocol

10

}

Copied!

Issuing Credential

After receiving the credential request from the user, the issuer verifies

$\pi = (C, S)$

and generates credentials for the user. The credential is generated using the issuer's private key $i_{sk}$

as follows:- 1.Select two random elements$e, s$from$Z_p$
- 2.Calculate
`B = g1 Â· HRand^s Â· Nym Â· MulAll(HAttrs[i]^(Attrs[i]))`

- 3.Compute
`A = B^(1/(e+x))`

- 4.Return the credential$(A, B, e, s, Attrs)$

The data structure of a credential looks something like:

1

type Credential struct {

2

A G1Point

3

B G1Point

4

e BigNum

5

s BigNum

6

Attrs []BigNum

7

}

Copied!

Presentation Protocol

In the presentation protocol, the prover tries to convince the verifier that they are aware of some secret input, such that some hypothetical predicate is true. A typical example of a predicate is that the prover is in possession of an anonymous credential, and they can selectively disclose certain attributes while hiding the other attributes.

The information that is available to the user is:

- User's secret key$sk$and its commitment$N_{ym}$
- Attribute values$attrs = (a_1, ...\ , a_L)$
- BBS +signature
`(A, B, e, s)`

- Extra input
- (D, I)
**:**Attribute predicate, describes what attributes will be disclosed. If`D[j] == 1`

,`I[j] = attrs[j] = aj`

, else`I[j] = null`

Proving Algorithm

The selective disclosure proof can be generated in the following manner:

- 1.Randomize A
**:**Select a random element$r_1$from${Z_p}^*$, and compute$A' = A^{r_1}$ - 2.Calculate$\_A = A'^{(âˆ’e)} \ Â· B^{r_1},\ r_3 = 1/r_1$
- 3.Select an element$r_2$from$Z_p$
- 4.Calculate$B' = B^{r_1} Â· {H_{Rand}}^{-r_2}$,$s' = s - r_2 Â· r_3$
- 5.Generate zero knowledge proof$\pi = PoK\{ (s_k, {a_i}\_{hidden}, e, r_2, r_3, s') \}$such that-

`_A/B' = A'^(-e) Â· HRand^r2`

`g1 Â· MulAll(hi^ai_reveal) = (B')^r3 Â· HRand^(-s') Â· HSk^(-sk) Â·MulAll(hi^(-ai_hidden))`

, where`hi`

stands for`HAttrs[i]`

The proof can be generated as follows:

1

r_ai : for i belongs to _D(attributes not disclosed), means D[i]==0

2

r_e : random from Zp

3

r_r2 : random from Zp

4

r_r3 : random from Zp

5

r_s' : random from Zp

6

r_sk : random from Zp

7

E : E = HSk^r_sk

8

t1 : t1 = A'^r_e Â· HRand^r_r2

9

t2 : t2 = (B')^r_r3 Â· HRand^r_s' Â· E^(-1) Â· MulAll(hi^r_ai)

10

c' : c' = H(A', _A, B', nym, t1, t2, g1, HRand, h1, ... , hL, w)

11

nonce : nonce, with Ï„ bit length, randomly generated again

12

c : c = H(nonce, c', (D, I))

13

s_sk : s_sk = r_sk + c Â· sk

14

s_ai : s_ai = r_ai - c Â· ai, for i belongs to _D(attributes not disclosed)

15

s_e : s_e = r_e - c Â· e

16

s_r2 : s_r2 = r_r2 + c Â· r2

17

s_r3 : s_r3 = r_r3 + c Â· r3

18

s_s' : s_s' = r_s' - c Â· s'

19

Ï€ : {c, s_sk, {s_ai}, s_e, s_r2, s_r3, s_s', nonce}, i belong to _D

Copied!

The output is

$(A', \_A, d, n_{ym}, \pi)$

where $\pi = \{c, s_{sk}, s_{ai}, s_e, s_{r_2}, s_{r_3}, {s_s}', nonce\}$

Here is the reference data structure for the zero knowledge proof:

1

type Proof struct {

2

APrime G1Point // randomized credential signature values

3

ABar G1Point // randomized credential signature values

4

BPrime G1Point // randomized credential signature values

5

â€‹

6

/* challenge in sigma-protocol */

7

ProofC BigNum

8

/* response in sigma-protocol */

9

ProofSSk BigNum

10

ProofSE BigNum

11

ProofSR2 BigNum

12

ProofSR3 BigNum

13

ProofSSPrime BigNum

14

ProofSAttrs []BigNum

15

â€‹

16

Nonce BigNum // nonce used to avoid replay attack

17

Nym G1Point

18

}

Copied!

Verification

The verifier has the following input information available:

- $(A', \_A, B', n_{ym}, \pi)$: from the signer
- $\{c, s_{sk}, {s_{a_i}}, s_e, s_{r_2}, s_{r_3}, {s_s}', nonce\}$: obtained by parsing$\pi$

The verification algorithm proceeds as in the following manner:

- 1.Check if
`A' != 1`

in G1; if false, return`false`

. - 2.Check if
`e(A', w) == e(_A, g2)`

; if false, return`false`

. This is$z_k-PoK$for**A**. - 3.Parse$\pi$:
`{c, s_sk, {s_ai}, s_e, s_r2, s_r3, s_s', nonce} <- Ï€`

; if failed, return`false`

. - 4.~$t_1$:
`~t1 = A'^s_e Â· HRand^s_r2 Â· (_A/B')^(-c)`

. This is$z_k-PoK$for**e**,**r2***.* - 5.~$t_2$:
`(B')^s_r3 Â· HRand^s_s' Â· HSk^(-s_sk) Â· MulAll(hi^(-s_ai)) Â· (g1Â·MulAll(hi^ai))^(-c)`

- the
`i`

above, first`MulAll( )`

belongs to`_D`

, where`D[i]==0(false)`

- the
`i`

above, second`MulAll( )`

belongs to`D`

, where`D[i]==1(true)`

This is$Z_k - PoK$for**r3**,**s'**,**gsk**,**ai**of _D. - 6.$c'$:
`c' = H(nonce, H(A', _A, B', nym, ~t1, ~t2, g1, HRand, h1, ... , hL, w), (D, I))`

- 7.Check if
`c == c'`

: if false, return`false`

. Otherwise return`true`

.

â€‹

Last modified 2yr ago