Structural Properties of Cryptographic Sequences - Computational Intelligence in Security for Information Systems - page 135

A Multisignature Scheme Based on the SDLP
and on the IFP

R. Duran D ıaz 1 ,L.Hernandez Encinas 2 ,andJ.Munoz Masque 2

1 Universidad de Alcala, 28871-Alcala de Henares, Spain
[e-mail]
2 Instituto de Fısica Aplicada, CSIC, C/ Serrano 144, 28006-Madrid, Spain
{ luis,jaime } @iec.csic.es

Abstract. Multisignature schemes are digital signature schemes that
permit one to determine a unique signature for a given message, de-
pending on the signatures of all the members of a specific group. In this
work, we present a new semi-short multisignature scheme based on the
Subgroup Discrete Logarithm Problem (SDLP) and on the Integer Fac-
torization Problem (IFP). The scheme can be carried out in an on- and
off-line basis, is ecient, and the bitlength of the multisignature does
not depend on the number of signers.

Keywords: Digital signature, Multisignature, Public key cryptography.

1 Introduction

There are currently different methods and algorithms to perform, in a safe way,
digital signatures. Most of these protocols are based on Public Key Cryptography
[1]. The main feature of this kind of cryptography is that each individual has two
keys, one public key and one private key. Additionally, to make more ecient the
procedures of digital signatures and their electronic transmission, hash functions
are used [2]. These functions are publicly known and allow signing a digest of
the original document instead of the whole document.
Multisignature schemes are protocols of digital signature whereby a group of
users, G = { U 1 ,...,U t }

, signs a document such that the signature is valid if and
only if all members of the group take part in the protocol and the signature ver-
ifies a specific condition of validity. These schemes have application in settings
such us, for example, corporate scenarios for signing contracts between compa-
nies, the government and public administrations, agreements between different
organization, etc. The easiest way to carry out a multisignature for a message
is to consider as such signature the list formed by all the partial signatures of
each one of the signers. However, this signature is not practical since its length
is proportional to the number of signers [3,4].
In general, most of the multisignature protocols are performed as follows:

1. The signer U 1 signs the original message by using the signer private key.