Efficient discrete logarithm based multi-signature scheme in the plain public key model

Publication Type

Journal Article

Publication Date

2-2010

Abstract

In this paper, we provide a new multi-signature scheme that is proven secure in the plain public key model. Our scheme is practical and efficient according to computational costs, signature size and security assumptions. At first, our scheme matches the single ordinary discrete logarithm based signature scheme in terms of signing time, verification time and signature size. Secondly, our scheme requires only two rounds of interactions and each signer needs nothing more than a certified public key to produce the signature, meaning that our scheme is compatible with existing PKIs. Thirdly, our scheme has been proven secure in the random oracle model under standard discrete logarithm (DL) assumption. It outperforms a newly proposed multi-signature scheme by Bagherzandi, Cheon and Jarecki (BCJ scheme) in terms of both computational costs and signature size.

Keywords

Cryptography, Digital signature, Multi-signature, Provable security, Plain public key model

Discipline

Information Security

Research Areas

Information Security and Trust

Publication

Designs, Codes and Cryptography

Volume

54

Issue

2

First Page

121

Last Page

133

ISSN

0925-1022

Identifier

10.1007/s10623-009-9313-z

Publisher

Springer Verlag

Additional URL

http://dx.doi.org/10.1007/s10623-009-9313-z

Link to Full Text

Share

COinS