群签名、环签名、盲签名

群签名

定义

群签名方案是算法组 Π G S = ( G e n , S i g n , V e r , O p e n ) Pi_{GS}=(Gen, Sign, Ver, Open) ΠGS​=(Gen,Sign,Ver,Open)，

1. G e n ( 1 λ , n ) Gen(1^lambda,n) Gen(1λ,n)：密钥生成算法，$n$ 为群成员数，输出
   • $gvk$：群公钥，用于验签
   • $gmsk$：主私钥，由管理员持有，用于追踪成员身份
   • $gsk=(gsk[1],\cdots ,gsk[n])$：成员私钥，用于签名
2. $Sign(gsk[i],m)$：签名算法，任意成员可以独立签署消息 $m$，输出签名 $\sigma$
3. $Ver(gvk,m,\sigma )$：验签算法，根据验签通过与否，输出 $0/1$
4. $Open(gmsk,m,\sigma )$：公开算法，如果签名正确，则输出签名者身份 $i$，否则输出 $\perp$

我们说 $\sigma$ 是 $m$ 的正确签名，如果存在 $i\in [1,n]$ 以及随机带 $r$，使得 $\sigma =Sign(gsk[i],m;r)$ 成立。

安全性

群签名的安全性只需两条：完全匿名性、完全可追踪性。其他奇奇怪怪的安全性要求都可以由这两条推出。

• 匿名性实验：

定义敌手的优势为：
A d v Π , A a n o n ( λ , n ) = 2 ∣ P r [ E x p t Π , A a n o n ( 1 λ , n , U 1 ) = 1 ] − 1 2 ∣ = ∣ P r [ E x p t Π , A a n o n ( 1 λ , n , 1 ) = 1 ] − P r [ E x p t Π , A a n o n ( 1 λ , n , 0 ) = 0 ] ∣ begin{aligned} Adv_{Pi,A}^{anon}(lambda,n) &= 2left| Prleft[Expt_{Pi,A}^{anon}(1^lambda,n,U_1)=1right] - frac{1}{2} right|\ &= left| Prleft[Expt_{Pi,A}^{anon}(1^lambda,n,1)=1right] - Prleft[Expt_{Pi,A}^{anon}(1^lambda,n,0)=0right] right| end{aligned} AdvΠ,Aanon​(λ,n)​=2∣∣∣∣​Pr[ExptΠ,Aanon​(1λ,n,U1​)=1]−21​∣∣∣∣​=∣∣​Pr[ExptΠ,Aanon​(1λ,n,1)=1]−Pr[ExptΠ,Aanon​(1λ,n,0)=0]∣∣​​

我们说 Π G S Pi_{GS} ΠGS​ 是完全匿名的，如果对于任意 PPT 敌手 $A$，优势 A d v Π , A a n o n ( λ , n ) Adv_{Pi,A}^{anon}(lambda,n) AdvΠ,Aanon​(λ,n) 是可忽略的。

• 可追踪性实验：

定义敌手的优势为：
A d v Π , A t r a c e ( λ , n ) = P r [ E x p t Π , A t r a c e ( 1 λ , n ) = 1 ] Adv_{Pi,A}^{trace}(lambda,n) = Prleft[Expt_{Pi,A}^{trace}(1^lambda,n)=1right] AdvΠ,Atrace​(λ,n)=Pr[ExptΠ,Atrace​(1λ,n)=1]

我们说 Π G S Pi_{GS} ΠGS​ 是完全可追踪的，如果对于任意 PPT 敌手 $A$，优势 A d v Π , A t r a c e ( λ , n ) Adv_{Pi,A}^{trace}(lambda,n) AdvΠ,Atrace​(λ,n) 是可忽略的。

构造

密码学部件：

• 一般签名算法 Π s = ( G e n s , S i g n , V e r ) Pi_s = (Gen_s, Sign, Ver) Πs​=(Gens​,Sign,Ver)
• 公钥加密方案 Π e = ( G e n e , E n c , D e c ) Pi_e = (Gen_e, Enc, Dec) Πe​=(Gene​,Enc,Dec)
• 非交互零知识证明 $(P,V)$

1. 令 P 0 P_0 P0​ 是组管理员。为了让组内的每个成员都可以签名并验证，可以简单地执行 $n$ 次 G e n s Gen_s Gens​，为各个成员生成私钥公钥，将 { v k i } i ∈ I {vk_i}_{i in I} {vki​}i∈I​ 作为群公钥。但是这会泄露成员身份。
2. 我们不再公开公钥，而是在签名时附加上一个证明 $\pi$，使得验签者相信确实存在一个群成员 $i$ 签署了消息。但这有个问题，就是没有证明 v k i vk_i vki​ 是属于这个组的。
3. 让 P 0 P_0 P0​ 再为每个成员的公钥添加上证书 c e r t i cert_i certi​，同时要证明 v k i vk_i vki​ 确实是组成员的公钥。但是这必须公布 c e r t i cert_i certi​，又把成员身份泄露了。
4. 因此我们把证书加密后再发布，签名者对于 $m$ 输出 $(C,\pi )$，验签者验证 $\pi$ 确实是对 $m,C$ 之间关系的证明。

环签名

定义

环签名方案是算法组 Π R S = ( G e n , S i g n , V e r ) Pi_{RS}=(Gen, Sign, Ver) ΠRS​=(Gen,Sign,Ver)，

1. G e n ( 1 λ ) Gen(1^lambda) Gen(1λ)：密钥生成算法，输出 $(sk,vk)$
2. $Sign(sk,R,m)$：签名算法，验签密钥集合 R = ( v k i , ⋯   , v k n ) R=(vk_i,cdots,vk_n) R=(vki​,⋯,vkn​)（环），任何人可以独立签署消息 $m$，输出签名 $\sigma$
3. $Ver(R,m,\sigma )$：验签算法，根据验签通过与否，输出 $0/1$

若验签通过，那么说明签名是由 $R$ 中的某个 v k i vk_i vki​ 对应的 s k i sk_i ski​ 所签署的。与群签名相比，环签名是去中心化的，并且参与者的加入退出很容易。缺点是没法追踪恶意的签名者。

安全性

• 无内部攻击的不可伪造性实验

• 内部攻击的不可伪造性实验

定义敌手的优势为：
A d v Π , F E U F − C M A ( λ ) = P r [ E x p t Π , F e u f − c o r r u p t − c m a ( 1 λ ) = 1 ] Adv_{Pi,F}^{EUF-CMA}(lambda) = Prleft[ Expt_{Pi,F}^{euf-corrupt-cma}(1^lambda)=1 right] AdvΠ,FEUF−CMA​(λ)=Pr[ExptΠ,Feuf−corrupt−cma​(1λ)=1]

我们说 Π R S Pi_{RS} ΠRS​ 是**（内部攻击下）不可伪造的**，如果对于任意 PPT 敌手 $F$，优势 A d v Π , F E U F − C M A ( λ ) Adv_{Pi,F}^{EUF-CMA}(lambda) AdvΠ,FEUF−CMA​(λ) 是可忽略的。

• 基本匿名性实验：

定义敌手的优势为：
A d v Π , A a n o n ( λ ) = 2 ∣ P r [ E x p t Π , A a n o n ( 1 λ , U 1 ) = 1 ] − 1 2 ∣ = ∣ P r [ E x p t Π , A a n o n ( 1 λ , 1 ) = 1 ] − P r [ E x p t Π , A a n o n ( 1 λ , 0 ) = 0 ] ∣ begin{aligned} Adv_{Pi,A}^{anon}(lambda) &= 2left| Prleft[Expt_{Pi,A}^{anon}(1^lambda,U_1)=1right] - frac{1}{2} right|\ &= left| Prleft[Expt_{Pi,A}^{anon}(1^lambda,1)=1right] - Prleft[Expt_{Pi,A}^{anon}(1^lambda,0)=0right] right| end{aligned} AdvΠ,Aanon​(λ)​=2∣∣∣∣​Pr[ExptΠ,Aanon​(1λ,U1​)=1]−21​∣∣∣∣​=∣∣​Pr[ExptΠ,Aanon​(1λ,1)=1]−Pr[ExptΠ,Aanon​(1λ,0)=0]∣∣​​

我们说 Π G S Pi_{GS} ΠGS​ 是基本匿名的，如果对于任意 PPT 敌手 $A$，优势 A d v Π , A a n o n ( λ ) Adv_{Pi,A}^{anon}(lambda) AdvΠ,Aanon​(λ) 是可忽略的。

• （有内部攻击的）匿名性实验：

定义敌手的优势为：
A d v Π , A a n o n − c o r r u p t ( λ ) = 2 ∣ P r [ E x p t Π , A a n o n − c o r r u p t ( 1 λ , U 1 ) = 1 ] − 1 2 ∣ = ∣ P r [ E x p t Π , A a n o n − c o r r u p t ( 1 λ , 1 ) = 1 ] − P r [ E x p t Π , A a n o n − c o r r u p t ( 1 λ , 0 ) = 0 ] ∣ begin{aligned} Adv_{Pi,A}^{anon-corrupt}(lambda) &= 2left| Prleft[Expt_{Pi,A}^{anon-corrupt}(1^lambda,U_1)=1right] - frac{1}{2} right|\ &= left| Prleft[Expt_{Pi,A}^{anon-corrupt}(1^lambda,1)=1right] - Prleft[Expt_{Pi,A}^{anon-corrupt}(1^lambda,0)=0right] right| end{aligned} AdvΠ,Aanon−corrupt​(λ)​=2∣∣∣∣​Pr[ExptΠ,Aanon−corrupt​(1λ,U1​)=1]−21​∣∣∣∣​=∣∣∣​Pr[ExptΠ,Aanon−corrupt​(1λ,1)=1]−Pr[ExptΠ,Aanon−corrupt​(1λ,0)=0]∣∣∣​​

我们说 Π G S Pi_{GS} ΠGS​ 是匿名的，如果对于任意 PPT 敌手 $A$，优势 A d v Π , A a n o n − c o r r u p t ( λ ) Adv_{Pi,A}^{anon-corrupt}(lambda) AdvΠ,Aanon−corrupt​(λ) 是可忽略的。

构造

方法一：类似群签名，使用 NIZKP 将一般签名方案转化为环签名方案。

方法二：真的构成一个环 [RST01]，使用 trapdoor OWP 群成员可以在环的某个位置上打开环，然后再关闭环。

设 { H s } {H_s} {Hs​} 是 CRHF， { F k , F k − 1 } {F_k,F_k^{-1}} {Fk​,Fk−1​} 是 trapdoor OWP，对应的公私钥为 $(pk,sk)$，$\Pi =(Gen,Enc,Dec)$ 是对称加密算法，签名算法如下：

1. 选取 R = ( p k 1 , ⋯   , p k n ) R = (pk_1,cdots,pk_n) R=(pk1​,⋯,pkn​)，包含自己的公钥 p k j pk_j pkj​
2. 计算 r = H s ( m ) r=H_s(m) r=Hs​(m)，生成 k ← G e n ( 1 λ ; r ) k leftarrow Gen(1^lambda;r) k←Gen(1λ;r)
3. 随机选取 x 1 , ⋯   , x j − 1 , x j + 1 , ⋯   , x n x_1,cdots,x_{j-1},x_{j+1},cdots,x_n x1​,⋯,xj−1​,xj+1​,⋯,xn​，计算 y i = F ( p k i , x i ) , j ≠ i y_i = F(pk_i, x_i), j neq i yi​=F(pki​,xi​),j​=i
4. 随机选取 t j ′ = v t_j'=v tj′​=v，计算 t j + 1 = E n c ( k , t j ′ ) t_{j+1}=Enc(k,t_j') tj+1​=Enc(k,tj′​)，然后依次计算 t i + 1 = E n c ( k , t i ⊕ y i ) , i = j + 1 , ⋯   , n , 1 , ⋯   , j − 1 t_{i+1} = Enc(k, t_i oplus y_i), i=j+1,cdots,n,1,cdots,j-1 ti+1​=Enc(k,ti​⊕yi​),i=j+1,⋯,n,1,⋯,j−1（令 $n+1\equiv 1$）得到 t j t_j tj​，接着求逆 x j = F − 1 ( s k j , t j ⊕ t j ′ ) x_j = F^{-1}(sk_j, t_j oplus t_j') xj​=F−1(skj​,tj​⊕tj′​)
5. 输出 ( R , t n , x 1 , ⋯   , x n ) (R, t_n, x_1, cdots, x_n) (R,tn​,x1​,⋯,xn​) 作为消息 $m$ 的签名。

盲签名

定义

盲签名方案是算法组 Π B S = ( G e n , < S , U > , V e r ) Pi_{BS}=(Gen, <S,U>, Ver) ΠBS​=(Gen,<S,U>,Ver)，其中 $<S,U>$ 是签名者和用户之间的交互协议，

1. G e n ( 1 λ ) Gen(1^lambda) Gen(1λ)：密钥生成算法，输出 $(sk,vk)$
2. $<S(sk),U(vk,m)>$：签名交互协议，签名者输出 $Out=OK/Fail$（签名是否成功），用户输出 $m$ 的签名值 $\sigma$
3. $Ver(vk,m,\sigma )$：验签算法，根据验签通过与否，输出 $0/1$

安全性

• 不可伪造性实验：因为挑战者 $Ch$ 看不到 $m$，因此不能像一般签名算法那样设置一个签名历史记录 Q s Q_s Qs​ 使得 m ∗ ∉ Q s m^* notin Q_s m∗​∈Qs​，而是需要敌手 $F$ 询问 $k$ 次签名后，应当输出至少 $k+1$ 个不同消息的合法签名。

定义敌手的优势为：
A d v Π , F E U F − C M A ( λ ) = P r [ E x p t Π , F e u f − c m a ( 1 λ ) = 1 ] Adv_{Pi,F}^{EUF-CMA}(lambda) = Prleft[ Expt_{Pi,F}^{euf-cma}(1^lambda)=1 right] AdvΠ,FEUF−CMA​(λ)=Pr[ExptΠ,Feuf−cma​(1λ)=1]

我们说 Π B S Pi_{BS} ΠBS​ 是**（内部攻击下）不可伪造的**，如果对于任意 PPT 敌手 $F$，优势 A d v Π , F E U F − C M A ( λ ) Adv_{Pi,F}^{EUF-CMA}(lambda) AdvΠ,FEUF−CMA​(λ) 是可忽略的。

• 盲签实验：

定义敌手的优势为：
A d v Π , A b l i n d ( λ ) = 2 ∣ P r [ E x p t Π , A b l i n d ( 1 λ , U 1 ) = 1 ] − 1 2 ∣ = ∣ P r [ E x p t Π , A b l i n d ( 1 λ , 1 ) = 1 ] − P r [ E x p t Π , A b l i n d ( 1 λ , 0 ) = 0 ] ∣ begin{aligned} Adv_{Pi,A}^{blind}(lambda) &= 2left| Prleft[Expt_{Pi,A}^{blind}(1^lambda,U_1)=1right] - frac{1}{2} right|\ &= left| Prleft[Expt_{Pi,A}^{blind}(1^lambda,1)=1right] - Prleft[Expt_{Pi,A}^{blind}(1^lambda,0)=0right] right| end{aligned} AdvΠ,Ablind​(λ)​=2∣∣∣∣​Pr[ExptΠ,Ablind​(1λ,U1​)=1]−21​∣∣∣∣​=∣∣​Pr[ExptΠ,Ablind​(1λ,1)=1]−Pr[ExptΠ,Ablind​(1λ,0)=0]∣∣​​

我们说 Π B S Pi_{BS} ΠBS​ 是盲的，如果对于任意 PPT 敌手 $A$，优势 A d v Π , A b l i n d ( λ ) Adv_{Pi,A}^{blind}(lambda) AdvΠ,Ablind​(λ) 是可忽略的。

构造

密码学部件：

• 一般签名算法 Π s = ( G e n s , S i g n , V e r ) Pi_s = (Gen_s, Sign, Ver) Πs​=(Gens​,Sign,Ver)
• 公钥加密方案 Π e = ( G e n e , E n c , D e c ) Pi_e = (Gen_e, Enc, Dec) Πe​=(Gene​,Enc,Dec)
• 非交互零知识证明 $(P,V)$
• 非交互承诺方案 Π c = ( C o m , O p e n ) Pi_c = (Com,Open) Πc​=(Com,Open)

盲签名的密钥生成算法 G e n ( 1 λ ) Gen(1^lambda) Gen(1λ) 为：

1. 获得公共随机串 C R S Z K CRS_{ZK} CRSZK​ 和 C R S C o m CRS_{Com} CRSCom​
2. 执行 ( p k s , s k e ) ← G e n e ( 1 λ ) (pk_s,sk_e) leftarrow Gen_e(1^lambda) (pks​,ske​)←Gene​(1λ) 和 ( s k , v k ) = G e n s ( 1 λ ) (sk,vk) = Gen_s(1^lambda) (sk,vk)=Gens​(1λ)
3. 输出公钥 v k B S = ( C R S Z K , C R S C o m , p k e , v k ) vk_{BS} = (CRS_{ZK},CRS_{Com},pk_e,vk) vkBS​=(CRSZK​,CRSCom​,pke​,vk)，私钥 s k B S = ( C R S Z K , C R S C o m , s k e , s k ) sk_{BS} =(CRS_{ZK},CRS_{Com},sk_e,sk) skBS​=(CRSZK​,CRSCom​,ske​,sk)

盲签协议（Blind-signing protocol）$<S,U>$ 构造如下：

验签算法 V e r ( v k B S , m , ( C σ , π ) ) Ver(vk_{BS},m,(C_sigma,pi)) Ver(vkBS​,m,(Cσ​,π)) 为：

1. 设置 x = ( C σ , p k e , C R S C o m , v k , m ) x = (C_sigma,pk_e,CRS_{Com},vk,m) x=(Cσ​,pke​,CRSCom​,vk,m)
2. 输出 V ( C R S Z K , x , π ) V(CRS_{ZK},x,pi) V(CRSZK​,x,π)

其中，NIZKP $<P,V>$ 所证明的关系为：
R L ( x , w ) = 1    ⟺    x = ( C σ , p k e , C R S C o m , v k , m ) w = ( u , v , σ , C ) 1)   C = C o m ( C R S C o m , m ; u ) 2)   1 = V e r ( v k , C , σ ) 3)   C σ = E n c ( p k e , C ∥ σ ; v ) R_L(x,w)=1 iff begin{aligned} &x = (C_sigma,pk_e,CRS_{Com},vk,m)\ &w = (u,v,sigma,C)\ &textbf{1) }C = Com(CRS_{Com},m;u)\ &textbf{2) }1 = Ver(vk,C,sigma)\ &textbf{3) }C_sigma = Enc(pk_e,C|sigma;v)\ end{aligned} RL​(x,w)=1⟺​x=(Cσ​,pke​,CRSCom​,vk,m)w=(u,v,σ,C)1) C=Com(CRSCom​,m;u)2) 1=Ver(vk,C,σ)3) Cσ​=Enc(pke​,C∥σ;v)​