文章目录
- 群签名
- 定义
- 安全性
- 构造
- 环签名
- 定义
- 安全性
- 构造
- 盲签名
- 定义
- 安全性
- 构造
群签名
定义
群签名方案是算法组 Π 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),
- 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]):成员私钥,用于签名
- S i g n ( g s k [ i ] , m ) Sign(gsk[i],m) Sign(gsk[i],m):签名算法,任意成员可以独立签署消息 m m m,输出签名 σ \sigma σ
- V e r ( g v k , m , σ ) Ver(gvk,m,\sigma) Ver(gvk,m,σ):验签算法,根据验签通过与否,输出 0 / 1 0/1 0/1
- 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) &= 2\left| Pr\left[Expt_{\Pi,A}^{anon}(1^\lambda,n,U_1)=1\right] – \frac{1}{2} \right|\\ &= \left| Pr\left[Expt_{\Pi,A}^{anon}(1^\lambda,n,1)=1\right] – Pr\left[Expt_{\Pi,A}^{anon}(1^\lambda,n,0)=0\right] \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 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) = Pr\left[Expt_{\Pi,A}^{trace}(1^\lambda,n)=1\right] 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)
- 令 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}i∈I 作为群公钥。但是这会泄露成员身份。
- 我们不再公开公钥,而是在签名时附加上一个证明 π \pi π,使得验签者相信确实存在一个群成员 i i i 签署了消息。但这有个问题,就是没有证明 v k i vk_i vki 是属于这个组的。
- 让 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,又把成员身份泄露了。
- 因此我们把证书加密后再发布,签名者对于 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),
- G e n ( 1 λ ) Gen(1^\lambda) Gen(1λ):密钥生成算法,输出 ( s k , v k ) (sk,vk) (sk,vk)
- 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 σ
- 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) = Pr\left[ 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 F 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) &= 2\left| Pr\left[Expt_{\Pi,A}^{anon}(1^\lambda,U_1)=1\right] – \frac{1}{2} \right|\\ &= \left| Pr\left[Expt_{\Pi,A}^{anon}(1^\lambda,1)=1\right] – Pr\left[Expt_{\Pi,A}^{anon}(1^\lambda,0)=0\right] \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 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) &= 2\left| Pr\left[Expt_{\Pi,A}^{anon-corrupt}(1^\lambda,U_1)=1\right] – \frac{1}{2} \right|\\ &= \left| Pr\left[Expt_{\Pi,A}^{anon-corrupt}(1^\lambda,1)=1\right] – Pr\left[Expt_{\Pi,A}^{anon-corrupt}(1^\lambda,0)=0\right] \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 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,对应的公私钥为 ( p k , s k ) (pk,sk) (pk,sk), Π = ( G e n , E n c , D e c ) \Pi=(Gen, Enc, Dec) Π=(Gen,Enc,Dec) 是对称加密算法,签名算法如下:
- 选取 R = ( p k 1 , ⋯ , p k n ) R = (pk_1,\cdots,pk_n) R=(pk1,⋯,pkn),包含自己的公钥 p k j pk_j pkj
- 计算 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)
- 随机选取 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
- 随机选取 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 ≡ 1 n+1 \equiv 1 n+1≡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′)
- 输出 ( 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 , , V e r ) \Pi_{BS}=(Gen, ΠBS=(Gen,<S,U>,Ver),其中 , Ver) <S,U> 是签名者和用户之间的交互协议,
- G e n ( 1 λ ) Gen(1^\lambda) Gen(1λ):密钥生成算法,输出 ( s k , v k ) (sk,vk) (sk,vk)
-
- 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^* \not\in Q_s m∗∈Qs,而是需要敌手 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) = Pr\left[ 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 F 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) &= 2\left| Pr\left[Expt_{\Pi,A}^{blind}(1^\lambda,U_1)=1\right] – \frac{1}{2} \right|\\ &= \left| Pr\left[Expt_{\Pi,A}^{blind}(1^\lambda,1)=1\right] – Pr\left[Expt_{\Pi,A}^{blind}(1^\lambda,0)=0\right] \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 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λ) 为:
- 获得公共随机串 C R S Z K CRS_{ZK} CRSZK 和 C R S C o m CRS_{Com} CRSCom
- 执行 ( 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λ)
- 输出公钥 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σ,π)) 为:
- 设置 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)
- 输出 V ( C R S Z K , x , π ) V(CRS_{ZK},x,\pi) V(CRSZK,x,π)
其中,NIZKP
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)