A General Model of Structured Multisignatures with Message Flexibility

Dan YAMAMOTO  Wakaha OGATA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E90-A   No.1   pp.83-90
Publication Date: 2007/01/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e90-a.1.83
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Signatures
Keyword: 
multisignatures,  aggregate signatures,  bilinear maps,  random oracle model,  

Full Text: PDF(190.8KB)>>
Buy this Article




Summary: 
Multisignature schemes enable us to integrate multiple signatures into a single short signature. In 2001, Mitomi and Miyaji proposed a general model of multisignatures, in which signed messages are flexible and the signing order is verifiable and flexible. Several schemes that satisfy these properties have been proposed, but to the best of our knowledge, their verifiable orders are limited to only sequential structures unlike some order-verifiable (but not message-flexible) multisignatures. We define a signing structure as a labeled tree, which can represent any natural signing order including series-parallel graphs, and formalize a general model of multisignatures that makes good use of our structure. We present a security model for such signatures, give the construction based on the general aggregate signature developed by Boneh et al., and provide a security proof in the random oracle model.