CL Signature

published at: https://t.me/laiskynotes/164

最简单的实现就是基于 RSA 的 CL Signature，这一算法的基础为 Discrete Logarithm Problem 和 strong RSA assumption：

1. DLP: g^a = b mod p，即使已知 g、b、p，也很难求出 a。
2. strong-RSA assumption: 大质因数的乘法很简单，但是分解质因数很难。

基于上述两个理论，我们可以构建 Pedersen 签名：

这是对 L 条隐私消息所生成的签名，隐私消息为 m。a、b、c、n 是公钥，e、s、v 是 issuer 生成的签名。

（省略的细节：issuer 持有私钥 p、q，n = pq。这里的 p、q 是生成签名的关键，作为私钥仅被 issuer 所见）

也就是说，方程中的 (m,a,b,c,n,e,s,v) 都是公开的，由 issuer 背书。但是 verifier 仍然需要拿到 m 的值才能验证这一方程。verifier 验证的方式就是让方程的两侧相等即可。

这个签名最巧妙的地方在于，它的整个方程是一个 DLP（形如 g^a = b mod p），它的每一个因子也是一个 DLP（如乘积中的每一项 a^m mod n 本身就是一个 DLP）。我们已知 DLP 中的 m 是无法被逆运算的，所以 holder 有两种披露信息的方式来使得 verifier 得以验证方程：

1. 提供 m_i 的明文值，这样就披露了信息，verifier 可以验证 m_i 的真实性
2. 不披露 m_i 的明文，而是披露 (a_i ^ m_i) mod n 的值，这样 verifier 无法验证这个 m_i，但是可以验证整个方程的真实性

issuer 可以灵活地同时组合运用上述两种方式，想要披露的地方使用 m_i 明文，不想要披露的地方使用 (a_i ^ m_i) mod n 的值。这样最终 verifier 可以验证整个方程的真实性，但是又只能看到 issuer 所选择披露的 m 信息。这也就实现了我们前文所述的 ABC。