A Verifiable Secret Shuffle of Homomorphic Encryptions学习笔记

A Verifiable Secret Shuffle of Homomorphic Encryptions为Jens Groth 2010年论文，提出了多个算法：

基于a commitment containing a permutation of a set of publicly known messages的证明算法。
基于密文（具有同态属性加密的密文）的shuffle证明算法【7-move public coin HVZK argument】，该算法具有如下特点： 1）argument size与所使用的加密系统无关，且比shuffle本身的size也要小； 2）使用了multi-exponentiation和batch-verification技术。 3）基于Neff[36]样式，无需trusted setup：polynomials being identical under permutation of their roots。
基于a combined shuffle-and-decrypt operation正确性的证明算法。【该算法可用于采用EIGamal encryption构建的mix-nets的decrypt。将shuffle和decrypt combine一起比分别单独操作可节约计算资源。】

1. homomorphic cryptosystems同态加密系统 1.1 Homomorphic Encryption 同态加密

满足要求的有Paillier encryption[45]和EIGamal encryption[16]。在这里插入图片描述

1.2 Homomorphic Commitment

commitment应具有hiding和binding属性。满足要求的有Pedersen commitment： c = c o m c k ( m 1 , ⋯ , m n ; r ) = g 1 m 1 ⋯ g n m n h r c=com_{ck}(m_1,\cdots,m_n;r)=g_1^{m_1}\cdots g_n^{m_n}h^r c=comck(m1,⋯,mn;r)=g1m1⋯gnmnhr。在这里插入图片描述

2. shuffle of known contents 明文shuffle证明。

Common input：commit key c k ck ck 和 messages m 1 , ⋯ , m n m_1,\cdots,m_n m1,⋯,mn。 Witness：permutation π \pi π 和 randomizer r r r。 Prover： c = c o m c k ( m π ( 1 ) , ⋯ , m π ( n ) ; r ) c=com_{ck}( m_{\pi(1)},\cdots,m_{\pi(n)};r) c=comck(mπ(1),⋯,mπ(n);r)。证明： c c c为messages m 1 , ⋯ , m n m_1,\cdots,m_n m1,⋯,mn的 shuffle commitment。

基本原理有：多项式 p ( X ) = ∏ i = 1 n ( m i − X ) p(X)=\prod_{i=1}^{n}(m_i-X) p(X)=∏i=1n(mi−X) is stable under permutation of the roots for any permutation π \pi π，即 p ( X ) = ∏ i = 1 n ( m i − X ) = ∏ i = 1 n ( m π ( i ) − X ) p(X)=\prod_{i=1}^{n}(m_i-X)= \prod_{i=1}^{n}(m_{\pi(i)}-X) p(X)=∏i=1n(mi−X)=∏i=1n(mπ(i)−X) 转为证明：witness μ 1 , ⋯ , μ n , r \mu_1,\cdots,\mu_n,r μ1,⋯,μn,r使得 c = c o m c k ( μ 1 , ⋯ , μ n ; r ) c=com_{ck}(\mu_1,\cdots,\mu_n;r) c=comck(μ1,⋯,μn;r)， ∏ i = 1 n ( m i − X ) = ∏ i = 1 n ( μ i − X ) \prod_{i=1}^{n}(m_i-X)= \prod_{i=1}^{n}(\mu_i-X) ∏i=1n(mi−X)=∏i=1n(μi−X)成立，由于working over a field Z q \mathbb{Z}_q Zq，等式成立意味着存在permutation π \pi π，使得 μ i = m π ( i ) \mu_i=m_{\pi(i)} μi=mπ(i)。

Verifier给Prover：random challenge x ∈ Z q x\in\mathbb{Z}_q x∈Zq。转为证明： ∏ i = 1 n ( m i − x ) = ∏ i = 1 n ( μ i − x ) \prod_{i=1}^{n}(m_i-x)= \prod_{i=1}^{n}(\mu_i-x) ∏i=1n(mi−x)=∏i=1n(μi−x)

整体思路为： 1）证明knowledge of opening μ 1 , ⋯ , μ n , r \mu_1,\cdots,\mu_n,r μ1,⋯,μn,r of c c c。借助sigma-protocol思路：

Prover: commit to random d 1 , ⋯ , d n d_1,\cdots, d_n d1,⋯,dn， 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)。Prover将 c d c_d cd发送给Verifier。
Verfier: Challenge e e e。
Prover：for i = 1 , ⋯ , n i=1,\cdots,n i=1,⋯,n，计算 f i = e μ i + d i ， z = e r + r d f_i=e\mu_i+d_i，z=er+r_d fi=eμi+di，z=er+rd，将 f 1 , ⋯ , f n , z f_1,\cdots,f_n,z f1,⋯,fn,z发送给Verifier。
Verifier：验证 c e c d = c o m c k ( f 1 , ⋯ , f n ; z ) c^ec_d=com_{ck}(f_1,\cdots,f_n;z) cecd=comck(f1,⋯,fn;z)成立，即完成证明knowledge of opening μ 1 , ⋯ , μ n , r \mu_1,\cdots,\mu_n,r μ1,⋯,μn,r of c c c。

2）Verifier收到 f 1 , ⋯ , f n f_1,\cdots,f_n f1,⋯,fn后，构建 f i − e x = e ( μ i − x ) + d i f_i-ex=e(\mu_i-x)+d_i fi−ex=e(μi−x)+di，有 ∏ i = 1 n ( f i − e x ) = e n ∏ i = 1 n ( μ i − x ) + p n − 1 ( e ) \prod_{i=1}^{n}(f_i-ex)=e^n\prod_{i=1}^{n}(\mu_i-x)+p_{n-1}(e) ∏i=1n(fi−ex)=en∏i=1n(μi−x)+pn−1(e)，其中 p n − 1 ( ⋅ ) p_{n-1}(\cdot) pn−1(⋅)为 n − 1 n-1 n−1阶多项式。转为证明 ∏ i = 1 n ( f i − e x ) = e n ∏ i = 1 n ( μ i − x ) + p n − 1 ( e ) = e n ∏ i = 1 n ( m i − x ) + p n − 1 ( e ) \prod_{i=1}^{n}(f_i-ex)=e^n\prod_{i=1}^{n}(\mu_i-x)+p_{n-1}(e)=e^n\prod_{i=1}^{n}(m_i-x)+p_{n-1}(e) ∏i=1n(fi−ex)=en∏i=1n(μi−x)+pn−1(e)=en∏i=1n(mi−x)+pn−1(e)，由于 e e e为随机选择的，即可证明 ∏ i = 1 n ( m i − x ) = ∏ i = 1 n ( μ i − x ) \prod_{i=1}^{n}(m_i-x)= \prod_{i=1}^{n}(\mu_i-x) ∏i=1n(mi−x)=∏i=1n(μi−x)成立。为了证明 ∏ i = 1 n ( f i − e x ) = e n ∏ i = 1 n ( m i − x ) + p n − 1 ( e ) \prod_{i=1}^{n}(f_i-ex)=e^n\prod_{i=1}^{n}(m_i-x)+p_{n-1}(e) ∏i=1n(fi−ex)=en∏i=1n(mi−x)+pn−1(e)，思路如下：

Prover：commit to random Δ 1 , Δ 2 , ⋯ , Δ n − 1 , Δ n \Delta_1,\Delta_2,\cdots,\Delta _{n-1},\Delta_n Δ1,Δ2,⋯,Δn−1,Δn，其中 Δ 1 = d 1 \Delta_1=d_1 Δ1=d1以保证后续的 F 1 = f 1 − e x F_1=f_1-ex F1=f1−ex， Δ n = 0 \Delta_n=0 Δn=0以保证后续的 F n = e ∏ i = 1 n ( m i − x ) F_n=e\prod_{i=1}^{n}(m_i-x) Fn=e∏i=1n(mi−x)。除 Δ 1 和 Δ n \Delta_1和\Delta_n Δ1和Δn之外，其它 Δ i \Delta_i Δi均为随机值。因为构建的$ f Δ j = − e ∏ i = 1 j ( u i − x ) d j + 1 − e ( u j + 1 − x ) Δ j + e Δ j + 1 − Δ j d j + 1 = e ( Δ j + 1 − ( u j + 1 − x ) Δ j − ∏ i = 1 j ( u i − x ) d j + 1 ) − Δ j d j + 1 f_{\Delta_j}=-e\prod_{i=1}^{j}(u_i-x)d_{j+1}-e(u_{j+1}-x)\Delta_j+e\Delta_{j+1}-\Delta_jd_{j+1}=e(\Delta_{j+1}-(u_{j+1}-x)\Delta_j-\prod_{i=1}^{j}(u_i-x)d_{j+1})-\Delta_jd_{j+1} fΔj=−e∏i=1j(ui−x)dj+1−e(uj+1−x)Δj+eΔj+1−Δjdj+1=e(Δj+1−(uj+1−x)Δj−∏i=1j(ui−x)dj+1)−Δjdj+1，Prover需分别对 ( Δ j + 1 − ( u j + 1 − x ) Δ j − ∏ i = 1 j ( u i − x ) d j + 1 ) (\Delta_{j+1}-(u_{j+1}-x)\Delta_j-\prod_{i=1}^{j}(u_i-x)d_{j+1}) (Δj+1−(uj+1−x)Δj−∏i=1j(ui−x)dj+1)和 − Δ j d j + 1 -\Delta_jd_{j+1} −Δjdj+1进行commit： c Δ = c o m c k ( − Δ 1 d 2 , ⋯ , − Δ n − 1 d n ; r Δ ) c_{\Delta}=com_{ck}(-\Delta_1d_2,\cdots,-\Delta_{n-1}d_n;r_{\Delta}) cΔ=comck(−Δ1d2,⋯,−Δn−1dn;rΔ)， c a = c o m c k ( ( Δ 2 − ( u 2 − x ) Δ j − ∏ i = 1 1 ( u i − x ) d 2 ) , ⋯ , ( Δ n − ( u n − x ) Δ n − 1 − ∏ i = 1 n − 1 ( u i − x ) d n ) ; r a ) c_a=com_{ck}((\Delta_2-(u_2-x)\Delta_j-\prod_{i=1}^{1}(u_i-x)d_2),\cdots,(\Delta_n-(u_n-x)\Delta_{n-1}-\prod_{i=1}^{n-1}(u_i-x)d_n);r_a) ca=comck((Δ2−(u2−x)Δj−∏i=11(ui−x)d2),⋯,(Δn−(un−x)Δn−1−∏i=1n−1(ui−x)dn);ra) Prover将 c Δ , c a c_{\Delta},c_a cΔ,ca发送给Verifier。
Verifier：Challenge e e e。
Prover：for j = 1 , ⋯ , n j=1,\cdots,n j=1,⋯,n，构建 F j = e ∏ i = 1 j ( μ i − x ) + Δ j F_j=e\prod_{i=1}^{j}(\mu_i-x)+\Delta_j Fj=e∏i=1j(μi−x)+Δj，其中 F 1 = f 1 − e x ， F n = e ∏ i = 1 n ( m i − x ) F_1=f_1-ex，F_n=e\prod_{i=1}^{n}(m_i-x) F1=f1−ex，Fn=e∏i=1n(mi−x)，同时 F j ( f j + 1 − e x ) = ( e ∏ i = 1 j ( μ i − x ) + Δ j ) ( e u j + 1 + d j + 1 − e x ) = ( e ∏ i = 1 j ( μ i − x ) + Δ j ) ( e ( u j + 1 − x ) + d j + 1 ) = e 2 ∏ i = 1 j + 1 ( μ i − x ) + e Δ j + 1 − f Δ j = e F j + 1 + f Δ j F_j(f_{j+1}-ex)=(e\prod_{i=1}^{j}(\mu_i-x)+\Delta_j)(eu_{j+1}+d_{j+1}-ex)=(e\prod_{i=1}^{j}(\mu_i-x)+\Delta_j)(e(u_{j+1}-x)+d_{j+1})=e^2\prod_{i=1}^{j+1}(\mu_i-x)+e\Delta_{j+1}-f_{\Delta_j}=eF_{j+1}+f_{\Delta_j} Fj(fj+1−ex)=(e∏i=1j(μi−x)+Δj)(euj+1+dj+1−ex)=(e∏i=1j(μi−x)+Δj)(e(uj+1−x)+dj+1)=e2∏i=1j+1(μi−x)+eΔj+1−fΔj=eFj+1+fΔj，其中 f Δ j = − e ∏ i = 1 j ( u i − x ) d j + 1 − e ( u j + 1 − x ) Δ j + e Δ j + 1 − Δ j d j + 1 f_{\Delta_j}=-e\prod_{i=1}^{j}(u_i-x)d_{j+1}-e(u_{j+1}-x)\Delta_j+e\Delta_{j+1}-\Delta_jd_{j+1} fΔj=−e∏i=1j(ui−x)dj+1−e(uj+1−x)Δj+eΔj+1−Δjdj+1为 e e e的线性函数（一阶多项式）。 Prover将 f Δ 1 , ⋯ , f Δ n − 1 , z Δ = e r a + r Δ f_{\Delta_1},\cdots,f_{\Delta_{n-1}},z_{\Delta}=er_a+r_{\Delta} fΔ1,⋯,fΔn−1,zΔ=era+rΔ发送给Verifier。 ⇒ e F j + 1 = F j ( f j + 1 − e x ) + f Δ j \Rightarrow eF_{j+1}=F_j(f_{j+1}-ex)+f_{\Delta_j} ⇒eFj+1=Fj(fj+1−ex)+fΔj，将该递归公式展开有： e n − 1 F n = ∏ i = 1 n ( f i − e x ) − p n − 1 ( e ) e^{n-1}F_n=\prod_{i=1}^{n}(f_i-ex)-p_{n-1}(e) en−1Fn=∏i=1n(fi−ex)−pn−1(e)，其中 p n − 1 p_{n-1} pn−1为a degree n − 1 n-1 n−1 polynomial in e e e。
Verifier：验证 e n − 1 F n = e n ∏ i = 1 n ( m i − x ) = ∏ i = 1 n ( f i − e x ) − p n − 1 ( e ) e^{n-1}F_n=e^n\prod_{i=1}^{n}(m_i-x)=\prod_{i=1}^{n}(f_i-ex)-p_{n-1}(e) en−1Fn=en∏i=1n(mi−x)=∏i=1n(fi−ex)−pn−1(e)成立，从而即可证明 ∏ i = 1 n ( m i − x ) = ∏ i = 1 n ( μ i − x ) \prod_{i=1}^{n}(m_i-x)= \prod_{i=1}^{n}(\mu_i-x) ∏i=1n(mi−x)=∏i=1n(μi−x)成立。

总的shuffle of known contents 明文shuffle证明算法实现为：在这里插入图片描述

Special Honest Verifier Zero-Knowledge：即Simulator可在不知道Witness：permutation π \pi π 和 randomizer r r r的情况下，在提前知道challenge x x x和 e e e的情况下，可仿真使argument被verifier验证通过。下图的hybrid argument和simulate argument差别仅在 c a c_a ca的内容不同，因commitment具有hiding属性，所以hybrid argument和simulate argument具有indistinguishability。
Witness-Extended Emulation：

3. SHVZK Argument for Shuffle of Homomorphic Encryptions 基于密文（具有同态属性加密的密文）的shuffle证明算法

与第二节基于明文的shuffle情况不同，用于shuffle的为密文 e 1 , ⋯ , e n e_1,\cdots,e_n e1,⋯,en，而不再是明文了。 Common input：commit key c k ck ck、encrypted messages e 1 , ⋯ , e n e_1,\cdots,e_n e1,⋯,en和shuffle后的密文 E 1 = e π ( 1 ) ε p k ( 1 ; R 1 ) , ⋯ , E 1 = e π ( n ) ε p k ( 1 ; R n ) E_1=e_{\pi(1)}\varepsilon_{pk}(1;R_1),\cdots,E_1=e_{\pi(n)}\varepsilon_{pk}(1;R_n) E1=eπ(1)εpk(1;R1),⋯,E1=eπ(n)εpk(1;Rn)。 Witness：permutation π \pi π 和 randomizers R 1 , ⋯ , R n R_1,\cdots,R_n R1,⋯,Rn。证明：存在permutation π \pi π 使得the plaintexts of E 1 , ⋯ , E n E_1,\cdots,E_n E1,⋯,En和the plaintexts of e π ( 1 ) , ⋯ , e π ( n ) e_{\pi(1)},\cdots,e_{\pi(n)} eπ(1),⋯,eπ(n)是相同的。

直观的思路是：若Prover可将permutation π \pi π 发送给Verifier，则Verifier可选择任意的随机值 t 1 , ⋯ , t n t_1,\cdots,t_n t1,⋯,tn发送给Prover；Prover发送 ∏ i = 1 n e i t i \prod_{i=1}^{n}e_i^{t_i} ∏i=1neiti；Verifer只需验证 ∏ i = 1 n e i t i = ∏ i = 1 n E i t π ( i ) \prod_{i=1}^{n}e_i^{t_i}=\prod_{i=1}^{n}E_i^{t_{\pi(i)}} ∏i=1neiti=∏i=1nEitπ(i)即可。

但是，若想保持permutation π \pi π 不被泄露给Verifier，相应的实现思路为： 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.

Prover：选择随机值 − d 1 , ⋯ , − d n -d_1,\cdots,-d_n −d1,⋯,−dn，用于保护permutation π \pi π不被reveal。 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) Prover给Verfier发送 c d c_d cd。
Verifier：challenges t 1 , ⋯ , t n t_1,\cdots,t_n t1,⋯,tn。
Prover：对收到的 t 1 , ⋯ , t n t_1,\cdots,t_n t1,⋯,tn按相同的permutation π \pi π进行permute，计算 f i = t π ( i ) + d i f_i=t_{\pi(i)}+d_i fi=tπ(i)+di。 Prover给Verifier发送 f 1 , ⋯ , f n f_1,\cdots,f_n f1,⋯,fn。

2）接下来要证明 f i f_i fi have been formed correctly, using the same permutation π \pi π that used to form c c c。 Witness: π \pi π Common Input: c = c o m c k ( π ( 1 ) , ⋯ , π ( n ) ; r ) c=com_{ck}(\pi(1),\cdots,\pi(n);r) c=comck(π(1),⋯,π(n);r)， ( f 1 , ⋯ , f n ) (f_1,\cdots,f_n) (f1,⋯,fn)【即 ( t π ( 1 ) , ⋯ , t π ( n ) ) (t_{\pi(1)},\cdots,t_{\pi(n)}) (tπ(1),⋯,tπ(n))】以及 ( t 1 , ⋯ , t n ) (t_1,\cdots,t_n) (t1,⋯,tn) 证明： ( f 1 , ⋯ , f n ) (f_1,\cdots,f_n) (f1,⋯,fn)中的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\cdot1+t_1,\cdots,\lambda\cdot n+t_n) (m1,⋯,mn)=(λ⋅1+t1,⋯,λ⋅n+tn)
Prover：利用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))，引入随机值 ρ \rho ρ，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));ρ)。 Prover发送给Verifier c λ c_{\lambda} cλ。
Verifier：（1）利用commitment的加法同态性，验证 c λ = c λ c d c o m c k ( f 1 , ⋯ , f n ; 0 ) c_{\lambda}=c^{\lambda}c_dcom_{ck}(f_1,\cdots,f_n;0) cλ=cλcdcomck(f1,⋯,fn;0)成立；（2）转为证明已知 c λ = c o m c k ( ( m π ( 1 ) , ⋯ , m π ( n ) ) ; ρ ) 和 ( m 1 , ⋯ , m n ) c_{\lambda}=com_{ck}((m_{\pi(1)},\cdots,m_{\pi(n)});\rho)和(m_1,\cdots,m_n) cλ=comck((mπ(1),⋯,mπ(n));ρ)和(m1,⋯,mn)，证明Prover知道相应的permutation π \pi π和randomizer ρ \rho ρ，显然地，可以借助第二节的“shuffle of known contents 明文shuffle证明”来实现。

3）上述步骤1）和2）实现了permutation π \pi π的不暴露证明。最后需证明permutation π \pi π 使得the plaintexts of E 1 , ⋯ , E n E_1,\cdots,E_n E1,⋯,En和the plaintexts of e π ( 1 ) , ⋯ , e π ( n ) e_{\pi(1)},\cdots,e_{\pi(n)} eπ(1),⋯,eπ(n)是相同的，则应满足 ∏ i = 1 n e i t i ∏ i = 1 n E i d i = ∏ i = 1 n E i f i \prod_{i=1}^{n}e_i^{t_i}\prod_{i=1}^{n}E_i^{d_i}=\prod_{i=1}^{n}E_i^{f_i} ∏i=1neiti∏i=1nEidi=∏i=1nEifi。 Prover：在收到challenge t 1 , ⋯ , t n t_1,\cdots,t_n t1,⋯,tn之前，在发送 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)的同时，也发送 E d = ∏ i = 1 n E i − d i ε p k ( 1 ; R d ) E_d=\prod_{i=1}^{n} E_i^{-d_i}\varepsilon_{pk}(1;R_d) Ed=∏i=1nEi−diεpk(1;Rd) Verifier：challenges t 1 , ⋯ , t n t_1,\cdots,t_n t1,⋯,tn。 Prover：发送 Z = ∑ i = 1 n t π ( i ) R i + R d Z=\sum_{i=1}^{n}t_{\pi(i)}R_i+R_d Z=∑i=1ntπ(i)Ri+Rd。 Verifier：验证 ∏ i = 1 n e i − t i ∏ i = 1 n E i f i E d = ε p k ( 1 ; Z ) \prod_{i=1}^{n}e_i^{-t_i}\prod_{i=1}^{n}E_i^{f_i}E_d=\varepsilon_{pk}(1;Z) ∏i=1nei−ti∏i=1nEifiEd=εpk(1;Z)成立。

至此，整个算法细节如下：在这里插入图片描述

4. 基于a combined shuffle-and-decrypt operation正确性的证明算法

在这里插入图片描述针对的场景为： mix-net中，选民会将其投票信息 m m m进行加密，加密后的投票信息会经多个mix-servers进行shuflle并证明信息未被篡改。最终统计选举结果时，需要对多个mix-servers shuffle后密文信息进行解密，查看明文的投票信息。

直观的做法是mix-servers先做shuffle和相应的证明，验证shuffle没有被篡改后，再依次调用各mix-servers进行threshold decryption，最终解密出明文投票信息。整个过程中，每个mix-server均需被激活两次。

若在shuffle的同时也做threshold decryption，则可将每个mix-server的激活次数降为1次，同时亦能节约计算资源。

以EIGamal encryption为例，假设有 N N N个mix-server服务器，每个服务器 j j j的私钥为 x j x_j xj，对应的公钥为 y j = g x j y_j=g^{x_j} yj=gxj，整个mix-net的public key 为 ( g , y 1 , ⋯ , y N ) (g,y_1,\cdots,y_N) (g,y1,⋯,yN)。假设共有 n n n个选民投票信息 m 1 , ⋯ , m n m_1,\cdots, m_n m1,⋯,mn，对选民的投票信息 m i m_i mi加密为： ( u i , v i ) = ( g r , ( ∏ j = 1 N y j ) r m i ) (u_i,v_i)=(g^r,(\prod_{j=1}^{N}y_j)^rm_i) (ui,vi)=(gr,(∏j=1Nyj)rmi)

第一个mix-server：输入为 ( u 1 , v 1 ) , ⋯ , ( u n , v n ) (u_1,v_1),\cdots,(u_n,v_n) (u1,v1),⋯,(un,vn)，利用permutation π \pi π 和randmizers R 1 , ⋯ , R n R_1,\cdots,R_n R1,⋯,Rn进行shuffle并用其私钥 x 1 x_1 x1进行decrypt，结果为： ( U i , V i ) = ( g R i u π ( i ) , Y R i v π ( i ) u π ( i ) − x 1 ) (U_i,V_i)=(g^{R_i}u_{\pi(i)},Y^{R_i}v_{\pi(i)}u_{\pi(i)}^{-x_1}) (Ui,Vi)=(gRiuπ(i),YRivπ(i)uπ(i)−x1)【其中 Y = ∏ j = 2 N y j Y=\prod_{j=2}^{N}y_j Y=∏j=2Nyj】，同时为shuffle和decrypt操作提供证明。给第二个服务器传送密文 ( u i , v i ) = ( U i , V i ) , f o r i = 1 , ⋯ , n (u_i,v_i)= (U_i,V_i), for\ i=1,\cdots,n (ui,vi)=(Ui,Vi),for i=1,⋯,n。
第二个mix-server：输入为 ( u 1 , v 1 ) , ⋯ , ( u n , v n ) (u_1,v_1),\cdots,(u_n,v_n) (u1,v1),⋯,(un,vn)，利用新的permutation π \pi π 和新的randmizers R 1 , ⋯ , R n R_1,\cdots,R_n R1,⋯,Rn进行shuffle并用其私钥 x 2 x_2 x2进行decrypt，结果为： ( U i , V i ) = ( g R i u π ( i ) , Y R i v π ( i ) u π ( i ) − x 2 ) (U_i,V_i)=(g^{R_i}u_{\pi(i)},Y^{R_i}v_{\pi(i)}u_{\pi(i)}^{-x_2}) (Ui,Vi)=(gRiuπ(i),YRivπ(i)uπ(i)−x2)【其中 Y = ∏ j = 3 N y j Y=\prod_{j=3}^{N}y_j Y=∏j=3Nyj】，同时为shuffle和decrypt操作提供证明。给第三个服务器传送密文 ( u i , v i ) = ( U i , V i ) , f o r i = 1 , ⋯ , n (u_i,v_i)= (U_i,V_i), for\ i=1,\cdots,n (ui,vi)=(Ui,Vi),for i=1,⋯,n。
⋮ \vdots ⋮
最后一个mix-server：shuffle并用私钥 x N x_N xN解密后即得相应的明文投票信息 m m m，并提供相应证明。为最终选举结果统计提供明文投票信息 m m m。

通用地，假设有 n n n个选民投票信息 m 1 , ⋯ , m n m_1,\cdots,m_n m1,⋯,mn，则mix-server s s s收到的input ciphertexts of the form ( u 1 , v 1 ) , ⋯ , ( u n , v n ) (u_1,v_1),\cdots,(u_n,v_n) (u1,v1),⋯,(un,vn) under the key ( g , ∏ j = s N y j ) (g,\prod_{j=s}^{N}y_j) (g,∏j=sNyj)，通过随机选择permutation π \pi π和randomizers R 1 , ⋯ , R n R_1,\cdots,R_n R1,⋯,Rn，对应的输出为 ( U 1 , V 1 ) , ⋯ , ( U n , V n ) (U_1,V_1),\cdots,(U_n,V_n) (U1,V1),⋯,(Un,Vn) under the key ( g , Y = ∏ j = s + 1 N y j ) (g, Y=\prod_{j=s+1}^{N}y_j) (g,Y=∏j=s+1Nyj)，输入与输出有如下对应关系： U i = g R i u π ( i ) , V i = Y R i v π ( i ) u π ( i ) − x s U_i= g^{R_i}u_{\pi(i)}, V_i= Y^{R_i}v_{\pi(i)}u_{\pi(i)}^{-x_s} Ui=gRiuπ(i),Vi=YRivπ(i)uπ(i)−xs 然后需要为以上shuffle-and-decrypt操作正确性提供零知识证明。在第三节SHVZK Argument for Shuffle of Homomorphic Encryptions 基于密文（具有同态属性加密的密文）的shuffle证明算法的基础上，增加了argue correctness of the partial decryption的算法——如prove knowledge of the secret key x s x_s xs and argue that it has been used to make partial decryptions。总体思路为： 1）prove knowledge of the secret key x s x_s xs。借助sigma-protocol思路： Common input: public key y s = g x s y_s=g^{x_s} ys=gxs。 Prover: 选择随机值 d x d_x dx，发送 D = g d x D=g^{d_x} D=gdx。 Verifier：发送challenge e e e。 Prover：发送 f = e x s + d x f=ex_s+d_x f=exs+dx。 Verifier：验证 g f = y s e D g^f=y_s^eD gf=yseD成立即可。 2）利用第三节算法证明 ( U 1 , ⋯ , U n ) = ( g R 1 u π ( 1 ) , ⋯ , g R 1 u π ( n ) ) (U_1,\cdots,U_n)=(g^{R_1}u_{\pi(1)},\cdots, g^{R_1}u_{\pi(n)}) (U1,⋯,Un)=(gR1uπ(1),⋯,gR1uπ(n))： ∏ i = 1 n U i f i = ∏ i = 1 n ( g R i u π ( i ) ) t π ( i ) + d i = g ∑ i = 1 n ( t π ( i ) R i ) + R d ∗ ( ∏ i = 1 n u i t i ) ∗ ( ∏ i = 1 n U i d i g − R d ) \prod_{i=1}^{n}U_i^{f_i}=\prod_{i=1}^{n}(g^{R_i}u_{\pi(i)})^{t_{\pi(i)}+d_i}=g^{\sum_{i=1}^{n}(t_{\pi(i)}R_i)+R_d}*(\prod_{i=1}^{n}u_i^{t_i})*(\prod_{i=1}^{n}U_i^{d_i}g^{-R_d}) ∏i=1nUifi=∏i=1n(gRiuπ(i))tπ(i)+di=g∑i=1n(tπ(i)Ri)+Rd∗(∏i=1nuiti)∗(∏i=1nUidig−Rd) 在这里插入图片描述 3）利用第三节算法证明 ( V 1 , ⋯ , V n ) = ( Y R 1 v π ( 1 ) u π ( 1 ) − x s , ⋯ , Y R n v π ( n ) u π ( n ) − x s ) (V_1,\cdots,V_n)=( Y^{R_1}v_{\pi(1)}u_{\pi(1)}^{-x_s},\cdots, Y^{R_n}v_{\pi(n)}u_{\pi(n)}^{-x_s}) (V1,⋯,Vn)=(YR1vπ(1)uπ(1)−xs,⋯,YRnvπ(n)uπ(n)−xs)以及secret key x s x_s xs has been used to make partial decryptions。【引入 r v r_v rv用于hiding V d V_d Vd，引入 d v d_v dv用于hiding U U U】 ∏ i = 1 n V i f i = ∏ i = 1 n V i t π ( i ) + d i = ( ∏ i = 1 n ( Y i R v π ( i ) u π ( i ) − x s ) t π ( i ) ) ∗ ( ∏ i = 1 n V i d i ) = ( Y ∑ i = 1 n t π ( i ) R i + R d ∗ ∏ i = 1 n v i t i ∗ ( ∏ i = 1 n u i − t i ) x s ) ∗ ( ∏ i = 1 n V i d i ∗ Y − R d g − r v ) ∗ g r v \prod_{i=1}^{n}V_i^{f_i}=\prod_{i=1}^{n}V_i^{t_{\pi(i)}+d_i}=(\prod_{i=1}^{n}(Y^R_iv_{\pi(i)}u_{\pi(i)}^{-x_s})^{t_{\pi(i)}})*(\prod_{i=1}^{n}V_i^{d_i})=(Y^{\sum_{i=1}^{n}t_{\pi(i)}R_i+R_d}*\prod_{i=1}^{n}v_i^{t_i}*(\prod_{i=1}^{n}u_i^{-t_i})^{x_s})*(\prod_{i=1}^{n}V_i^{d_i}*Y^{-R_d}g^{-r_v})*g^{r_v} ∏i=1nVifi=∏i=1nVitπ(i)+di=(∏i=1n(YiRvπ(i)uπ(i)−xs)tπ(i))∗(∏i=1nVidi)=(Y∑i=1ntπ(i)Ri+Rd∗∏i=1nviti∗(∏i=1nui−ti)xs)∗(∏i=1nVidi∗Y−Rdg−rv)∗grv 为了同时验证secret key x s x_s xs has been used to make partial decryptions，上述等式左右两侧进行 e e e的幂乘，同时均乘以 g d v ∗ ( ∏ i = 1 n u i − t i ) x d g^{d_v}*(\prod_{i=1}^{n}u_i^{-t_i})^d_x gdv∗(∏i=1nui−ti)xd。最终有：在这里插入图片描述 4）为了证明prover确实知道在上一步中引入的 r v 和 d v r_v和d_v rv和dv【引入 r v r_v rv用于hiding V d V_d Vd，引入 d v d_v dv用于hiding U U U】，仍然接用sigma-protocol有： Prover： C 1 = c o m c k ( r v ; r 1 ) , C 2 = c o m c k ( d v ; r 2 ) C_1=com_{ck}(r_v;r_1),C_2=com_{ck}(d_v;r_2) C1=comck(rv;r1),C2=comck(dv;r2)，发送 C 1 和 C 2 C_1和C_2 C1和C2。 Verifier：Challenge e e e。 Prover：计算 f v = e r v + d v , z v = e r 1 + r 2 f_v=er_v+d_v,z_v=er_1+r_2 fv=erv+dv,zv=er1+r2，发送 f v 和 z v f_v和z_v fv和zv。 Verifier：验证 C 1 e C 2 = c o m c k ( f v ; z v ) C_1^eC_2=com_{ck}(f_v;z_v) C1eC2=comck(fv;zv)成立即可。