Date: 2001/6/8

Name: Kazuo OHTA
The University of Electro-Communications, Department of Information and Communication Engineering, Professor

Title:On the security of Multi-Signature Schemes

In multi-signature schemes, where multiple users sign on a single message, it has been recently recognized that a straightforward extension of the security definition of usual (or single) signature schemes is not sufficient. That is, the key generation/registration phase can be a target of an adversary in addition to the traditional adversarial model, in the multi-signature schemes. This paper defines two models of the security definition of multi-signature schemes: weak security model(straightforward extension of usual signature scheme's definition: no key generation phase attacks are considered), and strong security model (key generation phase attacks as well as the traditional attacks are considered). In this paper we introduce two types of reductions in the provably secure multi-signatures: one is an insensitive reduction, and the other a sensitive reduction. This paper gives two methods of constructing a secure multi-signature scheme in the strong security model from a scheme secure in the weak security model, and also gives some concrete and practical examples of these construction methods.