1. 引言

Groth和Kohlweiss 2015年论文《One-out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin》

• 针对a list of commitments其中至少有一个commitment opens to 0 0 0 的场景，构建了一个3-move public coin special honest verifier zero-knowledge proof，称之为Sigma-protocol。
  在该protocol中，Prover不需要know openings of the other commitments。
  communication cost 为 O ( log ⁡ N ) O(\log N) O(logN)，其中 N N N为commitments的数量。

• 基于本文的Sigma-protocol，实现了ring signature和zerocoin—— a novel mechanism for bitcoin privacy。
  将Sigma-protocol作为a (linkable) ad-hoc group identification scheme，其中users have public keys that are commitments and demonstrate knowledge of an opening for one of the commitments to unlinkably identify themselves (once) as belonging to the group。
  在group identification scheme中使用Fiat-Shamir transform，即可实现ring signatures。
  将ring signatures与the linkable group identification scheme结合，则实现了zerocoin。

• 本文的ring signature基于discrete logarithm assumption，无需trusted setup。

• Sigma-protocol可用于实现membership proof of a secret committed value belonging to a public list of values。

当使用Pedersen commitment时，其具有computationally sound，仅需依赖discrete logarithm assumption。

∑ \sum ∑-protocol应用广泛，当使用cyclic prime-order groups或RSA-type groups时，都存在efficient ∑ \sum ∑-protocol，如 the identification schemes of Schnorr [Sch91] and Guillou-Quisquater [GQ88]。

∑ \sum ∑-protocol的一个优点是：很容易使用Fiat-Shamir heuristic来实现non-interactive。从而有利于使用 ∑ \sum ∑-protocol来构建digital signature schemes和encryption schemes，which are non-interactive in nature。

1.1 本文贡献

主要考虑的场景为：

• public info： N N N个commitments c 0 , ⋯   , c N − 1 c_0,\cdots,c_{N-1} c0​,⋯,cN−1​
• private info： l ∈ { 0 , ⋯   , N − 1 } l\in\{0,\cdots,N-1\} l∈{0,⋯,N−1} 以及 r ∈ Z q r\in\mathbb{Z}_q r∈Zq​
• relation： c l = C o m c k ( 0 ; r ) c_l=Com_{ck}(0;r) cl​=Comck​(0;r)

本文构建的相应sigma-protocol ∑ \sum ∑-protocol ：

• communication cost为： 4 log ⁡ N 4\log N 4logN commitments in G \mathbb{G} G和 3 log ⁡ N + 1 3\log N+1 3logN+1 elements in Z q \mathbb{Z}_q Zq​。
• Prover computation：约 N log ⁡ N N\log N NlogN exponentiations。
• Verifier computation：约 N N N exponentiations。

若Prover知道所有commitments的openings，则其computation会更快。

任何具有加法同态属性的commitment scheme都可使用：

• Pedersen commitment
• EIGamal encryption的变种，其中message is encoded as an exponent。即使用 g m y r g^my^r gmyr而不是标准的 m y r my^r myr。

另一个Prover知道所有commitments的openings的例子是 membership proof，即：
Prover有a commitment c = C o m c k ( u ) c=Com_{ck}(u) c=Comck​(u)，然后想prove knowledge of an opening to a value u u u that belongs to a list L = { λ 0 , ⋯   , λ N − 1 } \mathcal{L}=\{\lambda_0,\cdots,\lambda_{N-1}\} L={λ0​,⋯,λN−1​}。证明思路可为：
形成commitments c 0 = c ⋅ C o m c k ( − λ 0 ) , ⋯   , c N − 1 = c ⋅ C o m c k ( − λ N − 1 ) c_0=c\cdot Com_{ck}(-\lambda_0),\cdots,c_{N-1}=c\cdot Com_{ck}(-\lambda_{N-1}) c0​=c⋅Comck​(−λ0​),⋯,cN−1​=c⋅Comck​(−λN−1​)，然后prove knowledge of an opening of one of the commitments to 0 0 0。由于此处的special structure of the commitments c 0 , ⋯   , c N − 1 c_0,\cdots,c_{N-1} c0​,⋯,cN−1​，Prover computation仅为 2 N log ⁡ N 2N\log N 2NlogN multiplications in Z q \mathbb{Z}_q Zq​，Verifier computation为 2 N 2N 2N multiplications in Z q \mathbb{Z}_q Zq​。相比于Bayer和Groth 2013年论文《Zero-Knowledge Argument for Polynomial Evaluation with Application to Blacklists》中membership proof的Prover和Verifier computation 均为 O ( N log ⁡ 2 N ) O(N\log ^2 N) O(Nlog2N) 有了大幅改进。

2. ∑ \sum ∑-protocol

3. ∑ \sum ∑-protocol for commitment to 0 or 1

关注的场景为：

• public info：commitment c c c。
• private info： m , r m,r m,r
• relation： m ∈ { 0 , 1 } m\in\{0,1\} m∈{0,1}

核心思想为：
若 m ∈ { 0 , 1 } m\in\{0,1\} m∈{0,1}，则 m ( 1 − m ) = 0 m(1-m)=0 m(1−m)=0成立。

相应的证明为：

4. ∑ \sum ∑-protocol for one out of N N N commitments containing 0

针对的场景为：

• public info： N N N个commitments c 0 , ⋯   , c N − 1 c_0,\cdots,c_{N-1} c0​,⋯,cN−1​
• private info： l ∈ { 0 , ⋯   , N − 1 } l\in\{0,\cdots,N-1\} l∈{0,⋯,N−1} 以及 r ∈ Z q r\in\mathbb{Z}_q r∈Zq​
• relation： c l = C o m c k ( 0 ; r ) c_l=Com_{ck}(0;r) cl​=Comck​(0;r)

核心思想为：
若one of the commitments contains 0，等价为 存在an index l l l 使得 ∏ i = 0 N − 1 c i δ i l \prod_{i=0}^{N-1}c_i^{\delta_{il}} ∏i=0N−1​ciδil​​为a commitment to 0，其中 δ i l \delta_{il} δil​为Kronecker’s delta，即 δ l l = 1 \delta_{ll}=1 δll​=1 and δ i l = 0 \delta_{il}=0 δil​=0 for i ≠ l i\neq l i​=l。

假设 N = 2 n N=2^n N=2n，将 i , l i,l i,l以二进制表示： i = i 1 ⋯ i n , l = l 1 ⋯ l n i=i_1\cdots i_n, l=l_1\cdots l_n i=i1​⋯in​,l=l1​⋯ln​，则 δ i l \delta_{il} δil​可表示为 δ i l = ∏ j = 1 n δ i j l j \delta_{il}=\prod_{j=1}^{n}\delta_{i_jl_j} δil​=∏j=1n​δij​lj​​，从而转换为证明 ∏ i = 0 N − 1 c i ∏ j = 1 n δ i j l j \prod_{i=0}^{N-1}c_i^{\prod_{j=1}^{n}\delta_{i_jl_j}} ∏i=0N−1​ci∏j=1n​δij​lj​​​ 为 a commitment to 0：

• Prover：make commitments c l 1 , ⋯   , c l n c_{l_1},\cdots,c_{l_n} cl1​​,⋯,cln​​ to the bits l 1 , ⋯   , l n l_1,\cdots,l_n l1​,⋯,ln​。
  然后执行图1的 n n n parallel ∑ \sum ∑-protocol来 prove knowledge of openings of these commitments to values l j ∈ { 0 , 1 } l_j\in\{0,1\} lj​∈{0,1}。