本文涉及的方案：

• MSP：一种Multi-Signature(基于双线性对)合成多个签名，使用合成公钥 a p k apk apk可验证。（用全部的 a p k i apk_i apki一组可以批量验证multi-Signatures）
• AMSP：MSP聚合版，多个multi-Signatures聚合成一个，并给出相应的验证方法
• ASM：部分子集的multi-signature，使用总合成公钥apk可验证，使用 m k i mk_i mki可追责
• MSDL：基于离散对数Multi-Signature方案

以上方案PoP版本（用PoP对抗 Rogue public-key attack）

• M u l t i s i g n a t u r e : ( P g , K g , S i g n , K A g , V f ) {\rm Multisignature:( Pg, Kg, Sign, KAg, Vf}) Multisi g nature:(Pg,Kg,Sign,KAg,Vf)：签名算法的输入包括公钥集合 P K \mathcal{PK} PK，每个签名方各自生成签名。 K A g {\rm KAg} KAg将公钥集合聚合成一个聚合公钥，可用于验证任何一个签名。
• Aggregate Multi-Signatures：将多个Multisignature聚合成一个签名，扩展两个算法：
  • S A g ( ( a p k , m , σ ) , . . . ) → Σ {\rm SAg}((apk,m,\sigma),...)\rightarrow\Sigma SAg((apk,m,σ),...)→Σ
  • A V f ( ( a p k , m ) , . . . , Σ ) → 0 / 1 {\rm AVf}((apk,m),...,\Sigma)\rightarrow0/1 AVf((apk,m),...,Σ)→0/1

构造Aggregate Multi-Signatures的目标并非简单的聚合，而是构造远小于独立Multi-Signatures集合的规模，理想状态下是常数规模。

这个签名支持简单的聚合： 验证聚合签名：所有 ( p k i , m i ) i = 1 n (pk_i,m_i)_{i=1}^n (pki​,mi​)i=1n​ 如果所有被签名的message都一样： m 1 = . . . = m n m_1=...=m_n m1​=...=mn​，验证关系(2)归约成简单的形式： 以及一个短的聚合公钥 a p k : = p k 1 . . . p k n ∈ G 2 apk:=pk_1...pk_n\in\mathbb{G}_2 apk:=pk1​...pkn​∈G2​

• K e y G e n ( ) : x ← Z p , X = g x {\rm KeyGen}():x\leftarrow\mathbb{Z}_p,X=g^x KeyGen():x←Zp​,X=gx
• S i g n ( ( s k , p k ) , L = { p k 1 , . . . , p k n } , m ) → σ {\rm Sign}( (sk, pk),L=\{pk_1,...,pk_n\},m)\rightarrow \sigma Sign((sk,pk),L={ pk1​,...,pkn​},m)→σ. L = { X 1 , . . . , X n } L=\{X_1,...,X_n\} L={ X1​,...,Xn​}，签名者密钥 ( x 1 , X 1 ) (x_1,X_1) (x1​,X1​)

1. 对 i ∈ { 1 , . . . , n } i\in\{1,...,n\} i∈{ 1,...,n}，计算 a i = H 0 ( L , X i ) a_i=H_0(L,X_i) ai​=H0​(L,Xi​)，聚合公钥 X ~ = ∏ i = 1 n X i a i \widetilde{X}=\prod_{i=1}^nX_i^{a_i} X =∏i=1n​Xiai​​
2. 随机 r i ← Z p r_i\leftarrow\mathbb{Z}_p ri​←Zp​，计算 R 1 = g r 1 R_1=g^{r_1} R1​=gr1​，将 R 1 R_1 R1​发送给其他参与方
3. 收到其他所有 R 2 , . . . , R n R_2,...,R_n R2​,...,Rn​后，计算： R = ∏ i = 1 n R i , c = H 1 ( X ~ , R , m ) , s 1 = r 1 + c ⋅ a 1 ⋅ x 1   m o d   p R=\prod_{i=1}^nR_i,c=H_1(\widetilde{X},R,m),s_1=r_1+c\cdot a_1\cdot x_1~mod~p R=∏i=1n​Ri​,c=H1​(X ,R,m),s1​=r1​+c⋅a1​⋅x1​ mod p，将 s 1 s_1 s1​发送给其他参与方
4. 收到所有其他 s 2 , . . . , s n s_2,...,s_n s2​,...,sn​后，计算： s = ∑ i = 1 n s i   m o d   p s=\sum_{i=1}^ns_i~mod~p s=∑i=1n​si​ mod p，签名 σ = ( R , s ) \sigma=(R,s) σ=(R,s)

• V e r ( L , m , σ ) → 0 / 1 {\rm Ver}(L, m, \sigma)\rightarrow0/1 Ver(L,m,σ)→0/1