Multisignatures Using Proofs of Secret Key Possession, as Secure as the Diffie-Hellman Problem

A multisignature scheme allows a group of

n

players to produce a short string which is equivalent to

n

separate signatures on the same message. Assuming the Random Oracle Model (ROM), the aggregate signature schemes of Boneh et al. [BGLS03] and Bellare and Neven [BN06] provide multisignatures secure in the standard public key setting, but their multisignature verification algorithms involve respectively

O

(

n

) bilinear maps and

O

(

n

) exponentiations. Ristenpart and Yilek [RY07] recently showed two multisignature schemes relying on groups with bilinear maps, with just

O

(1) bilinear maps in multisignature verification, which are secure if each public key is accompanied by so-called “proof of (secret key) possession” (POP). We show how to achieve secure multisignatures in the POP model using any group where CDH or DDH problems are hard. Both schemes have multisignature verification with

O

(1) exponentiations, and their POP messages take

O

(1) group elements and require

O

(1) exponentiations to verify. Moreover, the security of the proposed schemes is

tightly

related to the CDH and DDH problems, in ROM.