Presentation 1997/7/19
The Exact Security of Multi-Signature Schemes
Kazuo Ohta, Tatsuaki Okamoto,
PDF Download Page PDF download Page Link
Abstract(in Japanese) (See Japanese page)
Abstract(in English) Although several multi-signature schemes have been proposed, no scheme has been proven to be secure against adaptive chosen-message insider attacks. This paper proposes the first provably secure multi-signature schemes under the random oracle model. The security of our schemes can be reduced to the intractability of calculating a secret key from the public key in the sense of exact security by Bellare and Rogaway. The proposed schemes are efficient if the random oracle is replaced by practical hash functions. Even a special case of our results for a single-signature scheme (e.g. Schnorr scheme) gives a tighter security analysis than the previous results for the Schnorr scheme by Pointcheval and Stern. The essential technique in our proof of security is the exact reduction from signature schemes to the corresponding identification schemes.
Keyword(in Japanese) (See Japanese page)
Keyword(in English) digital signature / Fiat-Shamir scheme / Schnorr scheme / random oracle model / zero-knowledge interactive proof / provable security
Paper # ISEC97-27
Date of Issue

Conference Information
Committee ISEC
Conference Date 1997/7/19(1days)
Place (in Japanese) (See Japanese page)
Place (in English)
Topics (in Japanese) (See Japanese page)
Topics (in English)
Vice Chair

Paper Information
Registration To Information Security (ISEC)
Language ENG
Title (in Japanese) (See Japanese page)
Sub Title (in Japanese) (See Japanese page)
Title (in English) The Exact Security of Multi-Signature Schemes
Sub Title (in English)
Keyword(1) digital signature
Keyword(2) Fiat-Shamir scheme
Keyword(3) Schnorr scheme
Keyword(4) random oracle model
Keyword(5) zero-knowledge interactive proof
Keyword(6) provable security
1st Author's Name Kazuo Ohta
1st Author's Affiliation NTT Information and Communication Systems Laboratories()
2nd Author's Name Tatsuaki Okamoto
2nd Author's Affiliation NTT Information and Communication Systems Laboratories
Date 1997/7/19
Paper # ISEC97-27
Volume (vol) vol.97
Number (no) 182
Page pp.pp.-
#Pages 12
Date of Issue