Introduction

In recent years, identification using electronic certificates such as IDs and passports has become increasingly digitalized. At the same time, there are significant concerns about security and privacy, which is one of the reasons that hinder digitization.

This is where the concept of "Unlinkable Selective Disclosure" becomes important.

Unlinkable Selective Disclosure

Unlinkable Selective Disclosure is the concept which disclosure only necessary information with preserving user’s privacy of personal information.

For example, when you’re joining on the conference in San Francisco and you need to prove your name at the entrance of the venue to enter the conference. If Selective Disclosure works, you can disclose only name via your government-issued ID card which has name, address, date of birth.
Furthermore, If Unlinkable works, when you disclose date of birth via the ID card at the souvenir shop to purchase the alcohol, they can never tell if the name and date of birth are from the same ID card. If Unlinkable doesn’t work, there will be a risk that information previously dislosed in various places could be linked like a puzzle.

The technologies which needs Unlinkable Selective Disclosure are “Verifiable Credential” and “Anonymous Authentication” and so on.

Verifiable Credential

Verifiable Credential is the data format of the Credential such as ID issued by the government, and Vaccination Certificate. W3C and some organizations lead the standardization.

It can be used as a digital ID displayed on a smart phone instead of a physical ID. Through the unlinkable selective disclosure, only the "name" of the personal information on the digital ID can be disclosed, and the other personal information can be hidden.

Anonymous Authentication

Anonymous Authentication is a method of accessing services and resources by proving possession of certain credentials or rights without revealing one's name, address, or other identifying information. For example, when playing adult online games, you can use your government-issued adult credentials to prove that you have the credentials and play the games without disclosing your name or other identifiers.

Digital Signature and Zero-knowledge Proofs

One of the schemes to realize the Unlinkable Selective Disclosure is a scheme that uses Digital Signatures and Zero-knowledge Proofs(ZKP).

In this scheme,

1. A trusted organization provides a digital signature to a set of attributes (m_1, m_2, \ldots m_l) possessed by the user, and send it to the user.
2. The user presents a Zero-knowledge Proof that a subset of the attributes (m_1, m_4) has been signed, while hiding other attributes and the signature value.
3. A verifier verifies the proof based on the disclosed attributes.

Signature Algorithms

This section introduces 3 major signature algorithms for that scheme.

CL signature

CL signature [CL2003] is RSA-ish signature altorithm, based on the strong-RSA assumptions.
This is used in Hyperledger AnonCreds v1 , a form of Verifiable Credential.

Notations:

• k denotes a security parameter for signature
• k_c denotes a security parameter for commitment
• {QR}_{n} denotes a set of quadratic residue mod n
• \langle h \rangle denotes the group generated by h
• a \stackrel{\}{\leftarrow} \mathbb{Z}$ denotes to random an element in the group \mathbb{Z} and substitute it to a
• (m_1, \ldots , m_l) denotes a set of l messages
• |m| denotes a message space
• L denotes the index set of messages
• D denotes the index set of disclosing messages in L
• PK\{(w): s\} denotes Proof of Knowledge which w is a secret value and s is a statement to prove

Key Generation

1. random k-bit prime numbers p,q and k_c-bit prime numbers p_c, q_c
2. calculate n := pq and n_c := p_cq_c
3. random (a_1, \ldots , a_l, b, c) \stackrel{\}{\leftarrow} {QR}_{n}$
4. random h \stackrel{\}{\leftarrow} {QR}_{n_c} , g \stackrel{$}{\leftarrow} \langle h \rangle$
5. set sk := (p, q, p_c, q_c), \, pk := (n, a_1, \ldots , a_l , b , c, n_c, g, h)
6. output sk, pk

Signature Generation

1. random prime e (|e| = |m| + 2)
2. random s (|s| = 3k+|m|)
3. calculate v = (\Pi_{i \in l} m_ib^{s}c)^{\frac{1}{e}} \, mod \, n
4. output \sigma = (s, e, v)

Signature Verification

1. check v^e \stackrel{?}{\equiv} \Pi_{i \in l}a_i^{m_i} \cdot b^s \cdot c \, (mod \, n)
2. check e > 2^{|e|-1}

Proof Generation

1. random w, r_w \stackrel{\}{\leftarrow} \mathbb{Z}_{n}$
2. calculate:
   1. C_x = g^{\sum m_i}h^{r_x} \, mod \, n_c
   2. C_v = v g^{w} (\, mod \, n)
   3. C_w = g^w h^{r_w} (\, mod \, n)
3. generate:
   \pi \in PK\{ (\alpha, \beta, \gamma, \epsilon, \xi, \sigma, \nu): \\            \, \, c \stackrel{?}{=} C_v^{\epsilon}(1/a)^{\epsilon}(1/b)^{\sigma}(1/g)^{\phi} \land \\            \, \, C_w \stackrel{?}{=} g^{\nu}h^{\alpha} \land 1 \stackrel{?}{=} C_w^{\epsilon}(1/g)^{\phi}(1/h)^{\beta} \land \\            \, \, C_x \stackrel{?}{=} g^{\xi}h^{\gamma} \land \\            \, \, 2^{e-1} < \epsilon < 2^e \land 2^{l_m - 1} < \xi < 2^{l_m}\}
4. output (\pi, C_x, C_v, C_w)

Proof Verification

1. verify \pi

BBS+ signature

BBS+ signature [BBS+2006] is pairing-based signature algorithm, based on the q-strong DDH assumptions. It was inspired by BBS signature [BBS2006].
The key size is constant.
This has been specified and discussed by organizations such as MATTR, IETF7 and Decentralized Identity Foundation . Example of implementations is docknetwork library.

For BBS+ signature, signer can choose the pk to be the point of \mathbb{G}_1 or \mathbb{G}_2. Following algorithms describes one of \mathbb{G}_2.

Signature parameter (h_1, \ldots , h_l) doesn’t have to be released as public information, only the seed can be released and recalculated when necessary.

Notations:

• \mathbb{G}_1, \mathbb{G}_2 denotes the groups of the bilinear curve, which has p elements
• g_1, g_2 denotes generators of \mathbb{G}_1, \mathbb{G}_2
• a \stackrel{\}{\leftarrow} \mathbb{Z}$ denotes to random an element in the group \mathbb{Z} and substitute it to a
• (m_1, \ldots , m_l) denotes a set of l messages
• e denotes the biliner map (=pairing) of e: \mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_T
• L denotes the index set of messages
• D denotes the index set of disclosing messages in L
• SPK\{(w): s\}(nonce) denotes Signature based on a proof of knowledge which w is a secret value, s is a statement to prove and nonce is the random parameter to sign

Key Generation

1. random (h_0, \ldots , h_l) \stackrel{\}{\leftarrow} \mathbb{G}_{1}^{l+1}$
2. random x \stackrel{\}{\leftarrow} \mathbb{Z}_p^{\ast}$
3. calculate X := g_2^x
4. set sk := (x), pk := (X, h_0, \ldots , h_l)
5. output sk, pk

Signature Generation

1. random e,s \stackrel{\}{\leftarrow} \mathbb{Z}_{p}$
2. calculate A := (g_1 \cdot h_0^s \cdot \Pi_{i \in l} h_i ^{m_i})^{\frac{1}{x + e}}
3. output \sigma = (A, e, s)

Signature Verification

1. check e(A, X \cdot g_2^{e}) \stackrel{?}{=} e(g_1 \cdot h_0^s \cdot \Pi_{i \in L} h_i ^{m_i}, g_2)

Proof Generation

1. calculate b = g_1 \cdot h_0^s \cdot \Pi_{i \in l} h_i ^{m_i}
2. random r_1 \stackrel{\}{\leftarrow} \mathbb{Z}{p}^{\ast}, r_2 \stackrel{$}{\leftarrow} \mathbb{Z}{p}$
3. calculate r_3 = \frac{1}{r_1}
4. calculate:
   1. A' := A^{r_1}
   2. \bar{A} := A'^{-e} \cdot b^{r_1} (= A'^{x})
   3. d := b^{r_1} \cdot h_0^{-r_2}
   4. s' := s - r_2 \cdot r_3
   5. \pi \in SPK\{( \{m_i\}_{i \notin D}, e, r_2, r_3, s' ): \\        \quad \frac{\bar{A}}{d} = A'^{-e} \cdot h_0^{r_2} \land \\        \quad g_1 \cdot \Pi_{i \in D}h_i^{m_i} = d^{r_3} \cdot h_0^{-s'} \Pi_{i \notin D} h_i^{-m_i} \\ \}(nonce)
5. output (A', \bar{A}, d, \pi)

Proof Verification

1. check A' \stackrel{?}{\neq} 1_{\mathbb{G}_1}
2. check e(A', X) \stackrel{?}{=} e(\bar{A}, g_2)
3. verify \pi

PS signature

PS signature [PS2016] is pairing-based signature algorithm, based on PS assumptions.
The signing algorithm is so simple and efficient.
This has been adopted in hyperledger AnonCreds v2 . Example of implementations is docknetwork library.

Notations:

• \mathbb{G}_1, \mathbb{G}_2 denotes the groups of the bilinear curve, which has p elements
• g_1, \tilde{g} denotes generators of \mathbb{G}_1, \mathbb{G}_2
• a \stackrel{\}{\leftarrow} \mathbb{Z}$ denotes to random an element in the group \mathbb{Z} and substitute it to a
• (m_1, \ldots , m_l) denotes a set of l messages
• e denotes the biliner map (=pairing) of e: \mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_T
• L denotes the index set of messages
• D denotes the index set of disclosing messages in L
• SPK\{(w): s\}(nonce) denotes Signature based on a proof of knowledge which w is a secret value, s is a statement to prove and nonce is the random parameter to sign

Key Generation

1. random l+1 secrets (x, y_1, \ldots , y_l) \stackrel{\}{\leftarrow} \mathbb{Z}_{p}^{l+1}$
2. calculate (\tilde{g}, \tilde{X}, \tilde{Y_1}, \ldots , \tilde{Y_l})  := (\tilde{g}, \tilde{g}^x, \tilde{g}^{y_1}, \ldots , \tilde{g}^{y_l})
3. set sk := (x, y_1, \ldots , y_l), pk := (\tilde{g}, \tilde{X}, \tilde{Y_1}, \ldots , \tilde{Y_l})
4. output sk, pk

Signature Generation

1. random w \stackrel{\}{\leftarrow} \mathbb{Z}_{p}^{\ast}$
2. calculate h := g_1^{w}
3. calculate (\sigma_1, \sigma_2)  := (h, h^{x + \sum_{i \in L}y_i \cdot m_i})
4. output \sigma = (\sigma_1, \sigma_2)

Signature Verification

1. check \sigma_1 \stackrel{?}{\neq} 1_{\mathbb{G}_1}
2. check e(\sigma_1, \tilde{X} \cdot \Pi_{i \in L}\tilde{Y}_i^{m_i}) \stackrel{?}{\neq} e(\sigma_2, \tilde{g})

Proof Generation

1. random r,t \stackrel{\}{\leftarrow} \mathbb{Z}_{p}$
2. calculate:
   1. \sigma_1' := \sigma_1^{r}
   2. \sigma_2' := (\sigma_2 \cdot \sigma_1^t)^r
   3. \pi \in SPK\{( \{m_i\}_{i \notin D}, t ): \\        \quad e(\sigma_1', \tilde{X}) \cdot \Pi_{i \in D}e(\sigma_1', \tilde{Y}_i)^{m_i} \cdot e(\sigma_1', \tilde{g})^t \\        \quad \quad \stackrel{?}{=}            e(\sigma_2', \tilde{g})          \}(nonce)
3. output (\sigma_1', \sigma_2', \pi)

Proof Verification

1. verify \pi

References

1. [CL2003]
   Jan Camenisch, and Anna Lysyanskaya, ”A signature scheme with efficient protocols ”in SCN 02, set. LNCS, Stelvio Cimato, Clemente Galdi, and Giuseppe Persiano, Eds., vol. 2576, Springer, Heidelberg, Sep. 2003, pp. 268–289.
2. [GS2004]
   Dan Boneh, Xavier Boyen, and Hovav Shacham, “Short group signatures”in Advances in Cryptology - CRYPTO, 2004, pp. 44-55.
3. [BBS2006]
   Isamu Teranishi, and Kazue Sako, K., ”k-Times Anonymous Authentication with a Constant Proving Cost” in: Yung, M., Dodis, Y., Kiayias, A., Malkin, T. (eds) Public Key Cryptography - PKC 2006. PKC 2006. Lecture Notes in Computer Science, vol 3958. Springer, Berlin, Heidelberg., 2006, pp 525–542.
4. [BBS+2006]
   Man Ho Au, Willy Susilo, and Yi Mu,“ Constant-Size Dynamic k-TAA ”in SCN 06, ser. LNCS, R. D. Prisco, and M. Yung, Eds., vol. 4116. Springer, Heidelberg, Sep. 2006, pp. 111-125.
5. [PS2016]
   David Pointcheval and Olivier Sanders, ”Short Randomizable Signatures ”in Proceedings of the RSA Conference on Topics in Cryptology - CTRSA 2016, vol. 9610. Springer, Heidelberg, 2016, pp. 111–126.