Anonymous Credential Part 3: BBS+ Signature

This series of three parts was co-written by:
— Dr Nuttawut Kongsuwan, Finema & QTFT
— Rachata Tosirisuk, Thailand Internet Exchange, Finema & QTFT

• Anonymous Credential Part 1: Brief Overview and History
• Anonymous Credential Part 2: Selective Disclosure and CL Signature
• Anonymous Credential Part 3: BBS+ Signature

Photo by Scott Graham on Unsplash

Despite its huge successes as core building blocks for anonymous credential (Anoncred) systems, the CL signature relies on the strong RSA assumption of which security is based on the practical difficulty of factoring the product of two large prime numbers. To achieve sufficient security, CL signature-based Anoncred systems require long keys and signatures, resulting in slow cryptographic operations.

On the other hand, the BBS+ signature relies on the q-Strong Diffie Hellman (q-SDH) assumption with pairing-based elliptic-curve cryptography that requires much shorter keys and signatures than the CL signature to achieve the same level of security. This article explains simplified mathematics for understanding BBS+ signature, as described in [CDL16], where all formal proofs are neglected.

Here, we assume the knowledge of the following topics:

• Abstract algebra, including group theory and finite fields
• Elliptic-curve cryptography over finite fields
• Discrete logarithm problem
• Diffie–Hellman assumption (DH), including Computational Diffie–Hellman assumption (CDH) and Decisional Diffie–Hellman assumption (DDH)

First, we describe bilinear pairing, which is an underlying mathematical operation for generating and verifying the BBS+ signature. This is followed by a brief explanation for q-SDH assumption. Three operations of the BBS+ signature are explained: namely (i) key generation, (ii) signature generation, and (iii) signature verification. Finally, we discuss the signature proof of knowledge as an essential privacy-preserving mechanism for the BBS+ signature.

Bilinear Pairing

Unlike the CL signature that generates keys and signatures from two large prime numbers, the BBS+ signature uses pairing-friendly elliptic-curves.

First, we define cyclic groups G_1 and G_2 of the same prime order p. Given g_1 as a generator of G_1 and g_2 as a generator of G_2, we can generate another third group G_T of also the prime order pusing a bilinear map e as follows:

The bilinear map e is a polynomial-time computable map that generates an element in G_T such that:

, where g1, g2 and g_T are generators of groups G_1, G_2 and G_T. The bilinear map e also satisfies the following properties

• Bilinearity:

• Non-degeneracy:

In the BBS+ signature, G_1 and G_2 are defined as groups of points on elliptic curves over finite fields. Therefore, they are written as additive groups. On the other hand, G_T is a finite field, and we can write G_T as a multiplicative group. Given P_1and P_2 as points on G_1 and G_2, we could rewrite the map e as follows:

As a result, we can write the e pairing as:

q-SDH Assumption

The security of the BBS+ signature is based on the q-Strong Diffie-Hellman (q-SDH) assumption [TS10]. This assumption was first defined by Boneh and Boyen in [BB04]. It is based on the Diffie-Hellman assumption over two cyclic groups G_1 and G_2 of prime order p where there might be an efficiently computable homomorphism ψ (in polynomial time) from G_2 to G_1.

BBS+ Signature

Following the previous sections that explain bilinear pairing and the q-SDH assumptions as building blocks, this section discusses the BBS+ signature. This signature scheme consists of three operations: (i) key generation, (ii) signature generation, and (iii) signature verification.

Given L messages (m_1, m_2, ..., m_L):

the BBS+ signature produces a public key that consists of L+2 variables(w, h_0, h_1, h_2, ..., h_L):

The signature σ of the messages can then be defined by 3 variables(A, e, s:

(i) Key generation

The BBS+ keys can be generated as follows:

• Generate L+1 random elements (h_0, h_1, h_2, ..., h_L) from group G_1:

• Generate a random number x as a secret key:

• Compute w:

(w, h_0, h_1, h_2, ..., h_L) are used as a public key:

(ii) Signature generation

Given the secret key x, a BBS+ signature of the messages (m_1, m_2, ..., m_L) can be generated as follows:

• Generate random numbers e and s:

• Compute A:

The signature σ is defined as(A, e, s):

(iii) Signature Verification

Given

• The messages (m_1, m_2, ..., m_L)
• The public key (w, h_0, h_1, h_2, ..., h_L)
• The signature σ

We can verify the signature by computing and comparing the LHS and RHS following equation:

This equation works because of the property of the bilinear pairing:

Signature Proof of Knowledge (SPK)

The prover can prove the knowledge of the signature without revealing the signature itself by using non-interactive zero-knowledge proof of knowledge. The prover can also choose to only disclose some of the messages to the verifier, hiding the rest of the messages.

We define the revealed messages as:

where D be the set of messages that the prover chooses to reveal to the verifier. Similarly, we define the hidden messages as:

The prover computes a signature proof of knowledge, denoted as SPK, which can be made non-interactive with the Fiat-Shamir heuristic [FS87] in the random oracle model [BR93] [CDL16].

The signature proof of knowledge consists of two operations: proof generation and proof verification

(i) Proof Generation

Given the secret key x and the signature σ, the prover can generate the signature proof of knowledge (SPK) by:

• Generate random numbers r_1, r_2:

• Set r_3, A', \bar{A}, d and s' as follows:

From the variables above, the prover can create the signature proof of knowledge (SPK) π [CDL16]

The SPK π consists of two subproofs, concatenated with a logical AND operator ^. The first subproof proves the validity of the signature σ whereas the second subproof proves the validity of the hidden attributes.

Finally, the proof of knowledge corresponds to (A', \bar{A}, d, \pi), which can then be sent to a verifier.

It is important to emphasize that the proof reveals neither the signature σ nor any of its variables (A, e, s). Hence, a verifier who receives the proof will be unable to obtain or derive the signature σ from the proof.

(ii) Proof Verification

The verifier can verify the proof as follows:

• Verify that:

where 1_{G_1} is the identity of the group G_1. Note that the probability that the above equation does not hold is negligible for an honest signer.

• Compute and compare the LHS and RHS of the following equation:

• Verify the SPK π, as shown above.

Conclusion

Compared to the CL signature, the BBS+ signature has much shorter keys and signatures for a comparable level of security. As a result, the BBS+ signature enables fast implementation for anonymous credentials. It can be used in combination with signature proof of knowledge to hide some of credential attributes/messages in a zero-knowledge fashion.

Recently, the open-source code for implementing BBS+ signature is available in Hyperledger Ursa. This is known as Anonymous Credential 2.0 and is documented extensively here.

The BBS+ signature will also soon be available in Finema’s Identity Wallet! We are excited to see how this technology will make an impact to the society in the coming years.

References

[FS87] Amos Fiat and Adi Shamir. How to prove yourself: Practical solutions to identification and signature problems. In Andrew M. Odlyzko, editor, CRYPTO’86, volume 263 of LNCS, pages 186{194. Springer, Heidelberg, August 1987.

[BR93] Mihir Bellare and Phillip Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. In V. Ashby, editor, ACM CCS 93, pages 62{73. ACM Press, November 1993.

[BB04] Dan Boneh and Xavier Boyen. Short signatures without random oracles. In Christian Cachin and Jan Camenisch, editors, EUROCRYPT 2004, volume 3027 of LNCS, pages 56–73. Springer, Heidelberg, May 2004.

[BBS04] Dan Boneh, Xavier Boyen, and Hovav Shacham. Short group signatures. In Matthew Franklin, editor, CRYPTO 2004, volume 3152 of LNCS, pages 41–55. Springer, Heidelberg, August 2004.

[GPS08] Steven D. Galbraith, Kenneth G. Paterson, and Nigel P. Smart. Pairings for cryptographers. Discrete Applied Mathematics, 156(16):3113–3121, 2008.

[TS10] Naoki Tanaka & Taiichi Saito. (2010). On the q-Strong Diffie-Hellman Problem. IACR Cryptology ePrint Archive. 2010. 215.

[CDL16] Jan Camenisch, Manu Drijvers, and Anja Lehmann. Anonymous attestation using the strong Diffie Hellman assumption revisited. In TRUST, volume 9824 of Lecture Notes in Computer Science, pages 1–20. Springer, 2016.