Permutation $\pi$ 零知识证明

1. 背景知识

Prover 需要在不reveal permutation π \pi π的基础上，证明其确实知道 π \pi π，且在收到Verifier challenge信息后，Prover对challenge 信息采用相同的 π \pi π处理并将处理后的消息发送给Verifier，Verifier应可验证所收到的消息确实是采用了相同的permutation π \pi π处理，尽管其并不知道具体的permutation π \pi π内容。 在Jens Groth 2010年论文《A Verifiable Secret Shuffle of Homomorphic Encryptions》和Stephanie Bayer和Jens Groth 2012年论文《Efficient Zero-Knowledge Argument for Correctness of a Shuffle》中，均有对permutation π \pi π证明算法实现，具体也可结合这两篇博客来看：

• 博客Efficient Zero-Knowledge Argument for Correctness of a Shuffle学习笔记（1） 第2节内容。
• 博客A Verifiable Secret Shuffle of Homomorphic Encryptions学习笔记 第3节内容。

假设均针对长度为 N = n m N=nm N=nm的Permutation π \pi π进行证明，且均采用Pedersen commitment规则：

2. Groth2010的permutation π \pi π零知识证明

Jens Groth 2010年论文《A Verifiable Secret Shuffle of Homomorphic Encryptions》的思路为： Common Input: public commitment key c k ck ck。【length为 N + 1 N+1 N+1】 Prover’s witness: permutation π ∈ ∑ N \pi\in\sum_{N} π∈∑N​。 证明：在不暴露permutation π \pi π的前提下，Verifier给challenge(s)，Prover respond，Verifier需验证：Prover确实知道某permutation π \pi π；Prover respond的消息内采用了相同的permutation π \pi π。

1）Prover：对permutation π \pi π进行commit c = c o m c k = ( π ( 1 ) , ⋯   , π ( N ) ; r ) c=com_{ck}=(\pi(1),\cdots,\pi(N);r) c=comck​=(π(1),⋯,π(N);r)，其实就是对数字 1 , ⋯   , N 1,\cdots,N 1,⋯,N的permutation commit。只需证明 c c c为a commit to a permutation of the numbers 1 , ⋯   , N 1,\cdots,N 1,⋯,N，这样就可以保证the prover is bound to some permutation he knows, but the permutation remains hidden. 同时选 N N N个随机数 − d 1 , ⋯   , − d N -d_1,\cdots,-d_N −d1​,⋯,−dN​用于保护permutation π \pi π不被reveal，对这些随机数进行commit c d = c o m c k ( − d 1 , ⋯   , − d N ; r d ) c_d=com_{ck}(-d_1,\cdots,-d_N;r_d) cd​=comck​(−d1​,⋯,−dN​;rd​)。 将 c c c和 c d c_d cd​发送给Verifier。 2）Verifier：Challenges t 1 , ⋯   , t N t_1,\cdots,t_N t1​,⋯,tN​。【length为 N N N】 3）Prover：对收到的 t 1 , ⋯   , t N t_1,\cdots,t_N t1​,⋯,tN​按相同的permutation π \pi π进行permute，计算 s i = t π ( i ) + d i s_i=t_{\pi(i)}+d_i si​=tπ(i)​+di​。Prover给Verifier发送 s 1 , ⋯   , s N s_1,\cdots,s_N s1​,⋯,sN​。【length为 N N N】 4）Prover：提供证明 s i s_i si​ have been formed correctly, using the same permutation π \pi π that used to form c c c。 Common Input: c k ck ck、 c c c、 c d c_d cd​、 ( s 1 , ⋯   , s N ) (s_1,\cdots,s_N) (s1​,⋯,sN​)以及 t 1 , ⋯   , t N t_1,\cdots,t_N t1​,⋯,tN​。 Prover’s witness: permutation π ∈ ∑ N \pi\in\sum_{N} π∈∑N​。 证明： s 1 , ⋯   , s N s_1,\cdots,s_N s1​,⋯,sN​中的permutation π \pi π和commitment c c c中的permutation π \pi π是相同的。

• Verifier：challenge λ \lambda λ
• Common input：构建向量 ( m 1 , ⋯   , m N ) = ( λ ⋅ 1 + t 1 , ⋯   , λ ⋅ N + t N ) (m_1,\cdots,m_N)=(\lambda\cdot 1+t_1,\cdots,\lambda\cdot N+t_N) (m1​,⋯,mN​)=(λ⋅1+t1​,⋯,λ⋅N+tN​)（构建依据为 c c c为a commit to a permutation of the numbers 1 , ⋯   , N 1,\cdots,N 1,⋯,N）。
• Prover： （1）利用witness permutation π \pi π构建向量 ( m π ( 1 ) , ⋯   , m π ( N ) ) = ( λ π ( 1 ) + t π ( 1 ) , ⋯   , λ π ( N ) + t π ( N ) ) (m_{\pi(1)},\cdots,m_{\pi(N)})=(\lambda\pi(1)+t_{\pi(1)},\cdots, \lambda\pi(N)+t_{\pi(N)}) (mπ(1)​,⋯,mπ(N)​)=(λπ(1)+tπ(1)​,⋯,λπ(N)+tπ(N)​)，引入随机值 ρ = r λ + r d \rho=r\lambda+r_d ρ=rλ+rd​，Prover可计算 c λ = c o m c k ( λ π ( 1 ) + t π ( 1 ) , ⋯   , λ π ( N ) + t π ( N ) ; ρ ) = c o m c k ( m π ( 1 ) , ⋯   , m π ( N ) ; ρ ) c_{\lambda}=com_{ck}(\lambda\pi(1)+t_{\pi(1)},\cdots,\lambda\pi(N)+t_{\pi(N)};\rho)=com_{ck}(m_{\pi(1)},\cdots,m_{\pi(N)};\rho) cλ​=comck​(λπ(1)+tπ(1)​,⋯,λπ(N)+tπ(N)​;ρ)=comck​(mπ(1)​,⋯,mπ(N)​;ρ)。 实际上，利用commitment的加法同态性，Verifier和Prover均可获得 c λ = c λ c d c o m c k ( s 1 , ⋯   , s N ; 0 ) c_{\lambda}= c^{\lambda}c_dcom_{ck}(s_1,\cdots,s_N;0) cλ​=cλcd​comck​(s1​,⋯,sN​;0)。 从而 c λ c_{\lambda} cλ​为common input，无需传递。 （2）已知 c λ = c o m c k ( m π ( 1 ) , ⋯   , m π ( N ) ; ρ ) c_{\lambda}= com_{ck}(m_{\pi(1)},\cdots,m_{\pi(N)};\rho) cλ​=comck​(mπ(1)​,⋯,mπ(N)​;ρ)和 ( m 1 , ⋯   , m N ) (m_1,\cdots,m_N) (m1​,⋯,mN​)，证明Prover知道相应的permutation π \pi π和randomizer ρ \rho ρ：（显然地，可以借助博客博客A Verifiable Secret Shuffle of Homomorphic Encryptions学习笔记第二节的“shuffle of known contents 明文shuffle证明”来实现。同时注意，其中的challenge x x x可复用以上（1）中的challenge λ \lambda λ）
• Prover和Verifier：均计算 c λ = c λ c d c o m c k ( s 1 , ⋯   , s N ; 0 ) c_{\lambda}= c^{\lambda}c_dcom_{ck}(s_1,\cdots,s_N;0) cλ​=cλcd​comck​(s1​,⋯,sN​;0)。
• Prover：复用 x = λ x=\lambda x=λ，复用之前的 c d = − c d , c = c λ c_d=-c_d,c=c_{\lambda} cd​=−cd​,c=cλ​，从而有：

由此，即完成整个permutation π \pi π零知识证明。

3. Groth2012的permutation π \pi π零知识证明

Stephanie Bayer和Jens Groth 2012年论文《Efficient Zero-Knowledge Argument for Correctness of a Shuffle》的思路为： Prover’s witness: permutation π ∈ ∑ N \pi\in\sum_{N} π∈∑N​。 Common Input: public commitment key c k ck ck。【length为 n + 1 n+1 n+1】（将 ( π ( 1 ) , ⋯   , π ( N ) ) (\pi(1),\cdots,\pi(N)) (π(1),⋯,π(N))向量以 n n n行 m m m列的矩阵表示，减少 c k ck ck的长度减少 m m m倍。） 证明：在不暴露permutation π \pi π的前提下，Verifier给challenge(s)，Prover respond，Verifier需验证：Prover确实知道某permutation π \pi π；Prover respond的消息内采用了相同的permutation π \pi π。

1）Prover：将 ( π ( 1 ) , ⋯   , π ( N ) ) (\pi(1),\cdots,\pi(N)) (π(1),⋯,π(N))向量以 n n n行 m m m列的矩阵表示 A = a ⃗ = ( a ⃗ 1 , ⋯   , a ⃗ m ) = { π ( i ) } i = 1 N A=\vec{a}=(\vec{a}_1,\cdots,\vec{a}_m)=\{\pi(i)\}_{i=1}^N A=a =(a 1​,⋯,a m​)={π(i)}i=1N​，逐列进行commit c ⃗ A = c o m c k ( A ; r ⃗ ) = c o m c k ( a ⃗ ; r ⃗ ) = ( c o m c k ( a ⃗ 1 ; r 1 ) , ⋯   , c o m c k ( a ⃗ m ; r m ) ) \vec{c}_A=com_{ck}(A;\vec{r})=com_{ck}(\vec{a};\vec{r})=(com_{ck}(\vec{a}_1;r_1),\cdots,com_{ck}(\vec{a}_m;r_m)) c A​=comck​(A;r )=comck​(a ;r )=(comck​(a 1​;r1​),⋯,comck​(a m​;rm​))，其实就是对数字 1 , ⋯   , N 1,\cdots,N 1,⋯,N的permutation commit。 将 c ⃗ A \vec{c}_A c A​发送给Verifier。【length为 m m m】【第一组commitment】 2）Verifier：Challenges x x x。【length为 1 1 1】 3）Prover：采用相同的permutation π \pi π构建 n n n行 m m m列的矩阵 B = b ⃗ = ( b ⃗ 1 , ⋯   , b ⃗ m ) = { x π ( i ) } i = 1 N B=\vec{b}=(\vec{b}_1,\cdots,\vec{b}_m)=\{x^{\pi(i)}\}_{i=1}^N B=b =(b 1​,⋯,b m​)={xπ(i)}i=1N​，逐列进行commit c ⃗ B = c o m c k ( B ; s ⃗ ) = c o m c k ( b ⃗ ; s ⃗ ) = ( c o m c k ( b ⃗ 1 ; s 1 ) , ⋯   , c o m c k ( b ⃗ m ; s m ) ) \vec{c}_B=com_{ck}(B;\vec{s})=com_{ck}(\vec{b};\vec{s})=(com_{ck}(\vec{b}_1;s_1),\cdots,com_{ck}(\vec{b}_m;s_m)) c B​=comck​(B;s )=comck​(b ;s )=(comck​(b 1​;s1​),⋯,comck​(b m​;sm​)) Prover给Verifier发送 c ⃗ B \vec{c}_B c B​。【length为 m m m】【第二组commitment】 4）Prover：提供证明 c ⃗ B \vec{c}_B c B​ have been formed correctly, using the same permutation π \pi π that used to form c ⃗ A \vec{c}_A c A​。 Prover提供argument，证明其知道相应的openings of the commitments to permutations of respectively 1 , … , N 1,…,N 1,…,N和 x 1 , … , x N x^1,…,x^N x1,…,xN，同时证明这两组commitment采用的是相同的permutation。【即第二组commitment是对 x 1 , … , x N x^1,…,x^N x1,…,xN permuted in an order that was fixed before the prover saw x x x】。

• 4.1 为了证明两组commitment采用的是相同的permutation，Verifier给Prover random challenges y y y和 z z z。
• 4.2 Prover commit to 一系列 d 1 − z = y π ( 1 ) + x π ( 1 ) − z , … , d N − z = y π ( N ) + x π ( N ) − z d_1-z=y\pi(1)+x^{\pi(1)}-z,…,d_N-z=y\pi(N)+x^{\pi(N)}-z d1​−z=yπ(1)+xπ(1)−z,…,dN​−z=yπ(N)+xπ(N)−z。使用product argument，即可证明 ∏ i = 1 N ( d i − z ) = ∏ i = 1 N ( y i + x i − z ) \prod_{i=1}^{N}(d_i-z)= \prod_{i=1}^{N}(yi+x^i-z) ∏i=1N​(di​−z)=∏i=1N​(yi+xi−z)等式成立。【想象其为 z z z的N阶多项式， d i d_i di​是对其root根 y i + x i yi+x^i yi+xi的permute，基于Schwartz-Zippel lemma可知，针对特定的 z z z值Prover伪造找到相应 d i d_i di​值使该等式成立的概率不高于 N q − 1 \frac{N}{q-1} q−1N​，可忽略。同理，针对 y y y值，Prover伪造两组commitment使等式成立的概率也可忽略。】 方法一： 直接将 { d i − z } i = 1 N \{d_i-z\}_{i=1}^N {di​−z}i=1N​发送给Verifier，Verifier验证等式成立即可。但由于 d i − z = y π ( i ) + x π ( i ) − z d_i-z=y\pi(i)+x^{\pi(i)}-z di​−z=yπ(i)+xπ(i)−z，Verifier对 x , y , z x,y,z x,y,z均已知，其可以直接猜测出相应的 π ( i ) \pi(i) π(i)，相当于 π \pi π被reveal了，违背了 π \pi π的零知识要求。 方法二： 构建 n n n行 m m m列矩阵 E = { d i − z } i = 1 N = ( e 11 , ⋯   , e n m ) = ( e ⃗ 1 , ⋯   , e ⃗ m ) E=\{d_i-z\}_{i=1}^N=(e_{11},\cdots,e_{nm})=(\vec{e}_1,\cdots,\vec{e}_m) E={di​−z}i=1N​=(e11​,⋯,enm​)=(e 1​,⋯,e m​)， 这样 ∏ i = 1 N ( d i − z ) \prod_{i=1}^{N}(d_i-z) ∏i=1N​(di​−z)可理解为矩阵 F F F中所有元素的乘积，亦可再次理解为每行乘积之后所有行的乘积。 ⇒ \Rightarrow ⇒对矩阵 E E E逐行乘积形成新的向量 f ⃗ = ( ∏ j = 1 m e 1 j , ⋯   , ∏ j = 1 m e n j ) = ( f 1 , ⋯   , f n ) \vec{f}=(\prod_{j=1}^{m}e_{1j},\cdots,\prod_{j=1}^{m}e_{nj})=(f_1,\cdots,f_n) f ​=(∏j=1m​e1j​,⋯,∏j=1m​enj​)=(f1​,⋯,fn​)，这样 ∏ i = 1 N ( d i − z ) = ∏ i = 1 n ∏ j = 1 m e i j = ∏ i = 1 n ( ∏ j = 1 m e i j ) = ∏ i = 1 n f i \prod_{i=1}^{N}(d_i-z)=\prod_{i=1}^{n}\prod_{j=1}^{m}e_{ij}=\prod_{i=1}^{n}(\prod_{j=1}^{m}e_{ij})=\prod_{i=1}^{n}f_i ∏i=1N​(di​−z)=∏i=1n​∏j=1m​eij​=∏i=1n​(∏j=1m​eij​)=∏i=1n​fi​ Verifier对 ∏ i = 1 N ( y i + x i − z ) \prod_{i=1}^{N}(yi+x^i-z) ∏i=1N​(yi+xi−z)中的 x , y , z x,y,z x,y,z均已知，可将其理解为某常量值 f f f。 构建 n n n行 m m m列矩阵 − z -z −z并对其逐列进行commit有 c ⃗ − z = c o m c k ( − z , ⋯   , − z ; 0 ⃗ ) \vec{c}_{-z}=com_{ck}(-z,\cdots,-z;\vec{0}) c −z​=comck​(−z,⋯,−z;0 )。 基本思路为： 利用commitment的加法同态性，对矩阵 E E E逐列commit值为 c ⃗ E = c ⃗ A y c ⃗ B c ⃗ − z \vec{c}_E=\vec{c}_A^y\vec{c}_B\vec{c}_{-z} c E​=c Ay​c B​c −z​。Verifier可直接计算该值。 对向量 f f f commit c f = c o m c k ( f ⃗ ; s ) = c o m c k ( f 1 , ⋯   , f n ; s ) c_f=com_{ck}(\vec{f};s)=com_{ck}(f_1,\cdots,f_n;s) cf​=comck​(f ​;s)=comck​(f1​,⋯,fn​;s)。

接下来，赋值 矩 阵 A = 矩 阵 E ， b ⃗ = f ⃗ ， b = f 矩阵A=矩阵E，\vec{b}=\vec{f}，b=f 矩阵A=矩阵E，b =f ​，b=f，就可以结合博客Efficient Zero-Knowledge Argument for Correctness of a Shuffle学习笔记（2）来理解了。

4. Groth 2010年论文《Short Pairing-based Non-interactive Zero-Knowledge Arguments》中的permutation argument

在博客Short Pairing-based Non-interactive Zero-Knowledge Arguments中介绍了Groth 2010年论文《Short Pairing-based Non-interactive Zero-Knowledge Arguments》中的permutation argument，与以上2和3中的permutation argument不同，相应的permutation ρ \rho ρ为public known。 Witness： a 1 , ⋯   , a n a_1,\cdots,a_n a1​,⋯,an​及 b 1 , ⋯   , b n b_1,\cdots,b_n b1​,⋯,bn​ Public info：permutation ρ \rho ρ Prover：计算 c = c o m c k ( a 1 , ⋯   , a n ; r a ) c=com_{ck}( a_1,\cdots,a_n;r_a) c=comck​(a1​,⋯,an​;ra​)和 d = c o m c k ( b 1 , ⋯   , b n ; r b ) d=com_{ck}(b_1,\cdots,b_n;r_b) d=comck​(b1​,⋯,bn​;rb​)