群签名、环签名、盲签名

群签名

定义

群签名方案是算法组 Π 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 n n 为群成员数,输出
    • g v k gvk gvk:群公钥,用于验签
    • g m s k gmsk gmsk:主私钥,由管理员持有,用于追踪成员身份
    • g s k = ( g s k [ 1 ] , ⋯   , g s k [ n ] ) gsk=(gsk[1],cdots,gsk[n]) gsk=(gsk[1],,gsk[n]):成员私钥,用于签名
  2. S i g n ( g s k [ i ] , m ) Sign(gsk[i],m) Sign(gsk[i],m):签名算法,任意成员可以独立签署消息 m m m,输出签名 σ sigma σ
  3. V e r ( g v k , m , σ ) Ver(gvk,m,sigma) Ver(gvk,m,σ):验签算法,根据验签通过与否,输出 0 / 1 0/1 0/1
  4. O p e n ( g m s k , m , σ ) Open(gmsk,m,sigma) Open(gmsk,m,σ):公开算法,如果签名正确,则输出签名者身份 i i i,否则输出 ⊥ perp

我们说 σ sigma σ m m m 的正确签名,如果存在 i ∈ [ 1 , n ] i in [1,n] i[1,n] 以及随机带 r r r,使得 σ = S i g n ( g s k [ i ] , m ; r ) sigma=Sign(gsk[i],m;r) σ=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)=2Pr[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 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 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 ) (P,V) (P,V)

在这里插入图片描述

  1. P 0 P_0 P0 是组管理员。为了让组内的每个成员都可以签名并验证,可以简单地执行 n n n G e n s Gen_s Gens,为各个成员生成私钥公钥,将 { v k i } i ∈ I {vk_i}_{i in I} {vki}iI 作为群公钥。但是这会泄露成员身份。
  2. 我们不再公开公钥,而是在签名时附加上一个证明 π pi π,使得验签者相信确实存在一个群成员 i i 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 m m 输出 ( C , π ) (C,pi) (C,π),验签者验证 π pi π 确实是对 m , C m,C 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λ):密钥生成算法,输出 ( s k , v k ) (sk,vk) (sk,vk)
  2. S i g n ( s k , R , m ) Sign(sk,R,m) Sign(sk,R,m):签名算法,验签密钥集合 R = ( v k i , ⋯   , v k n ) R=(vk_i,cdots,vk_n) R=(vki,,vkn)(环),任何人可以独立签署消息 m m m,输出签名 σ sigma σ
  3. V e r ( R , m , σ ) Ver(R,m,sigma) Ver(R,m,σ):验签算法,根据验签通过与否,输出 0 / 1 0/1 0/1

若验签通过,那么说明签名是由 R R 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Π,FEUFCMA(λ)=Pr[ExptΠ,Feufcorruptcma(1λ)=1]

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

  • 基本匿名性实验

在这里插入图片描述

定义敌手的优势为:
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(λ)=2Pr[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 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Π,Aanoncorrupt(λ)=2Pr[ExptΠ,Aanoncorrupt(1λ,U1)=1]21=Pr[ExptΠ,Aanoncorrupt(1λ,1)=1]Pr[ExptΠ,Aanoncorrupt(1λ,0)=0]

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

构造

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

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

{ H s } {H_s} {Hs} 是 CRHF, { F k , F k − 1 } {F_k,F_k^{-1}} {Fk,Fk1} 是 trapdoor OWP,对应的公私钥为 ( p k , s k ) (pk,sk) (pk,sk) Π = ( G e n , E n c , D e c ) Pi=(Gen, Enc, Dec) Π=(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) kGen(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,,xj1,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,tiyi),i=j+1,,n,1,,j1(令 n + 1 ≡ 1 n+1 equiv 1 n+11)得到 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=F1(skj,tjtj)
  5. 输出 ( R , t n , x 1 , ⋯   , x n ) (R, t_n, x_1, cdots, x_n) (R,tn,x1,,xn) 作为消息 m m m 的签名。

盲签名

定义

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

  1. G e n ( 1 λ ) Gen(1^lambda) Gen(1λ):密钥生成算法,输出 ( s k , v k ) (sk,vk) (sk,vk)
  2. < S ( s k ) , U ( v k , m ) > <S(sk),U(vk,m)> <S(sk),U(vk,m)>:签名交互协议,签名者输出 O u t = O K / F a i l Out=OK/Fail Out=OK/Fail(签名是否成功),用户输出 m m m 的签名值 σ sigma σ
  3. V e r ( v k , m , σ ) Ver(vk,m,sigma) Ver(vk,m,σ):验签算法,根据验签通过与否,输出 0 / 1 0/1 0/1

安全性

  • 不可伪造性实验:因为挑战者 C h Ch Ch 看不到 m m m,因此不能像一般签名算法那样设置一个签名历史记录 Q s Q_s Qs 使得 m ∗ ∉ Q s m^* notin Q_s mQs,而是需要敌手 F F F 询问 k k k 次签名后,应当输出至少 k + 1 k+1 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Π,FEUFCMA(λ)=Pr[ExptΠ,Feufcma(1λ)=1]

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

  • 盲签实验

在这里插入图片描述

定义敌手的优势为:
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(λ)=2Pr[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 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 ) (P,V) (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 > <S,U> <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 > <P,V> <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)=1x=(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)