Informatica 35 (2011) 123-137 83 An Identity-Based Mediated Signature Scheme Without Trusted PKG Xiaofeng Wang and Shangping Wang School of Science, Xi'an university of technology, Xi'an 710048, P.R.China E-mail: xfwang66@sina.com.cn Keywords: ID-based signature, ID-based mediated signature, without trusted PKG, immediate revocation, GDH group Received: July 14, 2008 Mediated Signature Scheme provides an efficient method for fast revocation of a user's identity in identity (ID)-based cryptosystems. The only ID-based mediated signature scheme was proposed by Cheng et al. from bilinear pairing in [8], Unfortunately their scheme has an inherent flaw that the PKG is fully capable to generate a valid mediated signature of some message on behalf of its signers by only utilizing the public information of the system. In this paper, an efficient ID-based mediated signature scheme without trusted PKG is proposed. Compared with the scheme [8], the proposed scheme has other property besides achieving immediate revocation of a signer's ID. That is, proposed scheme is ID-based, but without any assumption of pre-fixed trusted relationship between users and PKG, which effectively solves the problem that exists in some existing ID-based public key cryptosystems in which a trusted PKG and key escrow are needed. Povzetek: Predstavljena je metoda elektronskega podpisovanja. 1 Introduction The ID-based public key cryptosystems allow public keys of a user to be computed easily and publicly from a string to correspond with his (her) identity (such as name, telephone number, email address or an IP address). This characteristic avoids the necessity of using certificates and PKI system. Compared with certificate-based cryptosystems, ID-based cryptosystems have simplified key management since there is no need to maintain a great database containing a list of public keys and their respective owners. Therefore, ID-based public key cryptosystems have a wide application foreground in information security field. However, two inherent limitations of ID-based cryptosystems have hindered its development in implementing. The first limitation is the necessity of a trusted party, referred to as Private Key Generator (PKG) and key escrow. In ID-based cryptosystems, a user's identity (ID) is used as his/her public key, for this work, users cannot generate their own key-pairs. As alternative, this is done by a PKG. The PKG uses a master key to generate private keys for users. Usually, PKG is supposed to be trusty. However, there is not a fully trusted PKG in practice. Since PKG knows private key of each user, a dishonest PKG can impersonate any user and forge their signatures. Recent research shows that this problem can be mitigated by splitting PKG's master key between a numbers of PKGs[l], but this adds extra complexity to key generation. The second limitation is that current ID-based cryptosystems cannot provide an efficient solution to immediately revoke a user's identity. The typical way of revoking a user's identity is to concatenate a valid period to the identity string. Revocation is achieved by instructing PKG to stop issuing new private keys for revoked identities. This involves the need to periodically re-issue all private keys in the system, and the PKG must be online most of the time, otherwise, the user's identity cannot be immediately revoked using this method. Boneh et al. introduced a method for obtaining fast revocation of a user's public key privilege in RSA-based cryptosystems. They call it mediated RSA (mRSA)[2], The main idea behind mRS A is to introduce a special online entity in standard RSA, called Security Mediator (SEM). To sign or decrypt a message, user must first obtain a message-specific token from the SEM, and he(she) cannot use his (her) private key without this token. To revoke user's ability to sign or decrypt, the administrator instructs the SEM to stop issuing tokens for user's public key. Mediated RSA (mRSA) is a simple and practical method of splitting RSA private keys between the user and the SEM. Neither the user nor the SEM can cheat one another since each signature or decryption must involve both parties. mRSA allows fast revocation of user's security privileges. However, mRSA still relies on public key certificates to derive public keys. Boneh et al.[3] and Ding et al.[4] proposed Identity-based mRSA schemes, respectively. The basic idea behind identity-based mRSA is the use of a single common RSA modulus n among all users of a system. This modulus is assumed to be public and contained in a public key certificate, and the certificate is issued, as usual, by a Certificate Authority (CA). This method cannot essentially avoid the necessity of using certificates and CA. Boneh et al. first gave a practical ID-based encryption scheme from Weil pairing [5] in 2001. Based on this scheme, Libert et al. [6], Baek et al. [7] proposed an ID-based mediated encryption scheme, respectively, using the 102 Informática 35 (2011) 101-84 K.V. Devi et al. similar method given in mRSA. Both schemes provide efficient methods to immediately revoke a user's identity. Very recently, Cheng et al. proposed an ID-based mediated signature scheme [8]. Their scheme avoids the using of certificates and CA. The main idea behind it is to introduce a SEM, in a general ID-based signature scheme. A signer's private key is split into two parts. One part is hold by himself(herself), and another is given to the SEM. Therefore, only with the help of the SEM, can a signer generate a valid signature. As a result, an immediate revocation of a signer's ID (i.e. a signer's signing privilege) is possible by instructing the SEM not to help the revoked user anymore. Unfortunately, their scheme has an inherent flaw, it is that the PKG is fully capable to generate a valid mediated signature of some message on behalf of its signers by only utilizing the public information of the signers and the SEM. In this paper, we propose an ID-based mediated signature scheme from bilinear pairing. Proposed scheme has other properties besides achieving immediate revocation of signer's ID. First, our scheme is ID-based, but without any assumption of pre-fixed trusted relationship between users and PKG, it solves the problem that exists in some existing ID-based public key cryptosystems, in which a trusted PKG and key escrow are needed, in certain extent. Second, our scheme is able to prevent the dishonest PKG from impersonating the signer to generate a valid mediated signature. To construct such a scheme, we first improve Cheng's ID-based signature scheme [8], to make it has the property that the PKG is unable to generate a valid signature on behalf of any signers even if it knows the private keys of the signers, then used it to construct an efficient ID-based mediated signature scheme without trusted PKG. The remaining sections are organized as follows. In Section 2 we briefly introduce some related mathematical knowledge. In Section 3 we recall the Cheng's ID-based mediated signature scheme. In Section 4 we propose an ID-based signature scheme, based on this scheme, we propose a new ID-based mediated signature scheme without trusted PKG and analysis its security in Section 5, then we conclude this paper in Section 6. 2 Preliminaries 2.1 Bilinear pairings Let q be a prime with I bits length. Let G\ be an additive cyclic group generated by P, whose order is q. Let G2 be a multiplicative cyclic group of the same order q. A bilinear pairing is a map e : G\ x G\ —> G2 satisfies the following properties: (1) Bilinear: For any aPhP e Gu eiaP.bP) = eiP Pf'\ where a,b € Z*; (2) Non-degenerate: There exists P,Q e G\ such that (3) Computable: There exists an efficient algorithm to compute HP Q) for all P, Q e G\. 2.2 Gap Diffie-Hellman (GDH) group We consider the following problems in G\. (1) Discrete logarithm problem (DLP): Given Q e Gi, to find an integer x G Z*, such that Q = xP (Assuming such an integer exists.). (2) Computational Diffie-Hellman problem (CDHP): Given aP;bP1 € Gi, to compute abP. (3) Decisional Diffie-Hellman problem (DDHP): Given P. aP; bP; cP € Gi, to decide whether c = ab mod q, if so, (P, aP; 1)1'. cP) is called a valid Diffie-Hellman quaternion. Definition 2.1 We call Gi a gap Diffie-Hellman (GDH) group if DDHP can be solved in polynomial time but there is no polynomial time algorithm to solve CDHP on G\ with non-negligible probability. Such a group can be found in super-singular elliptic curve or hyper-elliptic curve over finite fields. For more details, see [9,10,11,12,13,14], An efficient method to solve DDHP is introduced in [15]: assuming there is a bilinear map e, then (P. a P. hi'. cP) is a valid Diffie-Hellman quaternion e(aP,bP) = e(P,cP). Schemes in this paper can work on any GDH group. Throughout this paper, we define the system parameters in all schemes as follows: G\, G2, P, q and e are as described above. These system parameters can be obtained using a GDH Parameters Generator [5,15]. Define two cryptographic hash functions: Hx : {0,1}* ->• Gi, H2 : {0,1}* ->• ryif. Aq■ 3 Cheng's ID-based mediated signature scheme and its security analysis 3.1 The scheme Cheng's ID-based mediated signature scheme (for short CMSS) consists of three entities: PKG, SEM and signers. There are four algorithms: Setup, MeExtract, MeSign and Verify. They are described as follows: (1) Setup: Sharing the same system parameters with above. PKG picks s G Z* at randomly as a master key and computes the system public key Ppub = sP. Ppub is published but s is kept secretly. (2) MeExtract: Given an identity ID, PKG chooses sw G Z* at randomly, computes: Qm = H\ (ID) d"pr = sw ■ Qid dsem = {s_sid).qid I)'['/')'' is sent secretly to the signer whose identity is ID, as the private key of the signer, and (£>f™, ID) is sent secretly to the SEM. (3) MeSign: To sign a message M, the signer interacts with the SEM as follows: AN IDENTITY-BASED MEDIATED SIGNATURE SCHEME. Informatica 35 (2011 ) 83-90 85 The signer chooses r\ G Z* at randomly, and computes: Ri = h P. The triple (M,RhID) is sent to the SEM. After having received (M.R\. II)), the SEM first checks the ID of the signer is not revoked. It then picks f2 G Z* at randomly, and computes: R2 = HP R = R1+R2 h = H2(M,R) Ssem = hPpub + hDs™ Then (R. Ssem) is sent back to the signer. After having received (R. Ssem), the signer computes: h = H2(M,R) Suser — hPpub+ S = Suser + Ssem He verifies whether e(P,S) = e{Ppub,R + hQw) holds. If so, the signature on message M under ID is set to be a=(R,S). (4) Verification: Given a signature a = ( R. S) on message M under ID, the verifier computes: h = H2(M,R) Qid = H^ID) He accepts the signature if eil'. S) = e(Ppub,R + hQw)• 3.2 Security analysis The signature on message M under ID is: S = Suser + Ssem = hPpub+ hDfDer +f2PPub+ hDs™ = s(R1+R2) + hQID = sR + hsQw It is obvious that not only can the dishonest PKG generate every user's private key and impersonate any user to forge their signatures, but also generate a valid mediated signature on message M under ID by only utilizing the public information (M. R. ID). 4 Improved ID-based signature scheme and its security 4.1 Improved ID-based signature scheme Our ID-based signature scheme is based on GDH groups. It is a variant of the ID-based signature scheme given by Yi [16]. Similar variants can be seen in [8,23,24], The security analysis of the scheme can be found in [17]. In some ID-based signature scheme such as [12,16,18], the PKG can directly forge signature by using of the signature's public information. Our construction avoids this flaw. Our ID-based signature scheme consists of four algorithms: Setup, Extract, Signing and Verification, which is described as follows. (1) Setup: Given a security parameter I, PKG runs the GDH Parameters Generator to obtain Params = {G\, G2, P, q , e, H\, H2}. Then it picks a random number s G Z* as a master key and computes the system public key Ppub = sP. Ppub is published but s is kept secretly. (2) Extract: It is a key extraction algorithm engaged by PKG and a user. A user submits and authenticates his/her identity ffl G {0,1}* to PKG, PKG inputs system parameters, master key and the user's identity II); and outputs the user's public key and private key. The signer randomly chooses an integer ru G Z*, sets Ru = ruP, submits (ID, Ru) to PKG, and authenticates his(her) identity to PKG by out-band mechanism. PKG generates signer's public key and private key: Qu = H\ {ID. Ru), Du = sQu, and sends Du to the signer via a secure channel. (3) Signing: Given a message M, the signer picks a random number rv G Z* such that rvru mod I, and computes: Rv = rvP h = H2(M,ID,RU,RV) X = rurvP + hDu The signature on message M is set to be 8 = (X,RU,RV). (4) Verification: Given a signature 8 = {X,RU,RV) on message M under ID, the verifier computes: h = H2(M,ID,RU,RV) Qu = H\ (ID,RU) He accepts the signature if e(X,P) = e(Ru,Rv)e(hQu,PPub)- 4.2 Security analysis Theorem 4.1 The improved ID-based signature scheme is secure against existential forgery under adaptively chosen message and ID attack in the random oracle model. Analysis: Generally, an ID-based signature scheme involving two security models [10]. The first is adaptively chosen message and ID attack, the second is adaptively chosen message and given ID attack. The latter is in fact the security notion of a general signature scheme. Using the same methodology as Lemma 1 in [10], we can prove that, if there exists a forger / / who performs an existential forgery under an adaptively chosen message and ID attack against our scheme, then, making use of //, we can construct an algorithm with the same advantage as //, against our scheme under adaptively chosen message and given ID attack. Following certification process shows, if there exists a adversary which performs an existential forgery against our scheme under adaptively chosen message and given ID 86 Informatica 35 (2011) 83-90 X. Wang et al. attack, then we can construct an algorithm that solves the CDHP by running the adversary as a subroutine. Proof: We cannot directly reduce the security of our ID-based signature scheme to the hardness of the CDHP because our scheme contains a random value in its signature [13]. We reduce the security of our ID-based signature scheme to the hardness of the CDHP by making use of the oracle replay technology and the forking lemma [20,21], Given an identity ID, the corresponding public/private key pair is (QU,DU). If there exists an efficient algorithm S3 against our scheme under adaptively chosen message and given ID attack, then an algorithm -/r can be constructed as follows: inputs P, Ppub = sP and Qu = tP for some t G Z*, if chooses a message M, uses the oracle replay method and the forking lemma [20,21], can obtain two valid signatures (M. Ru. Rv. h\. X\j and (M,Ru,Rv,h2,X2) such that h\ / h2, and satisfying equations e(XuP) = e(Ru,Rv)e(hiQu,Ppub) and e(X2,P) = e(Ru,Rv)e(h2Qu,Ppub). That is, g(Xi -X2,P) = e((h -h2)Du,P). We have e((Xi -X2) - (h1-h2)Du,P) = 1G2. Since e has the property of non-degeneracy, we have (X\ -X2) - (hi - h2)Du = O (here O is an ideally defined point, namely the point at infinity, and is also recognized as a point on elliptic curve.), and Du = ih\ — h2)~l(Xi —X2) (see [8]). It means that can solve an instance of CDHP in Gi since Du = sQu = stP = (h - h2yl(Xi -X2). 5 Proposed scheme and its security analysis The idea behind ID-based mediated signature is to introduce a trusted online party SEM in a general ID-based signature scheme. A private key of the signer is split into two parts. One part is given to the signer, and another is given to the SEM. Therefore, only with the help of the SEM, can a signer generate a valid mediated signature. As a result, an immediate revocation of a signer's signing privilege is possible by instructing the SEM not to help the revoked user anymore. 5.1 Our scheme Now we give the mediated version of the improved ID-based signature scheme in Section 4.1, and show how can avoid forging signature by dishonesty PKG in our scheme. Our scheme consists of three entities: PKG, SEM and signer, and four algorithms: Setup, MeExtract, MeSign and Verification, they are described as follows: (1) Setup: Given a security parameter I, PKG runs the GDH Parameters Generator to obtain Params= {G\,G2,P, q , e, Hi, H2}. PKG picks two different random numbers V| G Z* and s2 G Z*, lets .v V| I s2 as the master key, and generates system public key Ppub = sP. Ppub is published but V|, .v? are kept secretly. (2) MeExtract: the signer randomly chooses an integer rs G Z*, sets Rs = rsP, submits (ID,RS) to PKG and authen- ticates his/her identity ID to PKG by out-band mechanism. PKG generates the public key and private key of the signer: Qs = Hi (ID, RS),DS = siQs. PKG generates the private key of the SEM: DSEM = s2Qs. Then sent Ds to the signer, sent (■DsemJD) to the SEM, respectively, over a confidential and authentic channel. (3) MeSign: To sign a message M, the signer must present a service requisition to SEM. He interacts with the SEM as follows: The signer chooses a random number r\ G Z* such that rirs mod q^l and r\ modI, computes: Ri = rip Zs = rsnP + H2(M,ID,Rs,Ri)Ds Signer sends (M,ID,Rs,RhZs) to the SEM. After having received (M,ID,Rs,Ri,Zs), the SEM checks that the ID of the signer is not revoked, then computes: v, = H2(M,ID,Rs,Ri) Z = Zs + vsDsem and verifies: e(Z,P) = e(Rs,Ri)e(vsHi(ID,Rs),Ppub) If so, the signer is a legitimate participant, and the SEM provides service for him/her. SEM then picks a random number r2 G Z* such that r\ mod q / I, and computes: R2 = r2P Ssem = r22P + H2(M,ID,Rs,Ri,R2)Dsem The pair (R2,Ssem) is sent to signer. After having received (R2, Ssem), the signer computes: v = H2(M,ID,Rs,Ri,R2) Ss = rjP + vDs S = Ss + Ssem and verifies: e(S,P) = e(Ri,Ri)e(R2,R2)e(vQs,PPub) If so, the mediated signature on message M under ID is set to be a = (Rs,RhR2,S). (4) Verification: Given a signature a = (Rs,Ri,R2,S) on message M under ID, the verifier computes: v = H2(M,ID,Rs,RhR2) Qs = Hi(ID,Rs) He accepts the signature if and only if e(S,P) = e(Ri,Ri)e(R2,R2)e(vQs,Ppub). 5.2 Security analysis Theorem 5.1 In our scheme, the dishonest PKG can not impersonate its signer to generate a valid mediated signature. AN IDENTITY-BASED MEDIATED SIGNATURE SCHEME. Informatica 35 (2011 ) 83-90 87 Analysis: We discuss the Theorem 5.1 from the following two aspects: First, dishonest PKG can not generate a valid mediated signature by only utilizing the public information of a signer and the SEM. For the valid mediated signature on message M under signer U' s identity ID : S = Ss + Ssem = rjP + 4 P + vsQs Consider following impersonation attack[19]: PKG wants to impersonate the signer U to forge a mediated signature, it can do as follows: Chooses r's, r[, r'2 G Z* at randomly, computes: K = r'P R[ = r[P R'l = r'2P Lets Q's = H\ (ID. R's) as the U's public key, then PKG computes: V = H2(M,ID,R's,R,1,R,2) S> = rfp + rfp + v'sQ* Mediated signature is a' = (R's,R[,R'2,S'). Because e(S',P) = e(R'vR[)e(R'2,R'2)e(VQi,Ppub), PKG forged a valid mediated signature. However, signer U can provide a proof to convince that the mediated signature is forged by PKG. To do so, he firstly sends Rs = rsP to an arbiter, and provides a knowledge proof that he knows Qs = H\ (ID. Rs) and private key Ds s\ Qs; the arbiter randomly chooses a secret integer a I Oii/v + I )(qs I qn-, )/I, then CDHP can be solved with probability e > 1/9 within running time T < (23qH2To)/£o- Proof: Let G\ be a cyclic additive group defined in Section 2. We show how to construct an algorithm that compute abP for a randomly given instance I', a I'. bP G G\ (where a, b G Z*) by running - / as a subroutine. During the game, will consult for answers to the random oracles H\,H2. Roughly speaking, these answers are randomly generated, but to maintain the consistency and to avoid collision, 38 keeps two lists L\ and L2 to store the answers. We assume that will ask for H\ (ID, •) before ID is used as an input of any other queries. Initialization: Fix an identity ID, lets Ppub = aP as system public key. ID-Hash Queries (Hi): When ¡1), is submitted to H\ oracle, first scans L\ of sorted elements (ID,. QSi) (where 88 Informatica 35 (2011 ) 83-90 X. Wang et al. I < / < qu[ ) to check whether H\ was already defined for that input. If it was, the previously defined value QSi is returned. Otherwise, picks r,- G Z* at randomly, defines f bP, if IDi = ID , _ ^ , . Qs- = { „ , • , and stores (DUQS.) m ^ \ r(P, otherwise v U- Private Key Extraction Queries (MeExtract): When requests the private key associated with an identity IDk (where \ < k < qt ), recovers the corresponding (.IDk,QSk) from L\. Then 83 picks uk G Z* at randomly, lets Dk = UkQsk as the private key corresponding to IDk. Note that must not ask the private key corresponding to the IDk = ID. Message-Hash Queries (H2): When a message (.Mj,IDj) is submitted to the Hi oracle, first scans L2 of sorted elements M;.ll);. A',.. A'i .R\. v; (where 1 < j < Qh2) to check whether Hi was already defined for that input. If it was, the previously defined value Vj is returned. Otherwise, picks rij,r2j,Vj €rZ* at randomly, returns Vj as the answer to , lets RSj = rjP, /-i 1 = nP, ¡hj = r2jP, and stores M;.II);.R, ,R\ .R\. r, inL2. Signing Queries (MeSign): If -/r asks the signature on M, of IDt, 8§ first scans L\ to recover the previously defined value (IDt, Qs, ), then scans L2 to recover the previously defined value (M,. ID,. RSl.R\rRir v,). Then 88 lets St = r\P + r\P + rtvt(aP), and returns o, = Sign(Mt,IDt) = (Mt,IDt,RSt,Rh,R2t,vt,St) to J? as the answer. Obvious, at is a valid ID-based mediated signature, i.e. it satisfies the verify equation e(St,P) = e(Rh,Rh)e(R2t,R2t)e(vtQSt,Ppub). Output: We need to take care of a nasty problem of collisions of the query result of MeSign and H2, as mentioned in [20] (Proof of Lemma 4). This may cause some "collision"; a query result of MeSign may produce a value that is inconsistent with other query results of MeSign or H2. In this case, just outputs fail and exits. If no collisions have appeared, 8§ outputs a valid signature a = (M.I I). Rs. R\.Ri- V- S) with probability £0, which is expected to be valid for the fixed ID, without accessing any oracles except Hi, Hi. i.e. it satisfies the verification equation e(S,P) = e(Ri,Ri)e(R2,R2)e(vQs,Ppub). Considering Ppub = aP, Qs = bP, we have e(S,P) = t{RuR{)t{R2,R2)t{vabP,P)......(1). We apply the oracle replay technique which was invented by Pointcheval and Stern in [20,21], in which, ./i replays the same random tape but different choices of Hi, as done in the forking lemma [20], we obtain signature (M,ID,Rs,Ri,R2,V,S') with v / V, which are expected to be valid with respect to hash function H{ on iM.ID.Rs.R\.Ri). So we have e(S'.l') = e(R\,Ri)e(R2,R2)e(v' abP,P)......(2). From (1) and (2), we have: e{S-S',P) = e{{v-v')abP,P) Then we obtain abP = ^r. Since the oracle Hi, H2, MeExtract, and MeSign generate random distribution and are indistinguishable from the original scheme, learns nothing from query re- sults. Therefore, 88 works as expected if no collisions appear in Output. Intuitively, since v is random, the possibility of collisions is negligible; in [20] (Proof of Theorem 3), this probability was computed explicitly, and furthermore, it was proved that the oracle replay in Output produces valid signatures (M,ID,Rs,Ri,R2,v,S) and (M. ID. Rs. R\. Ri. v". .S" j with the expected properties such that v / v' with probability e > 1/9 within the time T < (23qH2T0)/e0. 5.3 Discussion There are two types of possible attacks against the proposed scheme. The first comes from the choice of the random numbers used in our scheme; the second comes from the attacks on the discrete logarithm of elliptic curves. We show the details as following: (1) Choosing appropriate random numbers In our ID-based signature scheme (see the Section 4.1(3)), if rvru mod q = 1, then X = rurvP + hDu can be represented as X = P + hDu, thus the signer's private key can be computed from l)u h UX — i'). In our ID-based mediated signature scheme (see the Section 5.1(3)), if rirs mod q=l, then Zs = ririP + vsDs can be represented as Zs = P + vsDs, thus the signer's private key can be computed by SEM from Ds = vj 1(ZS -P). If r] mod q I, then Ss = rjP + vDs can be represented as S s = P+vDs, thus the signer's private key can be computed by the verifier from l)s v 1 (Ss — I'). If r\ mod q I, then Ssem = r2P + vDSEM can be represented as Ssem = P + vDsem, thus the SEM's private key can be computed by the signer from DSEm = v 1 (Ssem ~ !')■ The probability of both rv ru mod q I and/v'v mod i/ 1 are all \/(q — 1), and the probability both r] mod q I and r\ mod q = 1 are all \/(q — 1). It is neglectable when q is large enough, (e.g., The bit length of q exceed the length that defined in the international standards for elliptic curve cryptography, such as ANSIX9.62, ANSIX9.63, IEEE-PI363, ISO/IEC14888,etc..) In our scheme, we restrict that rvru mod I, nrs mod q ^ 1, r\ mod q ^ 1, and r\ mod q ^ 1 to avoid these events taking place. Though similar ID-based signature scheme[16] and its variants [8,23,24] have not any restriction for choosing random numbers, and do not discuss this security flaw, but we especially emphasize such a restriction in order to make our scheme more perfect. (2) The attacks on the discrete logarithm of elliptic curves Our scheme is based on elliptic curve cryptography whose security relies on the difficulty to solve the discrete logarithm problem of the elliptic curve abelian group (The Elliptic Curve Discrete Logarithm Problem, ECDLP). The results show, the time complexity is exponential to break the ECDLP using the Pollard rho algorithm that is acknowledged most effective attack method for ECDLP [25,26]. However, not all the elliptic curves are suitable for cryptography. In order to guarantee the security, we must choose AN IDENTITY-BASED MEDIATED SIGNATURE SCHEME. Informatica 35 (2011 ) 83-90 89 secure elliptic curves whose orders are large prime numbers (e.g. Its bit length exceeds 234[26]) or include large prime factors. The result [27] provided four efficient methods to select secure elliptic curves. As long as select appropriate secure elliptic curves, as far as we know, there are not efficient methods to break ECDLP. 6 Conclusions We improved an ID-based signature scheme and constructed an efficient ID-based mediated signature scheme from the bilinear pairing. Our ID-based mediated signature scheme has a character that the dishonest PKG can not impersonate signer to generate a valid mediated signature. Our scheme not only provides an efficient method for immediate revocation of a user's identity in ID-based public key cryptosystems, but also solves the problem that exists in some existing ID-based signatures scheme, in certain extent, in which, a trusted PKG and key escrow are needed. Acknowledgement This work was supported by the National Natural Science Foundation of China (60873268); the China Postdoctoral Science Foundation (No.20080431238 and No.200902596); the Natural Science Foundation Research Plan of Shaanxi province of China (No.08JK382 and NO.2009JM8004-5). References [1] T.Candebat, C.R.Dunne and D.Gray. (2005) Pseudonym Management using Mediated Identity-Based Cryptography, In Advances in 2005 ACM Workshop on Digital Identity Management (DIM'05), Fairfax, Virginia, USA, pp. 1-10. [2] D.Boneh, X.Ding, G.Tsudik and C.Wong. (2001) A method for fast revocation of public key certificates and security capabilities, In Advances in the 10th USENIX Security Symposium, Washington D.C., pp.297-308. [3] D.Boneh, X.Ding, G.Tsudik, Identity-based Mediated RSA.(2002) In Advances in 3rd. International Workshop on Information and Security Applications, Jeju Island, Korea, pp. 192-209. [4] X.Ding,G.Tsudik.(2003) Simple Identity-Based Cryptography with Mediated RSA. volume 2612 of LNCS, Springer-Verlag, pp. 192-209. [5] D.Boneh, M.Franklin.(2001) Identity-based encryption from the Weil pairings, In Advances in Cryptology-Crypto2001,volume 2139 of LNCS, Springer-Verlag, pp.213-229. [6] B.Libert,J.Quisquater.(2003) Efficient revocation and threshold pairing based cryptosystems. In Advances in 22nd Symposium on Principles of Distributed Computing, ACM Press, pp.163-171. [7] J.Baek and Y.Zheng.(2004) Identity-based threshold decryption. In Advances in PKC'04, volume 2947 of LNCS. Springer-Verlag, PP.248-261. [8] X.Cheng, L.Guo, X.Wang.(2006) An Identity-based Mediated Signature Scheme from Bilinear Pairing. International Journal of Network Security, Vol.2, No.l, pp.29-33. [9] Q.Wu, WSusilo, Y.Mu, F.Zhang.(2006) Efficient Partially Blind Signatures with Provable Security. In Advances in ICCSA 2006, volume 3982 of ZjVCS,Springer-Verlag, pp.345-354. [10] J.C.Cha and J.H.Cheon, An identity-based signature from gap Diffie-Hellman groups, In Advances in PKC 2003, volume 2567 of LNCS, Springer-Verlag, pp.1830. [11] S.D.Galbraith, K.Harrison and D.Soldera.(2002) Implementing the Tate pairings. In Advances in ANTS 2002, volume 2369 of LNCS, Springer-Verlag, pp.324-337. [12] F.Hess.(2003) Efficient identity based signature schemes based on pairings. In Advances in Select Areas in Cryptography, SAC 2002, volume 2595 of LNCS, Springer-Verlag, pp.310-324. [13] J.H.Cheon, Y.Kim, H.J.Yoon.(2004) A New ID-based Signature with Batch Verification, Cryptology ePrint Archive, Report 2004/131. [14] X.Huang,YMu,WSusilo,F.Zhang.(2005) Short Designated Verifier Proxy Signature from Pairings. In Advances in EUC Workshops 2005, volume 3823 of LNCS. Springer-Verlag, pp.835-844. [15] D.Boneh, B. Lynn and H. Shacham.(2001) Short signatures from the Weil-pairing. In Advances in Asi-acrypt'01, volume 2248 of LNCS, Springer-Verlag, pp.514-532. [16] X.Yi.(2003) An identity-based signature scheme from the Weil pairing, IEEE Communications Letters, vol.7, no.2, pp.76-78. [17] X.Cheng,J.Liu,X.Wang.(2005) Identity-based aggregate and verifiably encrypted signatures from bilinear pairing. In Advances in ICCSA 2005, volume 3483 of LNCS, Springer-Verlag, pp. 1046-1054. [18] K.Paterson.(2002) ID-based signatures from pairings on elliptic curves. Electronics Letters, vol.38, no. 18, pp. 1025-1026. 90 Informatica 35 (2011) 83-90 X. Wang et al. [19] X.Chen, F.Zhang, K.Kim.(2002) A new ID-based group signature scheme from bilinear pairings. Cryptology ePrint Archive, Report2002/184, http://eprint.iacr.org/ [20] D.Pointcheval and I.Stern.(2000) Security arguments for digital signatures and blind signatures, lournal of Cryptology, vol.13, no.3, pp.361-396. [21] D.Pointcheval and J.Stern.(1998) Security proofs for signature schemes. In Advances in Cryptology-Eurocrypt 96, volume 1163 of LNCS, SpringerVerlag, pp.387-405. [22] R.Gennaro, SJarecki, H.Krawczyk and T. Ra-bin.(1996) Robust threshold DDS signatures. In Advances in Cryptology-Eurocrypt'96, volume 1070 of LNCS, New York,Springer-Verlag, pp.354-371. [23] I.Malone-Lee.(2002) Identity-Based Signcryption. Cryptology ePrint Archive, http://eprint.iacr.org /2002/098/. [24] B.Libert, I.Quisquater.(2003) New identity based signcryption schemes from pairings. IEEE Information Theory Workshop 2003. Paris, France, Available from http://eprint.iacr.org/2003/023. [25] Ma DaPeng, Huang IianHua.(2007) The elliptic curve cryptosystem and its security analysis. http://www.paper.edu.cn/ downloadpaper.php/serial-number=200707-432. [26] Huang BaoQing. The elliptic curve cryptosys-tem(ECC). http://www.hids.com.cn/ data.asp. [27] J.H. Silverman.(1986) The Arithmetic of Elliptic Curves. Graduate Texts in Math., vol.106, SpringerVerlag, Berlin, Heidelberg, New York, pp.130-136.