<aside> 📘 Series:
该系列介绍了 Anonumous Credential（Anoncred）/Attribute-Based Credential（ABC）的概念，背后的算法原理 selective disclosure，具体的实现 CL signature、BBS+ signature。
Anonymous Credential Part 1: Brief Overview and History
Anonymous Credential Part 2: Selective Disclosure and CL Signature
Anonymous Credential Part 3: BBS+ Signature
</aside>
As discussed in in Part 1 of this series, selective disclosure and an anonymous credential (Anoncred) relies on an efficient signature scheme that supports multiple messages with a single signature. One such signature scheme is known as CL signature that is named after its Jan Camenisch and Anna Lysyanskaya in a series of papers from 2001 to 2004 [CL01, CL02, CL03, CL04]. CL signature popularized Anoncreds, and it also served as a cryptographic building block in Identity Mixer (Idemix) and Hyperledger Indy projects.
Here, we first discuss two important concepts for understanding CL signature—the discrete logarithm problem and cryptographic commitment—and then outline subprotocols of CL signature. Finally, the application of CL signature on selective disclosure is discussed.
Given real numbers y and a, the value of m from an expression y=a^m can be calculated by evaluating a logarithm of y to base a, i.e. m=log_a(y). The term m = log_a(y) can be easily calculated when all a,m,y>=0 are Real numbers. However, when y and a are members of a sufficiently large discrete group G, finding m becomes extremely difficult. This is known as the discrete logarithm problem, which serves as the foundation of many modern cryptographic protocols, including CL-signature.
<aside> 📘 Discret Logarithm Problem, DLP
最常见的形式是 $g^a \equiv b \mod p$，已知 g、b、p（质数），求算 a？
当 g、b、p 非常大时，该计算目前只能通过遍历求解，可以认为是无法在有效时间内被破解。
</aside>
A commitment scheme is a cryptographic protocol that allows one to commit to a message while keeping it hidden to other parties, with the ability to reveal the committed value later. A commitment scheme that is considered here is known as the Pedersen commitment. In its simplified version, a commitment c of a message m is simply c = a^m where a is a member of a large discrete group G. The commitment c can be sent to another person, called the receiver, and the receiver will not be able to calculate m due to the hardness of the discrete logarithm problem.
At a later time, the message m can then be revealed to the receiver. The receiver then verifies that the message m is really the one that was committed by checking that the expression a^m is really equal to c.
A more detailed discussion on Pedersen commitment can be found here.
<aside> 📘 Hashing Collision
使用 HASH 函数作为签名时，需要特别考虑两个特性：
pedersen commitment 仍然可能面对 collision 的威胁。它和哈希相比最主要的特性是 homomorphic，使其可以被用于构建 ZKP。
</aside>
Originally, CL signature is based on the strong RSA (SRSA) assumption. As a result, its key sizes are very long to provide sufficient security against ever faster prime factorization algorithms and computers. There has been an improvement on this issue by using paring-based cryptography.
Here, for simplicity, we discuss the signing algorithm base on the strong RSA (SRSA) assumption. We consider two parties, namely an issuer, a holder, and a verifier. The issuer signs a signature on blocks of messages (or attributes) for the holder, and the holder then shares the messages together with the signature to the verifier. We assume that the holder has L messages m_1, m_2, m_3, …, m_L. The CL signature scheme consists of 3 steps: