Meeting Tight Security for Multisignatures in the Plain Public Key Model

Naoto YANAI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E101-A   No.9   pp.1484-1493
Publication Date: 2018/09/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E101.A.1484
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
multisignatures,  plain public key model,  provable security,  tight reduction,  random oracle model,  CDH problem,  

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


Summary: 
Multisignatures are digital signatures for a group consisting of multiple signers where each signer signs common documents via interaction with its co-signers and the data size of the resultant signatures for the group is independent of the number of signers. In this work, we propose a multisignature scheme, whose security can be tightly reduced to the CDH problem in bilinear groups, in the strongest security model where nothing more is required than that each signer has a public key, i.e., the plain public key model. Loosely speaking, our main idea for a tight reduction is to utilize a three-round interaction in a full-domain hash construction. Namely, we surmise that a full-domain hash construction with three-round interaction will become tightly secure under the CDH problem. In addition, we show that the existing scheme by Zhou et al. (ISC 2011) can be improved to a construction with a tight security reduction as an application of our proof framework.