一个高效率的双指数多重签名方案

An Efficient Double Exponential Multi-Signature Scheme

本文提出了一个高效率的双指数多重签名DEMSP(Double Exponential Pairing-Based Multi-Signature)方案,在DEMSP方案中,每个签名者进行BLS(Boneh-Lynn-Shacham)签名,在聚合公钥的计算上,DEMSP方案比MSP(Pairing-Based Multi-Signature with Public-Key Aggregation)方案高效数倍,倍数与签名者人数呈正相关.MSP方案实现了签名聚合与密钥聚合,使得验证者验证一个消息是由n个签名者签名时,只需一个签名与一个公钥,并且MSP方案可以在普通公钥模型下抵抗流氓密钥攻击,然而MSP方案中,每个签名者在签名时都需要获得其他签名者的公钥,这增加了通信开销,在验证阶段,验证者计算聚合公钥时需要进行额外的指数计算.DEMSP方案通过引入可追责第三方实现高签名效率与高验证效率,并利用分叉引理将DEMSP方案规约到co-CDH问题.DEMSP方案应用于在线支付,使得交易合法,商家与用户的纠纷得以有效处理,并且DEMSP方案被扩展至多权威机构的多重签名方案.同时DEMSP方案应用于ASM(Accountable-Subgroup Multi-signature)方案及MSDL(Discrete-Logarithm based Multi-Signature)方案,使得计算聚合公钥的时间比原方案减少数倍.

We propose an efficient double exponential pairing-based multi-signature(DEMSP)scheme.In the DEMSP scheme,each signer only needs to perform the Boneh-Lynn-Shacham(BLS)signature.In the calculation of aggregate public keys,the DEMSP scheme is several times more efficient than the pairing-based multi-signature scheme with public-key aggregation(MSP).The efficiency is linear with the number of signers.The MSP scheme implements signature aggregation and key aggregation,so that the verifier only needs one signature and one public key when verifying that a message is signed by n signers.The MSP scheme can resist the rogue public-key attack under the plain public key model.However,in the MSP scheme,each signer needs to obtain public keys of other signers when signing,which increases the communication overhead.In the verification phase,the verifier needs to perform additional exponential calculations when calculating the aggregated public key.The DEMSP scheme improves the signature and verification efficiency of the MSP scheme by introducing the accountable third party,and we use forking lemma to reduce the DEMSP scheme to the co-CDH problem.The DEMSP scheme is applied to online payment to make transactions legal and disputes between merchants and users resolved.The DEMSP scheme has also been extended to multi-signature schemes with multiple authorities.At the same time,we apply the DEMSP scheme to the accountable-subgroup multi-signature(ASM)scheme and the discrete-logarithm based multi-signature(MSDL)scheme.The time of calculating the aggregate public key is reduced several times.The time of calculating the aggregate public key is reduced several times.