Multi-Signature Schemes Secure against Active Insider Attacks

Kazuo OHTA  Tatsuaki OKAMOTO  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E82-A   No.1   pp.21-31
Publication Date: 1999/01/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: 
Keyword: 
digital signature,  Fiat-Shamir scheme,  Schnorr scheme,  random oracle model,  zero-knowledge interactive proof,  provable security,  

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


Summary: 
This paper proposes the first provably secure multi-signature schemes under the random oracle model. The security of our schemes can be proven in the sense of concrete security in Ref. [13]. The proposed schemes are efficient if the random oracle is replaced by practical hash functions. The essential techniques in our proof of security are the optimal reduction from breaking the corresponding identification to breaking signatures (ID Reduction Technique), and the hierarchical heavy row lemmas used in the concrete reduction from solving the primitive problem to breaking the identification scheme.