
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Provably Secure Multisignatures in Formal Security Model and Their Optimality
Yuichi KOMANO Kazuo OHTA Atsushi SHIMBO Shinichi KAWAMURA
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E91A
No.1
pp.107118 Publication Date: 2008/01/01
Online ISSN: 17451337
DOI: 10.1093/ietfec/e91a.1.107
Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security) Category: Signatures Keyword: multisignatures, trapdoor oneway permutation (TOWP), clawfree permutation (CFP), provably secure, random oracle model,
Full Text: PDF(346.7KB)>>
Summary:
We first model the formal security model of multisignature scheme following that of group signature scheme. Second, we prove that the following three probabilistic multisignature schemes based on a trapdoor permutation have tight security; PFDH (probabilistic full domain hash) based multisignature scheme (PFDHMSS), PSS (probabilistic signature scheme) based multisignature scheme (PSSMSS), and short signature PSS based multisignature scheme (SPSSMSS). Third, we give an optimal proof (general result) for multisignature schemes, which derives the lower bound for the length of random salt. We also estimate the upper bound for the length in each scheme and derive the optimal length of a random salt. Two of the schemes are promising in terms of security tightness and optimal signature length. In appendix, we describe a multisignature scheme using the clawfree permutation and discuss its security.

