Informática 34 (2010) 104-490 477 Multisignature Scheme Based on Discrete Logarithms in the Plain Public Key Model Zuhua Shao Zhejiang University of Science and Technology, P. R. of China E-mail: zhshao_98@yahoo.com Keywords: discrete logarithm, random oracle model, group oriented cryptography, multisignature. Received: November 18, 2008 In this paper, we propose a new multisignature scheme based on discrete logarithms. We show that this new scheme can resist existential forgeries against adaptive chosen-message attacks in the random oracle model. The main contribution is that our security model gets rid of the special security requirement on the generation of the signers' public keys. Adversaries are not required to reveal private keys corresponding to the public keys of its choice to the challenger in attack games. Thus the new multisignature scheme does not suffer from the problem identified by Micali et al., which is shared by many current multisignature schemes. Moreover, if the joint public key of a group of signers in this multisignature scheme is precomputed, the proposed multisignature scheme is optimal. Povzetek: Opisana je shema podpisov za zaščito javnih ključev. 1 Introduction Society oriented cryptography is a notion introduced by Desmedt [1]. A society oriented signature is essentially like a single signature except that is generated by plural individuals simultaneously. A multisignature scheme is one kind of society oriented signature scheme, which allows multiple signers to sign the same message in a collaborative and simultaneous manner. A trivial solution is that every signer signs the message using a normal signature scheme respectively. Obviously, this simple solution will meet the security requirements for the multisignature scheme if the underlying signature scheme is secure. Its main drawback, however, is that both the data expansion and the computation costs for verification increase linearly with the number of signers in the group. Harn [2] submitted two additional properties that need to be achieved in the design of an optimal multisignature scheme: 1. The size of a multisignature should be identical to that of an individual signature. 2. The verification process of a multisignature should be almost identical to that of an individual signature. Hence, in an optimal multisignature scheme, not only the size of signatures is independent of the number of signers participating in signing, but also the computation costs for verification. Since the notion of multisignatures was introduced by Itakura and Nakamura [3], there have been many multisignature schemes proposed in literatures. However, most importantly, until the works of Ohta and Okamoto [4] and of Micali et al. [5], there were no formal security models for multisignatures. This lack of formalism has led not only to some confusion as to the precise security requirements for multisignatures, but also to some multisignature schemes having been subsequently broken [6, 7]. In group oriented cryptosystems, we must consider the possibility that an adversary could corrupt some fraction of participants, and thereby comes into possession of their private keys. We even allow the adversary to specify the public keys of the corrupted participants. In so-called rogue-key attacks, the adversary would register public keys created as a function of public keys of other honest participants. This kind of attacks could be extremely danger to break some multisignature schemes. The security notion of Ohta and Okamoto [4] is not strong enough to withstand such rogue-key attacks in the key generation. Micali et al. [5] gave the first strong security notion for multisignature schemes in the plain public key model. They discussed a series of more sophisticated approaches based on zero-knowledge proofs, by which the private keys corresponding to the public keys can be extracted. Their scheme requires, as a pre-processing step, that the set of potential signers engage in an interactive key generation protocol to generate their key pairs. Besides expensive and resulting in complex public keys, this dedicated key generation enforces the set of potential signers to be static. Boldyrva [8] proposed an efficient multisignature scheme based on the Gap-Diffie-Hellman group. Lu et al. [9] proposed the first multisignature scheme from pairings, provably secure without random oracles. Their security models allow an adversary to create arbitrary public keys for the corrupted signers possibly dependent on the public keys of the honest signers. But they require the adversary to prove the knowledge of the 105 Informatica 34 (2010) 535-540 B.D. Dan et al. corresponding secret keys (KOSK) during the public key registration. For simplicity, it has the adversary to hand over the secret keys of the corrupted signers in key generation algorithm. However, this KOSK assumption is not realized by existing public key infrastructure (PKI). Key registration protocols specified by the most widely used standards, PKCS#10 [10] - used by VeriSign and RFC 4210 [11, 12] do not specify that the Certification Authority (CA) should require proofs of knowledge, instead, specify that the CA should require proofs of possession (POP). That is, applicant is required to hand over the CA a signature, under the public key it is attempted to get certified, of some message that includes the public key and the identity of the applicant. While such requirement might intuitively appear to stop adversaries from picking rogue keys, it does not suffice to realize the security models of [8, 9]. Ristenpart and Yilek [13] analyzed these schemes when key registration requires POPs. They showed that the standardized POP mechanism does not lead to secure multisignatures. Both schemes fall to rogue-key attacks despite the use of standardized POP. They presented a straightforward and natural fix for this problem: simple use separate hash function for POPs and multisignatures at the cost of upgrading existing PKI. In 2006, Bellare and Neven [14] proposed a new multisignature scheme in the plain public key model, requiring nothing more than each signer has a (certified) public key in GF(p), which means neither KOSK or POP is required in key registration protocols. They provided a security proof in the random oracle model. However, their scheme is less efficient than the original Schnorr signature since the computation of verification increases linearly with the number of signers in the group. In this paper, we also propose a new multisignature scheme based on Discrete Logarithms (DL) in the plain public key model. We show that this new scheme can resist existential forgeries against adaptive chosen-message attacks in the random oracle model. The main contribution is that our security model gets rid of the special security requirement on the generation of participants' public keys. Namely, like [14], our security model not only allows so-called rogue-key attacks in the key generation, but also gives the adversary complete freedom in specifying the public keys of the corrupted signers. The adversary is no longer enforced to prove either knowledge or possession of the private keys corresponding to the public keys of its choice. The second contribution is that our multisignature scheme can provide sequentially accountability, which means that not only individual signers can be identified from the multisignatures, but also the order of accountability. The main technique of this paper is the joint public key composed of the public keys of a group of users, which has been used in self-certified signatures [15, 16] and joint encryption scheme [17] to achieve provably secure. Moreover, if the joint public key of a group of signers is precomputed, the proposed multisignature scheme is optimal, since the size of multisignatures and the verification costs are the same as those for the single- signer Schnorr signature scheme, regardless of the number of signers. 2 The new multisignature scheme In this section, we first present a formal definition for the multisignature scheme, and then provide an implementation of Multisignature Scheme based on Discrete Logarithms (MSDL). Let U = {U1, U2, ..., Un} be a group of n signers. 2.1 Definition for multisignature scheme Definition 1. A multisignature scheme is specified as four randomized algorithms: ParaGen, KeyGen, Sign and Verify: ParaGen: takes a security parameter 1k as input and returns a system parameter P, including some cryptographic hash functions. KeyGen: takes the system parameter P as input, each signer Ut of the group U chooses its keypair (x,, y) respectively. Sign: takes as input P, the signers of any subset S of the group U (without loss of generality S = {U1, U2, ..., Ut}) cooperatively generate a multisignature a for a message M by using their keypairs (x,, y,). The joint public key YS of the subset S is composed of the individual public keys (yi, ..., yt}. Verify: takes as input P, M, the joint public key YS and a multisignature a, it returns invalid or valid, with the property that if (P) ^ ParaGen(1k), ((x1, ..., xt}, YS) ^ KeyGen(P) and a^ Sign(P, M, (x1, ..., xt}, YS), then Verify(P, M, a, YS) = valid. 2.2 An Implementation of Multisignature Scheme based on Discrete Logarithms (MSDL) We use the Schnorr signature [18] as the underlying signature, which has been proved to be secure in the random oracle model [19]. ParaGen: A trusted party takes a security parameter 1k as input and returns the system parameter P, which includes a subgroup Gg,p = (g0, g1, ..., gq~1} of a prime order q in the multiplicative group Zp\ where g is a generator with the prime order q, and two (ideal) hash functions H and F, where H: Ggp x...x Ggp ^ Zq* and F: (0, 1}*x Zp*x Zq* ^ Z * q KeyGen: takes the system parameter P as input, each signer U, of a group U chooses its private key xt e Zq* and computes its public key y, = gx respectively. Sign: takes as input P, the signers of a subset S of the group U (without loss of generality S = (U1, U2, ..., Ut}) cooperatively generate a multisignature a for a message M by using their keypairs (xi, yi) as follows: 1. Each signer Ut of the subset S chooses a random number kt e Z *, computes r, = gki and broadcasts (y, r,). 2. After receiving (yp r) (j = 1, 2, ..., t), each signer MULTISIGNATURE SCHEME BASED ON. Informatica 34 (2010) 509-515 511 computes R = r1r2...rt, h = H(y1, y2,..., yt) and f = F(M, R, h). 3. The first signer U1 computes s1 = k1 - fr1 (mod q) and sends it to the second signer U2. 4. After receiving s1 from the first signer U1, the s f second signer U2 first verifies g 1 y = r1 and then computes s2 = s1 + k2 - hfx2 (mod q), and sends it to the third signer U3. 5. After receiving st-1 from the (t - 1)th signer Ut-1, the last signer Ut first verifies g^U y2h••• ytJ 2)f = rir2-rt-i , and then computes s = st-1 + kt - ht'lJxt (mod q). The multisignature for the message Mis a= (f s). Verify: The verifier first computes the joint public key of h ht-1 the subset YS = y1y2 ...yt , where h = H(y1, y2,..yt), and then checks the verification equation of the multisignature f = F(M, gsYSf, H(y1, y2,..., yt)). Completeness: Because s1 = k1 - fx1 (mod q) implies s f g 1 y = ri , s2 = s1 + k2 - hfx2 (mod q) implies gs1( yj y2 h)f = rlr2 . By the same reason, gs-1 (y^.^2h -yt-1h'2)f = r^^r- and s = st-1 + kt - ht-1fxt (mod q) imply the verification equation. Hence, the signature a = (s, f) produced by the algorithm Sign is always valid. Notice that our results can also be carried over to other groups, such as those built on elliptic curves. Notice that the algorithm Verify requires that a verifier computes the joint public key YS = h ht-1 y1 y2 ...yt from the individual public keys of a subset of signers. However, this time-consuming computation is independent of messages to be signed, and hence can be done once for all. Once the joint public key YS of a subset of signers is precomputed, the performance of the multisignature scheme is optimal. 3 Security model and security proof In this section, we first define a new security model for multisignature schemes, which gives the adversary complete freedom in specifying the public keys of the corrupted signers without handing over the corresponding private keys. Then we provide the security proof in this strong security model. 3.1 Security model for multisignature schemes Security model Existential unforgeability against adaptive chosen message attacks (EUF-CMA) [20] is the well-accepted security model for signature schemes, where the adversary is allowed to ask the challenger to sign any message of its choice adaptively, i.e. he can adapt its queries according to previous answers. Finally, the adversary could not provide a new message-signature pair with a non-negligible advantage. Hence, it is natural to require that the multisignatures also satisfy this strong security notion. Accordingly, existential unforgeability for group oriented setting means that the adversary attempts to generate a new multisignature without the knowledge of all private keys. We formalize this intuition as a chosen key model. In this model, the adversary is given a single public key, while the adversary is allowed to choose the key pairs of other signers of the group, and to ask the sign query for any multisignature under any joint public key. His goal is to generate a new multisignature under the joint public keys of the group composed of the given public key and the public keys of its choice. We say that a multisignature scheme is existential unforgeable against adaptive chosen message attacks if no polynomial bounded adversary A has a non-negligible advantage against the challenger in the following game: Setup: The challenger takes a security parameter 1 k as input and runs the randomized system parameter generation algorithm and the key generation algorithm to generate the system parameter P and a public key y. The challenger gives them to the adversary A. Queries: Processing adaptively, the adversary A requests multisignatures queries (Mi, Yi) under any joint public key Yi on any message Mi of its choice, where the challenged public key y might be included in the joint public key Yi. Response: Finally, the adversary A outputs a new multisignature a for a message M under a joint public key Y. The adversary A wins the game if the output multisignature a is nontrivial, i.e. it is not an answer of a sign query (M, Y) for the message M under a joint public key Y, and the joint public key Y is composed of the individual public keys {y1, ..., y,^, y, yj+1, ..., yt}, where the individual public keys {y1, ..., y,-_1, yj+1, ..., yt}, (j e {1, ..., t}), are chosen by the adversary A and y is the given public key. The probability is over the random bits used by the challenger and the adversary. Notice that our security model does not suffer from the same special limitation as the multisignature schemes proposed before. The adversary is given complete freedom in specifying the public keys but the given public key and is not enforced to disclose any knowledge of the corresponding private keys. Notice that the Schnorr signature generation is not deterministic, there may be several signatures corresponding to a given message. Hence, our security model actually adopts the more liberal rule, which makes the adversary successful when it outputs a fresh signature of a given message different from previously obtained 512 Informatica 34 (2010) 509-515 Z. Shao signatures of the same message. Thus, our security model achieves non-malleability (NM) [21]. 3.2 Security proof of the MSDL scheme The security of the proposed MSDL scheme is based on the DL assumption. Definition 2 (DL assumption) A probabilistic algorithm A is said to (t, e)-break DL in a group Ggp, if on input (g, p, q, y = gx) and after running in time at most t, A solves the discrete logarithm problem x = loggpy with probability at least e, where the probability is over the uniform random choice of g from the group Ggp, of x from Zq*, and the coin tosses of A. The (t, e)-DL assumption on the group Gg,P is that if no algorithm (t, e)-breaks DL in Ggp. We have the following theorem about the security of the MSDL scheme. Theorem. Let the hash functions H, F be random oracles. Then the Multisignature Signature scheme based on DL is existentially unforgeable against adaptive chosen message attacks (EUF-CMA) under the DL assumption. Concretely, suppose that there is a EUF-CMA adversary A, which has an advantage eMSDL against the MSDL scheme of t signers and A runs in time at most tMSDL. Suppose that A makes at most qS sign queries, and at most qH, qF queries to the hash functions H, F, respectively. Then there is a DL algorithm B that has an advantage ePh in Ggp with running time t°L, where: eMSDL < (4qFqH)(e°L)1/(3t+1) + 1/q + qs(qF + qs)/p (1) tMSDL > tDL/(2t) - 2qsCexp(Gg,p) (2) Here Cexp(Ggp) denotes the computation cost of a long exponentiation in the group Ggp. Proof: We use the random oracle model to show that the proposed multisignature scheme is secure. Concretely, suppose that there is a EUF-CMA adversary A that has an advantage e MSDL against the MSDL scheme and A runs in time at most tMSDL. Suppose that A makes at most qH, qF queries to the hash functions H and F respectively, and at most qS queries to the sign oracle. Then there is a DL algorithm B that has an advantage eDL in Gg,p with running time tDL. We show how to construct a DL algorithm B that uses A as a computer program to gain an advantage eDL for a DL problem with running time tDL. The challenger takes a security parameter 1* and runs the system parameter generation algorithm and the key generation algorithm to obtain the group Gp,g and y. Its goal to output x = loggpy e Zq . Algorithm B simulates the challenger and interacts with the adversary A in the following attack games: Algorithm B gives the adversary A the resulting system parameter P, and y as the public key of an honest signer. At any time, the adversary A can query hash oracles H or F. To response to these queries, B maintains two lists of tuples for the hash oracles H and F respectively. We refer to these lists as H-list and F-list. The contents of the two lists are "dynamic" during the attack games. Namely, when the games start, they are initially empty, but at the end of the games, they record all pairs of queries/answers. Answering #-oracle Queries. When A queries the oracle H with some message , algorithm B responds as follows: 1. If the query already appears on the H-list in some tuple <, h>, then algorithm B responds with h = H(y1, y2, ..., yt). 2. Otherwise, algorithm B picks a random h in Zq*, and responds with h = H(y1, y2, ..., yt) and adds the tuple << y1, y2, • •, yt >, h> to the H-list. Answering F-oracle Queries. When A queries the oracle F with some message , algorithm B responds as follows: 1. If the query already appears on the F-list in some tuple <, f>, then algorithm B responds with f = F(M, r, h). 2. Otherwise, B checks if h is in the H-list, then generates a random f e Z*, responds with f = F(M, R, h), and adds the tuple <, f> to the F-list. Obviously, in two ways, h and f are uniform in Zq*, and they are independent of A's current view as required. Answering sign queries. When the adversary A requests a signature for under a joint public key Y, algorithm B responds to this query as follows: 1. B checks if Y is a valid joint public key: Y = yy h... yth , where h = H(yu y2,., yt). 2. Algorithm B chooses at random 5, f e Zq\ and computes R = gsYf. 3. If there exists a tuple <, f'> in the F-list with f 4- f', B reports failure and terminates. (The probability of this unfortunate coincidence is at most (qF + qs)/p). 4. Otherwise, B responds with (s, f) to the adversary A, and adds the tuple <, f> to the F-list. Obviously, the outputs of the simulated oracles are indistinguishable from those in the real attacks. Finally, the adversary A returns a new valid message M and its multisignature (s, f) under the joint public key Y composed of public keys {y1, ..., yj.1, y, yj+1, ..., yt}, where y is the challenged public key and others are chosen by the adversary A such that hJ ) f, h), f = F(M g(yv..yj-1 y y^ ...yt where h = H(y1, y2,..., yt) If the adversary A has not queried F(M, R, h) or H(y1, y2,., yt), the probability t-1 MULTISIGNATURE SCHEME BASED ON. Informatica 34 (2010) 108-515 511 Pr[f = f(m, g-(yi...y^ryh^y]+r...y; ) h), where h = H(yuy2,...,yt)] < 1/q, since both the responses F(M, R, H(y1, y2,..., yt)) and H(y1, y2,..yt) are picked randomly. Hence, with the probability (1- 1/q)(^SDL - qS(qF + qS)/p) the adversary A returns a new multisignature (s, f) such that . s( h'-2 h'-1 h h'-\ f f = F(M, g (yl...y]-l y yJ+1 ...yt y,h), where h = H(y1, y2,..., yt) and the responses F(M, R, H(y1, y2,..., yt)) and H(y1, y2,..., yt) are in the F-list and the H-list. The verification equation is equivalent to the equation h' f h'.h'- gs (yv-y,-1 y h' ht-y1+i -yt F(M,R,h) _ n = R, and f22 to the hash queries F(M2, R2, h2) (the third forking point) in the second two runs, ft1 and ft2 to the hash queries F(Mt, Rt, ht) (the (t + 1)th forking point) in the last two runs. Thus, we would obtain 2t multisignatures, satisfying the following equations: gs11(yyi"l--yt" )f11 = R gyi^-yt* )f12 = R (3) (4) g^^-yt"2 )f21 = R. gs22(y^-it"2 )f22 = R where h = H(yu yi,..., yt), where y is the challenged public key and other public keys yi, ..., y,_i, yj+1, ..., yt are chosen by the adversary A. Since Pointcheval and Stern proposed the forking reduction proof [19], oracle replay techniques have been used to provide formal security proofs for ElGamal-like triplet signature schemes. In this proof, we are required to find x = loggpy. It is a knowledge extraction problem. Hence, we try to use the oracle replay techniques to solve this DL problem. We use 2t copies of the adversary A. In the attack games, the adversary A would ask H-query for . We first guess a fixed index 1 < u < qH and hope that (y1, ..., yj.1, y, yj+1, ..., yt) happens to be uth H-query used in the forged multisignature. Then we guess a fixed index 1 < v < qF and hope that happens to be vth F-query used in the forged multisignature. Note that A must ask for H(y1, yj.1, y, yj+1, yt) before for F(M, R, h). Suppose that we make two good guesses by chance, denoted by the event GoodGuess. The probability of the event GoodGuess is Pr[GoodGuess] = 1/(qHqF). Hence, with the probability e= (1 - 1/q)(eMSDL - qs(qF + qs)/p)/(qFqn) > (eMSDL- 1/q - qS(qF + qs)/p)/(qf^H) the adversary A generates a new multisignature. B gives the same system parameter, the same public key y and same sequence of random bits to the 2t copies of the adversary A, and responds with the same random answers to their queries for oracles until they at the same time ask the H-oracle query for < y1, ..., y-1, y, yJ+1, ..., yt>. This is the first forking point. At that point, B gives t independent random answers h1, h2 and ht to the hash queries H in the 2t runs, the first two, gives h1, the second two, gives h2, and the last two, gives ht. Then B gives the first two copies of the adversary A same sequence of random bits, and the same random answers to their oracle queries until they both ask for F(M1, R1, h1). This is the second forking point. At that point, B gives two independent random answers f11 and f12 to the hash queries F(M1, R1, h1) in the first two runs. Similarly, B gives two independent random answers f21 gst1( y yiht... y/Mft1 = Rt gst 2( y^yi ^ ...yt^)ft 2 = Rt From these equations, we can derive loggpy as follows: From eqn.(3) and eqn.(4), we can derive a1 = (s11 -s12)/(f12 - f11) (mod q) such that (y^i "-y^) = ga1 (t+1) By the same way, we can derive a2, ..., at, such that (y^y2 ^...y^) = ga2 (t+2) (y1 y2h...yth~) = gat (t+t) Then from eqn.(t+1)—eqn.(t+t), we have a system of equations x1 + h1 x2 +... + h1t-1 xt = a1 (mod q) x1 + h2x2 +... + h2t-1 xt = a2 (mod q) x1 + htx2 +... + h 1 xt = at (mod q) We can derive x- = loggpy since h1, h2 and ht are different from each other. We use the "splitting lemma" [19] to compute the probability that A works as hoped. Let X be the set of possible sequences of random bits and random function values that take the adversary up to the first forking point where A asks for H(y1, ..., y-_1, y, y-+1, ..., yt); let Y1 be the set of possible sequences of random bits and random function values from the first forking point to the second forking point; let Z1 be the set of possible sequences of random bits and random function values from the second forking point. By assumption, for any x e X, y e Y1, z e Z1, the probability that A, supplied the sequences of random bits and random values (x|y||z), generates a new multisignature is e. Suppose that the sequences of random bits and random function values supplied up to the first forking point in the simulations is a. By "splitting lemma", the probability that Pr{a e "good" subset H} > e/2, and whenever a e Q, y e Y1, z e Z1, the probability that A, supplied the sequences of random bits and random values (a||y||z), produces a forgery is at least e/2. t-1 t-1 t -1 t-1 t-1 512 Informatica 34 (2010) 509-515 Z. Shao Suppose that the sequences of random bits and random function values supplied from the first forking point up to the second forking point in the simulations is b. Thus, the probability that Pr{b e "good" subset Q'} > s/4, and whenever a e Q, b e Q', z e Z1, the probability that A, supplied the sequences of random bits and random values (a||b||z), produces a forgery is at least e/4. By the same reason, we can compute the same probability for the other t -1 cases. Hence the probability that B solves the discrete logarithm in the 2t simulations is > (e)(3t+1)/2(6t+1) > ((eMSDL- 1/q - qs(qP + qs)lp)l(4qFqH))i3M) fiMSDL < ^qq)^)1^ + 1/q + qs(qF + qMp. The time required to run one simulation is tMSDL + 2qsCexp(Ggp). The time required by the simulator B to solve the discrete logarithm loggIy is tDL < 2t(tMSDL +2qsCexp(Ggp)). tMSDL > tDL/(2t) -2qsCxp(Ggp). Q.E.D. 4 Conclusion We have proposed a Multisignature Scheme based on Discrete Logarithms (MSDL). We show that this new scheme can resist existential forgeries against adaptive chosen-message attacks in the random oracle model. The main contribution is that our security model gets rid of the special security requirement on the generation of the participants' public keys. Thus the new multisignature scheme does not suffer from the problem identified by Micali et al., which is shared by many current multisignature schemes. The second contribution is that our multisignature scheme can provide sequentially accountability, which means that not only individual signers can be identified from the multisignature, but also the order of accountability. That is, the first signer U1 is responsible for the first partial multisignature, the second signer U2 is responsible for the second partial multisignature, and the last signer Ut is responsible for the last multisignature. Thus, our scheme is robust. Notice that here sequentially accountability means that verifiers can demand that the signers are responsible for multisignatures according to the specified order rather than that the signers could generate multisignatures only according to the specified order. Furthermore, the proposed multisignature scheme is more efficient, since the size of multisignatures is the same as that of the underlying signatures, regardless of the number of participants. If the joint public key Y of a group of signers is precomputed, the computation cost for verification a multisignature is identical to those of an individual's signature. Thus the proposed multisignature scheme is optimal. However, the forking reduction proof we use makes our proof inefficient. Strictly speaking, our proof is only loosely related to the DL problem according to Micali and Reyzin [22]. Therefore, our multisignature scheme is only applicable to the group of polynomial bounded signers. Although the Schnorr scheme provably secure by oracle replay technique is only loosely related to DL problem, there has been not any efficient forgery attack without solving DL problem first. By similar reasons, our more loosely reduction would also provide users with somewhat security confidence that there is no efficient forgery algorithm without solving DL problem first. We have proposed a Multisignature Scheme based on Discrete Logarithms (MSDL). We show that this new scheme can resist existential forgeries against adaptive chosen-message attacks in the random oracle model. The main contribution is that our security model gets rid of the special security requirement on the generation of the participants' public keys. Thus the new multisignature scheme does not suffer from the problem identified by Micali et al., which is shared by many current multisignature schemes. The second contribution is that our multisignature scheme can provide sequentially accountability, which means that not only individual signers can be identified from the multisignature, but also the order of accountability. That is, the first signer U1 is responsible for the first partial multisignature, the second signer U2 is responsible for the second partial multisignature, and the last signer Ut is responsible for the last multisignature. Thus, our scheme is robust. Notice that here sequentially accountability means that verifiers can demand that the signers are responsible for multisignatures according to the specified order rather than that the signers could generate multisignatures only according to the specified order. Furthermore, the proposed multisignature scheme is more efficient, since the size of multisignatures is the same as that of the underlying signatures, regardless of the number of participants. If the joint public key Y of a group of signers is precomputed, the computation cost for verification a multisignature is identical to those of an individual's signature. Thus the proposed multisignature scheme is optimal. However, the forking reduction proof we use makes our proof inefficient. Strictly speaking, our proof is only loosely related to the DL problem according to Micali and Reyzin [22]. Therefore, our multisignature scheme is only applicable to the group of polynomial bounded signers. Although the Schnorr scheme provably secure by oracle replay technique is only loosely related to DL problem, there has been not any efficient forgery attack without solving DL problem first. By similar reasons, our more loosely reduction would also provide users with somewhat security confidence that there is no efficient forgery algorithm without solving DL problem first. Acknowledgement The author would like to thank the anonymous reviewers for their valuable comments and suggestions that improve the presentation of this paper significantly. MULTISIGNATURE SCHEME BASED ON. Informatica 34 (2010) 110-515 511 References [1] Y. Desmelt (1988). Society and group oriented cryptography: A new concept, Advances in Cryptology-Crypto'87, LNCS 293, Springer, Berlin, pp. 120-127. [2] L. Harn (1999). Digital multisignature scheme with distinguished signing authorities, Electron. Lett ., 35(4), pp.294-295. [3] K. Itakura and K. Nakamura (1983). A public key cryptosystem suitable for digital multisignatures, NEC Research & Development, (71): pp. 1- 8. [4] K. Ohta and T. Okamoto (1999(. Multi-signature schemes secure against active insider attacks, IEICE Transaction on Fundamentals of Electronics communications and computer Science, E82-A(1), pp.21-31. [5] S. Micali, K. Ohta, and L. Reyzin (2001). Accountable-subgroup mulitisignatures, In ACM Conference on Computer and communications Security, 2001. [6] L. Harn (1994). Group-oriented (t, n) threshold digital signature scheme and digital multisignature, IEE Proc.-Comput. Digit. Tech, 141(5), pp.307313. [7] C.-M. Li, T. Hwang, and N.-Y. Lee (1994). Threshold-multisignature schemes where suspected forgery implies traceability of adversarial shareholders, Advances in Cryptology - Eurocrypt 94, LNCS 950, Springer-Verlag, pp. 194-204. [8] A. Boldyreva (2003). Threshold signature, multisignature and blind signature schemes based on the gap-Diffie-Hellman-group signature scheme, Proceedings of PKC 2003, LNCS 2567, SpringerVerlag, pp. 31-46. [9] S. Lu, R. Ostrovsky, A. Sahai, H. Shacham, and B. Waters (2006). Sequential Aggregate Signature and Multisignature without Random Oracle, In EUROCRYPTO'06, LNCS 4004, Springer-Verlag, Berlin, pp. 465-485. [10] PKCS#10: Certification request syntax standard, RSA Data Security, Inc., 2000. [11] C. Adams, S. Farrell, T. Kause, T. Monen (2005). Internet X.509 Public Key Infrastructure Certificate Management Protocol (CMP), Internet, Engineering Task Force RFC 4210. [12] J. Schaad (2005). Internet X.509 Public Key Infrastructure Certificate, Request Message Format, Internet Engineering Task Force RFC, 4211. [13] T. Ristenpart and S. Yilek (2007). The Power of Proofs-of-Possession: Securing Multiparty Signatures against Rogue-Key Attacks. in Advances in Cryptology - EUROCRYPT 2007, LNCS 4515, Springer-Verlag, pp. 228-245. [14] M. Bellare and G. Neven (2006). Multi-signatures in the plain public-key model and a generalized forking lemma, CCS 2006, ACM, pp.390-399. [15] Zuhua Shao (2007). Self-certified Signatures Based on Discrete Logarithms, in Proceedings of WAIFI 2007, LNCS 4547, Springer-Verlag, pp.252-263. [16] Zuhua Shao (2007). Self-certified signature scheme from pairings, Journal of Systems and Software, 80(3), pp. 388-395. [17] Zuhua Shao (2009). Dynamic and efficient joint encryption scheme in the plain public key model, Computers and Electrical Engineering, 35(1), pp. 189-196. [18] C. P. Schnorr (1991). Efficient signature generation by smart cards, Journal of Cryptology, 3(3), pp. 161174. [19] D. Pointcheval and J. Stern (2000). Security arguments for digital signatures and blind signatures, Journal of Cryptology, 13(3), pp. 361396. [20] S. Goldwasser, S. Micali, and R. Rivest (1988). A digital signature scheme secure against adaptive chosen-message attacks, SIAM Journal on Computing, 17(2), pp.281-308. [21] M. Bellare, A. Desai, D. Pointcheval, and P. Rogaway (1998). Relation among notions of security for public-key encryption schemes, In Crypto'98, LNCS 1462, Springer-Verlag, Berlin, pp. 26-45. [22] S. Micali and L. Reyzin (2002). Improving the exacting security of digital signature schemes, Journal of Cryptology, 15(1), pp.1-18.