<aside> 📘 Series:

该系列介绍了 Anonumous Credential（Anoncred）/Attribute-Based Credential（ABC）的概念，背后的算法原理 selective disclosure，具体的实现 CL signature、BBS+ signature。

</aside>

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

A (Relatively Easy To Understand) Primer on Elliptic Curve Cryptography

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 $p$ using a bilinear map $e$ as follows:

$$ e: \mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_T $$

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

$$ e(g_1, g_2) = g_T $$

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

Bilinearity:

$$ \begin{align} \forall x,y &\in \mathbb{Z} \notag \\ e(g_1^x, g_2^y) &= e(g_1^y, g_2^x) \notag \\ e(g_1^x, g_2^y) &= e(g_1, g_2)^{xy} \notag \end{align} $$