Efficient Protocols for Set Membership and Range Proof 学习笔记

1. 引言

Camenisch等人2008年发表在AsiaCrypto的论文《Efficient Protocols for Set Membership and Range Proof》。

相关代码见：

• https://github.com/ing-bank/zkrp/blob/master/ccs08【Go】
• https://github.com/boltlabs-inc/libzkchannels/blob/master/src/ccs08.rs【Rust】
• https://github.com/appliedzkp/semaphore【Solidity & Java】

本论文针对的场景为：

• public info：commitment C C C，discrete set Φ = { ϕ 1 , ϕ 2 , ⋯   , ϕ n } \Phi=\{\phi_1,\phi_2,\cdots, \phi_n\} Φ={ϕ1​,ϕ2​,⋯,ϕn​}
• private info： σ \sigma σ
• relation： C = C o m ( σ ) C=Com(\sigma) C=Com(σ) 且 σ ∈ Φ \sigma\in\Phi σ∈Φ【换种方式可表达为： C = C o m ( ϕ 1 ) C=Com(\phi_1) C=Com(ϕ1​) 或 C = C o m ( ϕ 2 ) C=Com(\phi_2) C=Com(ϕ2​) 或 C = C o m ( ϕ 3 ) C=Com(\phi_3) C=Com(ϕ3​) …… 或 C = C o m ( ϕ n ) C=Com(\phi_n) C=Com(ϕn​)。】

其中discrete set Φ \Phi Φ可为a list of cities or clubs，也可为整数范围如 [ 1 , 2 20 ] [1,2^{20}] [1,220]。

若采用基于RSA假设的commitment scheme，则仅需要在Prover和Verifier之间交互a constant number of RSA-group elements。 若采用基于bilinear group假设的commitment scheme，之前的研究成果需要 O ( k ) O(k) O(k)个group elements，其中 k k k为security parameter。

基于bilinear group假设， Φ \Phi Φ为整数范围时，本文提供的set-membership proof算法，仅需 O ( k log ⁡ k − log ⁡ log ⁡ k ) O(\frac{k}{\log k-\log\log k}) O(logk−loglogkk​) 个group elements。【当 Φ \Phi Φ为整数范围时，set-membership proof也可称为range proof。】

1.1 主要创新

可使用 Σ \Sigma Σ-protocol来进行OR证明，具体可参见 基于Sigma protocol实现的零知识证明protocol集锦 2.3节“Protocol 3. Disjunction (OR) of discrete logs”，其proof length 与 条件数 n n n 呈正比。

本文分别基于Strong RSA assumption 和 bilinear group assumption 构建的proof size为 O ( 1 ) O(1) O(1)，与条件数 n n n 无关。

1.1.1 range proof

range proof为set membership proof的特例情况，set Φ \Phi Φ对应为a range [ a , a + 1 , a + 2 , ⋯   , b ] [a,a+1,a+2, \cdots, b] [a,a+1,a+2,⋯,b]（可表示为 [ a , b ] [a,b] [a,b]）。 若基于Strong RSA assumption，则已有efficient proofs的研究成果。但是当range范围较小 或 同一range范围被使用多次时，本文提供的算法效率更高，优于8~10倍。

若不想基于Strong RSA assumption，可改为：Prover对其 secret s s s 的所有 k k k个bits都进行commit，然后证明这 k k k个commitments all encode either a 0 0 0 or a 1 1 1，以及证明这些commitments确实是commit to all the bits of s s s。这样，Verifier即可信任 s s s在 [ 0 , 2 k + 1 − 1 ] [0,2^{k+1}-1] [0,2k+1−1]范围内，因为只有 k k k个commitments。这种方式可推广为任意范围，相应的proof size为 O ( k ) O(k) O(k) 个group elements。

也可不采用二进制，而选择更优的 u u u进制来表示secret s s s，然后对每个digit进行commit生成 ℓ \ell ℓ个commitments，再证明 s ∈ [ 0 , u ℓ ] s\in[0,u^\ell] s∈[0,uℓ]。不过，采用 Σ \Sigma Σ-protocol的 OR proof 来证明每个commitment 对应的digit为 [ 0 , u ) [0,u) [0,u)，相应的proof size 为 O ( u ) O(u) O(u)。因此总的proof size仍为 O ( u ⋅ ℓ ) O(u\cdot \ell) O(u⋅ℓ)，并未减少proof size。

本文的算法在 Σ \Sigma Σ-protocol的基础上进行了改进，相应的proof size为 O ( u + ℓ ) O(u+\ell) O(u+ℓ)。通过选择合适的 u u u和 ℓ \ell ℓ值，可实现proof size为 O ( k log ⁡ k − log ⁡ log ⁡ k ) O(\frac{k}{\log k-\log\log k}) O(logk−loglogkk​)。

2. 相关定义

• set membership proof 以及 range proof定义：
• bilinear group computational assumption定义：
• Strong Diffie-Hellman Assumption（q-SDH假设）：

3. 基于签名的set membership

受Jan Camenisch等人2007年论文《Simulatable adaptive oblivious transfer》中的oblivious transfer不经意传输协议启发，核心思想为：

• Verifier发送给Prover a signature of every element in the set Φ \Phi Φ。【可在其它membership proofs中复用】
• 然后，Prover收到a signature on the particular element σ \sigma σ， σ \sigma σ对应的commitment为 C C C。
• 然后，Prover对收到的签名进行blind，运行a proof of knowledge that she possesses a signature on the committed element。

以上proof的communication complexity取决于 Φ \Phi Φ中的元素数——因为一开始Verifier就需要发送 a signature of every element in the set Φ \Phi Φ，剩下的communication complexity为a constant number of group elements。