# An efficient and provable secure certificateless identification scheme in the standard model.

1. IntroductionIn traditional public key cryptography, a certificate authority is in charge of issuing certificates to users verifying that the public keys indeed belong to them. The down side of these certificates is that when the amount of users grows larger, the cost of managing these certificates increases as well. In identity-based cryptography, first proposed by Shamir in [1], a user can implicitly certify himself through the use of a unique identity-string binding him to his user secret key. However, the Trusted Authority who generates these keys still has access to the master secret key and therefore knows every user's secret. This key escrow, although desirable in certain situations, poses a security concern in others.

In the paradigm of certificateless cryptography, first proposed by Al-Riyami and Paterson in [2], the key generation center generates only a partial private key of the user. The user takes this partial secret key and combines it with a personal secret value to produce a full user secret key. This secret value is hidden from the key generation center and thus removes the key escrow. Identity-based cryptography also has the desired property of doing away with certificates, similar to certificateless cryptography. However, while there have been many advances in the realm of encryption and signature primitives for certificateless cryptography, the identification primitive has been virtually untouched.

An identification scheme allows a prover to prove himself to a verifier with the verifier learning nothing about the prover's secret key. Neven et al. in [3] and Kurosawa and Heng in [4] first pioneered the rigorous definition of identity-based identification, and their work has been incrementally improved upon over the most of the last decade in works such as [5-12]. However, to date little has been done to define and construct certificateless identification schemes. Some preliminary work has come in the form of [13] where the authors proposed a new and fairly effective scheme but without a proper definition of security models and proofs. [14] recently showed that the schemes in [13] are indeed insecure. A second but more comprehensive independent work has come in the form of [15] but the scheme is only provable secure in the random oracle model.

The random oracle model was first proposed by Bellare and Rogaway in [16]. Random oracles are treated as idealistic hash functions in a security proof where no mathematical parameters can be used to define the properties of random oracles. Open to honest and malicious parties alike, random oracles generate fully random responses to new queries while returning the same responses for queries that have been made before. However, since they are idealistic, random oracles cannot exist in the real world. In practice, regular hash functions are used to substitute these random oracles when implementing a cryptosystem. Canetti et al. in [17] showed that there are instances of cryptosystems where the cryptosystem can be broken if the random oracles are replaced by ordinary hash functions. Therefore it is our observation that while proofs of security in the random oracle model are better than having no proofs at all, it is more desirable to construct cryptosystems that are provable secure in the standard model.

In this paper, we provide the definitions of certificateless identification and proceed to construct a certificateless identification scheme that is efficient and provable secure in the standard model. This, as opposed to a proof in the random oracle model, is more desirable in rigorously defining security for a cryptosystem.

We divide our paper into the following sections: In Section 2 we introduce preliminary definitions required for certificateless identification schemes. In Section 3 we show the construction of our scheme. In Section 4 we provide four security proofs in the standard model--passive security against Type-1 and Type-2 adversaries, as well as active/concurrent security against Type-1 and Type-2 adversaries. In Section 5 we show the operation costs of the scheme and conclude in Section 6.

2. Preliminaries

2.1. Bilinear Pairings

Let [G.sub.1] and [G.sub.2] be cyclic multiplicative groups of prime order q where the discrete logarithm problems are intractable. Then e: [G.sub.1] x [G.sub.1] [right arrow] [G.sub.T] is an admissible bilinear map if it satisfies

1) Bilinearity: e([g.sup.a], [g.sup.b]) = e[(g, g).sup.ab] for all generators g [member of] G and a, b [member of] [Z.sup.*.sub.q]

2) Non-degenaracy: e(g, g) [not equal to] 1.

3) Computability: computation of the bilinear map e should be efficient.

2.2. Problems and Assumptions

We use the following hard problems to prove our certificateless identification scheme is secure:

a) Computational Diffie-Hellman problem (CDHP):Given g, [g.sup.a], [g.sup.b] for some a, b [member of] [Z.sup.*.sub.q], compute [g.sup.ab].

b) One-More computational Diffie-Hellman Problem (OMCDHP): The One-More Computational Diffie-Hellman Problem is modeled as a game played by an adversary where the adversary is given 1k, G, [G.sub.T], g, [g.sup.a] as input and access to two oracles CHALL and CDH. CHALL on any input returns a random point [W.sub.i], while CDH on any input h will return [h.sup.a]. The adversary is required to find [W.sup.a.sub.0], ..., [W.sup.a.sub.n] while using the CDH oracle only i < n times.

The OMCDHP was first proposed by [18] and subsequently used by [3] to prove security against impersonation under active/concurrent attacks for the pairing family schemes in their paper. Subsequent work utilized the one-more problems frequently to achieve active/concurrent level security for identification schemes.

The Computational Diffie-Hellman assumption and the One-More Computational Diffie-Hellman assumption state that there are no polynomial time algorithms for solving the discrete logarithm problem and the one-more discrete logarithm problems with non-negligible probability respectively.

2.3. The Knowledge of Exponent Assumption [19]

We use the Knowledge of Exponent Assumption for the proof against Type-1 adversaries, for the case when a target identity's public key is replaced. Let k = log [absolute value of <g>] be the security parameter of a prime order group where g is a generator. For any probabilistic polynomial time algorithm A that takes as input g and [g.sup.a], where a is chosen from [0, [absolute value of <g>] - 1] uniformly at random, and which produces as output a pair of the form (x, y), x [member of] (g), there exists a probabilistic polynomial time extractor E, which takes in the same input and outputs the pair (x, y) along with an exponent r such that for sufficiently large k, Pr[y = [x.sup.a] [conjunction] [g.sup.r] [not equal to] x] [less than or equal to] 1/[Q.sup.k] for any polynomial Q.

2.4. Definition for Certificateless Identification Schemes

A certificateless scheme consists of six probabilistic polynomial time algorithms (Setup, Set-User-Key, Partial-Private-Key-Extract, Set-Private-Key, Prove and Verify).

1) Setup is run by the key generation center. Taking in the security parameter [1.sup.k] as input, it returns the master public key MPK and the master secret key MSK. It publishes MPK and securely stores MSK.

2) Set-User-Key is run by the user when creating his own account. Taking in the security parameter [1.sup.k] and the user's identity ID as input, it generates the secret value for a user [SV.sub.ID] as well as a corresponding public key [UPK.sub.ID] which it publishes.

3) Partial-Private-Key-Extract is run by the key generation center upon a user's request for a partial private key. It takes in MPK, MSK, a user's identity ID and the user's public key [UPK.sub.ID]. It returns the partial private key [PPK.sub.ID] for the user via a secure channel.

4) Set-Private-Key is done by the user to combine the user's identity ID, partial private key [PPK.sub.ID], user public key [UPK.sub.ID] and secret value [SV.sub.ID] into the full private key. It returns the user private key as [USK.sub.ID].

5) Identification Protocol is the interactive protocol run by the 2 algorithms Prove and Verify. Both algorithms take in the master public key MPK, Prove's identity string ID, user public key [UPK.sub.ID]. Prove takes in the user private key [USK.sub.ID] as auxiliary input. They perform the three-step canonical honest verifier zero knowledge proof of knowledge protocol with the following steps:

(a) Commitment: Prove sends a commitment CMT to Verify.

(b) Challenge: Verify sends to Prove a challenge CHA randomly chosen from a predefined set.

(c) Response: Prove returns a response RSP where Verify will either choose to accept or reject.

2.5. Security Notion For Certificateless Identification Scheme

We consider four types of adversaries for the certificateless identification scheme:

1) The Type-1 passive impersonator (IMP-PA-1) and the active/concurrent impersonator (IMP-AA/CA-1) model malicious users attacking the scheme. Type-1 impersonators do not have access to the master secret key, but are able to request and replace public keys with values of their choosing.

2) The Type-2 passive impersonator (IMP-PA-2) and the active/concurrent impersonator (IMP-AA/CA-2) model malicious key generation centers attacking a particular user. Type-2 impersonators can generate partial private keys of users since they have access to the master secret key, and are able to replace public keys of users of their choice except the target user being attacked.

The difference in capability between passive and active impersonators is the passive impersonator can only eavesdrop on conversations between honest parties, while the active impersonator can act as a cheating verifier to gain knowledge from honest provers through interacting with them. The concurrent impersonator is an active impersonator who can run several instances of the protocol simultaneously.

We also classify adversary subtypes based on adversaries of certificateless signature schemes according to the definitions by [20,21]. These subtypes are the Normal, Strong and Super type adversary for Type 1 and Type 2 categories, which are differing in what parameters they have.

1) Normal-type adversaries cannot use a prover to converse with a verifier once its public key is replaced.

2) Strong-type adversaries can continue using a prover whose public key has been replaced, provided they supply the secret value corresponding to the replaced public key for the conversation.

3) Super-type adversaries can replace a prover's public key and still use it to correspond with a verifier without the new secret value.

The strength of these classifications are in increasing order, i.e. if a scheme is secure against super-type adversaries, it is secure against normal-type adversaries as well.

We describe the security model of CLI schemes against Type-1 and Type-2 impersonators in terms of the following games. We highlight the differences between each game with respect to the capabilities when making identification queries, for both passive and active/concurrent impersonators as well as Normal, Strong and Super adversaries.

Game I. The game played between a challenger C and the Type-1 impersonator [I.sub.1] for the CLI scheme is as follows:

1) Setup. C runs Setup, generates and passes the system parameters params to [I.sub.1] and keeps the master secret key MSK.

2) Phase 1: [I.sub.1] is allowed to make the following queries adaptively to C.

a) ExtrPartSK(ID). On request for the partial private key on user ID, C will run Partial-Private-Key-Extract and returns the user's partial private key [PPK.sub.ID] to [I.sub.1].

b) ExtrFullSK(ID). On request for the full private key on user ID, C will run Partial-Private-Key-Extract, Set-Secret-Value, Set-Private-Key algorithms to generate the user's full private key and pass it to [I.sub.1].

c) RequestPK(ID). On request for the user public key on user ID, C will run Set-User-Key to generate the user's public key [UPK.sub.ID] and pass it to [I.sub.1].

d) ReplacePK(ID,[UPK'.sub.ID]). [I.sub.1] will replace the user ID's public key [UPK.sub.ID] with the public key [UPK'.sub.ID] chosen by him. The corresponding secret value is not required for public key replacement queries.

e) Identification(ID). For passive [I.sub.1], C will generate a valid transcript between user ID and itself as the verifier and return the transcript to [I.sub.1]. For active/concurrent [I.sub.1], C will play the role of the prover to interact with [I.sub.1] as the cheating verifier.

i) Normal-type adversaries cannot make an identification query for a prover if its public key is replaced.

ii) Strong-type adversaries have to additionally supply sv which is the corresponding secret value for the public key. If sv = 1 then the user's public key is the original one. Otherwise C will use sv in the conversation for the replaced public key.

iii) Super-type adversaries can continue to make identification queries, even for replaced public keys, without supplying sv.

3) Phase 2. [I.sub.1] will eventually output the challenge identity ID* and then changes role to then play the role of the cheating prover. C, in turn, assumes the role of the verifier. [I.sub.1] wins the game if it manages to convince C to accept.

We say a CLI scheme is (t, [q.sub.I], [epsilon])-secure under passive or active/concurrent attacks if for any passive or active/concurrent Type-1 impersonator [I.sub.1] who runs in time t, Pr[[I.sub.1] can impersonate] < [epsilon], where [I.sub.1] can make at most [q.sub.I] extract queries on full private keys.

Game II. The game played between a challenger C and the Type-2 Impersonator [I.sub.2] for the CLI scheme is as follows:

1) Setup. C runs Setup and passes both the system parameters params and the master secret key MSK to [I.sub.2].

2) Phase 1: [I.sub.2] will be allowed to make the following queries adaptively to C.

a) ExtrFullSK(ID).On request for the full private key [USK.sub.ID] on user ID, C will run Partial-Private-Key-Extract, Set-Secret-Value, Set-Private-Key algorithms to generate the user's full private key. It passes the full private key to [I.sub.2].

b) RequestPK(ID). On request for the user public key on user ID, C will run Set-User-Key to generate the user's public key [UPK.sub.ID] and pass it to [I.sub.2].

c) ReplacePK(ID,[UPK'.sub.ID]). [I.sub.2] is able to replace the user ID's public key [UPK.sub.ID] with the public key [UPK'.sub.ID] chosen by him. Once again, the corresponding secret value is not required for public key replacement queries. The only exceptions are the targets ID and ID*, otherwise it will be trivial to win the game.

d) Identification(TD). For passive [I.sub.2], C will generate a valid transcript between user ID and itself as the verifier and return the transcript to [I.sub.2]. For active/concurrent [I.sub.2], C will play the role of the prover to interact with [I.sub.2] as the cheating verifier.

i) Normal-type adversaries cannot make an identification query for a prover if its public key is replaced.

ii) Strong-type adversaries have to additionally supply sv which is the corresponding secret value for the public key. If sv = [perpendicular to] then the public key is the original one. Otherwise C will use sv in the conversation for the replaced public key.

iii) Super-type adversaries can continue to make identification queries, even for replaced public keys, without supplying sv.

3) Phase 2. [I.sub.2] will eventually output the challenge identity, ID* and change roles to then play the role of the cheating prover. C will assume the role of the verifier. [I.sub.2] wins the game if it manages to convince C to accept.

Note that [I.sub.2] does not need to perform ExtrPartSK queries as it already has the master secret key and can generate partial private keys by itself. [I.sub.2] is also not allowed to replace the public key of the challenge identity, but is able to do so for any other user.

We say a CLI scheme is (t, [q.sub.1], [epsilon])-secure under passive or active/concurrent attacks if for any passive or active/concurrent Type-2 impersonator [I.sub.2] who runs in time t, Pr[[I.sub.2] can impersonate] < [epsilon], where [I.sub.2] can make at most [q.sub.I] extract queries on full private keys.

3. Construction

In this section we show the construction of the new certificateless identification scheme. Let G and [G.sub.T] be finite cyclic groups of large prime order q and let g be a generator of G. Use a collision-resistant hash function H: {0,1}* [right arrow] [(0,1}.sup.n] to hash identity strings of arbitrary length to size n.

1. Setup([1.sup.K]) : Select [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and an n -length vector <u> consisting of elements [u.sub.1], ..., [u.sub.n] [member of] G. Set [g.sub.1] = [g.sup.a] and publish master public key as mpk = <G, [G.sub.T], e, g, [g.sub.1], u', <u>, H>. The master secret key is msk = [g.sup.a.sub.2].

2. Set-User-Key([1.sup.k], mpk): Select [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and set [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

3. Partial-Private-Key-Extract(mpk, msk, ID, [upk.sub.ID]): Parse ID as an n-bit identity string with [d.sub.i] denoting the i-th bit of ID. Let ID = {1, ..., n} be the set of all i in which [d.sub.i] = 1. Define the Waters hash function as U = (u'[[product].sub.i[member of]ID][u.sub.i]). Select [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and construct the user partial private key as ppk = <[S.sub.ID], [R.sub.ID]> = <[g.sup.a.sub.2][([U.sub.ID]).sup.r], [UPK.sup.r.sub.1,ID]>.

4. Set-Private-Key(mpk, ID, [s.sub.ID], [upk.sub.ID], [ppk.sub.ID]):

First check if e([S.sub.ID], [UPK.sub.1,ID]) = e([g.sub.2], [UPK.sub.2,ID])e([U.sub.ID], [R.sub.ID]). This is according to the equation:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

If the partial private key is correct, then proceed to calculate [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

5. Identification protocol is run by Prover(mpk, ID, [upk.sub.ID], [usk.sub.ID]) and Verifier(mpk, ID, [upk.sub.ID]) as such:

a) Prover chooses a random [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], computes X = e[([U.sub.ID], [USK.sub.2,ID]).sup.z], Y = [g.sup.z.sub.2] and sends X, Y, [USK.sub.2,ID] to Verifier.

b) Verifier picks a random challenge [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and sends it to Prover.

c) Prover calculates Z = [USK.sup.z+c.sub.1,ID] and sends Z as a response to V.

V accepts if

1) e([g.sub.1], [UPK.sub.1,ID]) = e([UPK.sub.2,ID], g) and

2) e(Z, g) = e(Y[g.sup.c.sub.2], [UPK.sub.1,ID])Xe([XU.sup.c.sub.ID], [USK.sub.2,ID])

To check for completeness:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2)

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3)

4. Security Analysis

In this section, a security analysis on the certificateless identification scheme is presented. The scheme manages to achieve security against Super-Type-1 and Super-Type-2 adversaries for impersonation under passive attacks, and security against Strong-Type-1 and Strong-Type-2 adversaries for impersonation under active/concurrent attacks, all in the standard model.

4.1 Security Against Type-1 Impersonation under Passive Attacks

Theorem 1. The certificateless identification scheme is (t, [q.sub.1], [epsilon])-secure against Super-Type-1 impersonators under passive attack in the standard model if the CDHP is (t', [epsilon]')-hard where

t' = t + O([rho](2n([q.sub.e]) + [tau]([q.sub.I])), (2)

[epsilon] [less than or equal to] [square root of 4[q.sub.e](n + 1)[epsilon]'] + [q.sup.-1] (3)

where [rho] represents time taken to do a multiplication in G, t is the time taken to do an exponentiation in G, [q.sub.e] represents the number of extract queries made, [q.sub.i] represents the number of transcript queries made and [q.sub.I] = [q.sub.e] + [q.sub.i].

Proof Suppose there exists an impersonator [I.sub.1] who (t, [q.sub.I], [epsilon])-breaks the IBI scheme. Then we show an algorithm M which (t', [epsilon]')-breaks the CDH assumption by running [I.sub.1] as a subroutine. M is given a group G, a generator g [member of] G and elements [g.sup.a], [g.sup.b]. Without loss of generality, it can be assumed any ExtrPartSK, RequestPK, ExtrFullSK and Identification queries are preceded by a CreateUser query, while Identification and ExtrFullSK queries are preceded by a RequestPK query. M simulates the challenger for [I.sub.1] as follows:

1. Setup([1.sup.k]). Taking in the security parameter [1.sup.k], M sets l = 2[q.sub.e] and randomly chooses [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Assume that l(n + 1) < q for the given values of [q.sub.e] and n. Furthermore, M randomly chooses [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], a vector <X> of length n with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for all [iota], a randomly selected [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and a vector <y> of length n with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for all [iota]. Define the following functions:

F(ID) = x' + [summation over ([iota][member of]ID)][x.sub.[iota]] - lk (4)

J(ID) = y' + [summation over ([iota][member of]ID)][y.sub.l] (5)

M now sets [g.sub.1] = [g.sup.a] and [g.sub.2] = [g.sup.b]. M also sets u' = [g.sup.x'-lk.sub.2][g.sup.y'] and a vector <u> of length n consisting of n elements [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. M passes the system parameters mpk to [I.sub.1] as (G, [G.sub.T], e, g, [g.sub.1], [g.sub.2], u', <u>, H) but does not have the master secret key [g.sup.a.sub.2] = [g.sup.ab]. Note that with functions F(ID) and J(ID), we have:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (6)

2. CreateUser([ID.sub.i]) query: For any ExtrPartSK, RequestPK, ExtrFullSK and Identification query, M first checks if the user [ID.sub.i] is created. If not, M first selects [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], pre-computes [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and the public key components [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and sets a flag [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] denoting that the public key is still the original for [ID.sub.i]. M stores these values for future use.

3. ExtrPartSK([ID.sub.i]) query. When [I.sub.1] queries M for the partial private key of [ID.sub.i], M checks if F([ID.sub.i]) = 0 mod l and aborts if it is. This is because given the assumption l(n + 1) < q implies [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Therefore F([ID.sub.i]) = 0 mod q implies that F([ID.sub.i]) = 0 mod l and the simulator aborts because it is unable to construct the partial private key. Otherwise if F([ID.sub.i]) [not equal to] 0 mod l, M constructs the partial private key (by randomly selecting [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and computes the partial private key as: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

M returns [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

4. RequestPK([ID.sub.i]) query. M finds [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and returns it to [I.sub.1].

5. ExtrFullSK([ID.sub.i]) query. If F([ID.sub.i]) = 0 mod l then M aborts the simulation. Otherwise M returns [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to [I.sub.1].

6. ReplacePK([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) query. If the new public key satisfies e([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]), M then replaces [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Note that the new corresponding secret value is not required here.

7. Identification([ID.sub.i]) query. [I.sub.1] will act as a cheating verifier to learn information from valid conversation transcripts from M. M retrieves [ID.sub.i]'s stored details to construct the transcript. Once again, note that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is not necessary for passive attacks. M can create a valid transcript for each m-th query by picking [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (if not yet created) and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. M sets the transcript as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and passes the transcript to [I.sub.1] x [I.sub.1] can check that this is a valid transcript since:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (7)

Note that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is not needed by M even for replaced public keys for [ID.sub.i] while conducting Identification queries since the public keys need to hold for the verifier's first check equation [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. In other words, the new public values of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of all IDs must fulfill the check equation even with the replaced public keys, thus requiring [I.sub.1] to submit valid public key replacement values for ReplacePK queries.

Eventually [I.sub.1] stops phase 1 and outputs the challenge identity, ID*, on which it wishes to be challenged on. M checks if F([ID.sup.*]) = 0 mod q then reports failure and aborts if not. Otherwise M runs [I.sub.1] now as a cheating prover on ID*. M obtains (X, Y, R, [c.sub.1], [z.sub.1]) then resets [I.sub.1] to its previous state where it just sent its commitment to obtain (X, Y, R, [c.sub.2], [z.sub.2]). In both cases, it must hold that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for all public values of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Based on the Reset Lemma [22], M is then able to extract the full private key as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (8)

By using the knowledge of exponent assumption from [19], M can either extract [sigma] if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] were generated from g, [g.sup.a], or extract [??] if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] were generated from [g.sup.[sigma]], [g.sup.a[sigma]].

For the first case, M calculates the solution to the CDH problem as:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (9)

For the second case, M calculates the solution to the CDH problem as:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (10)

It remains to calculate the probability of M solving the CDH problem and winning the game.

The probability of M successfully extracting 2 valid transcripts from [I.sub.1] is given by [([epsilon] - 1/q).sup.2] as given by the Reset Lemma [21]. Upon extraction of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], M will be able to compute [g.sup.ab].

We break down the probability of M winning the CDHP to:

Pr[M wins CDHP] = Pr[M computes [g.sup.ab] [conjunction][logical not]abort] = Pr[M computes [g.sup.ab] |[logical not]Pr[[logical not]abort] [epsilon]' [greater than or equal to] [([epsilon] - [q.sup.-1]).sup.2]Pr[[logical not]abort] (11)

Finally, calculate Pr[[logical not]abort]. Define the following events:

1) Event [A.sub.i] where M answers all queries F([ID.sub.i]) [not equal to] 0 mod l and

2) Event [A.sup.*] where I outputs the challenge identity [ID.sup.*] where F(ID) = 0 mod q.

Calculate the probability of [A.sup.*] as:

Pr[[A.sup.*]] = Pr[F([ID.sup.*]) = 0 mod q [disjunction] F([ID.sup.*] = 0 mod l] = Pr[F([ID.sup.*]) = 0 mod l] Pr[F([ID.sup.*]) = 0 mod q | F([ID.sup.*]) = 0 mod l] = 1/l(1/n + 1) (12)

Notice that:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (13)

Since l = 2[q.sub.e] in the simulation, therefore

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (14)

Putting them together, the advantage of M in breaking CDHP is:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (15)

4.2 Security Against Type-1 Active/Concurrent Attacks

Theorem 1. The certificateless identification scheme is (t, [q.sub.1], [epsilon])-secure against Strong-Type-1 impersonators under active/concurrent attack in the standard model if the OMCDHP is (t", q", [epsilon]")-hard where

t' = t + 0([rho](2n([q.sub.e]) + [tau]([q.sub.I])), (16)

[epsilon][less than or equal to] [square root of 4[q.sub.e](n + 1)[epsilon]"] + [q.sup.-1] (17)

where [rho] represents time taken to do a multiplication in G, [tau] is the time taken to do an exponentiation in G, - [q.sub.e] represents the number of extract queries made, [q.sub.i] represents the number of transcript queries made and [q.sub.I] = [q.sub.e] + [q.sub.i].

Proof. Define the following as the impersonation under active/concurrent attack (IMP-AA/CA-1) game. Assume that if the certificateless identification scheme is (t, [q.sub.I], [epsilon]) -breakable by an impersonator [I.sub.1], then we can show a simulator M that (t", q", [epsilon]") -breaks the OMCDHP. M is given a challenge oracle CHALL which provides random points in [G.sub.1] and a solution oracle CDH that upon an input h outputs [h.sup.a]. In order to win the game, M has to provide the solutions to n queries to CHALL by using strictly less queries to CDH. To begin, M is given (g, [g.sup.1] = [g.sup.a]). M then queries CHALL for the initial challenge W0 and runs the Type-1 impersonator [I.sub.1] as a subroutine. Without loss of generality, it can be assumed any ExtrPartSK, RequestPK, ExtrFullSK and Identification queries are preceded by a CreateUser query, while Identification and ExtrFullSK queries are preceded by a RequestPK query. The way the environment is simulated for [I.sub.1] is similar to that of the IMP-PA-1 game, and hence only the differences are shown.

1. Setup([1.sup.k]) is similar to the one in the IMP-PA-1 game, except M sets [g.sub.2] = [W.sub.0] instead,

2. CreateUser([ID.sub.i]) query is similar to the one in the IMP-PA-1 game.

3. ExtrPartSK([ID.sub.i]) query is similar to the one in the IMP-PA-1 game.

4. RequestPK([ID.sub.i]) query is similar to the one in the IMP-PA-1 game.

5. ExtrFullSK([ID.sub.i]) query is similar to the one in the IMP-PA-1 game.

6. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] query is similar to the one in the IMP-PA-1 game.

7. Identification([ID.sub.i]) query. This is where the game differs significantly from that of the IMP-PA-1 game. Once again, [I.sub.1] will act as a cheating verifier to learn information, but this time by requesting a valid conversation with M. M retrieves [ID.sub.i]'s stored details to conduct the conversation. If <p = 0, M then requests the new secret value [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and the replaced public key [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] from [I.sub.1]. M starts with a counter m = 0 that is incremented every Identification query, then does the following:

i) M queries CHALL for a random [W.sub.m] and additionally chooses [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (if not yet created) and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and passes them as a commitment to to [I.sub.1].

ii) [I.sub.1] selects a random challenge [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and sends it back to M.

iii) M responds by querying [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and sends it to [I.sub.1]. One can check the validity of the second checking equation by:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (18)

Additionally the verifier's first check equation [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for public values of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of all IDs must hold even with the replaced public keys.

Eventually [I.sub.1] stops phase 1 and outputs the challenge identity, [ID.sup.*], on which it wishes to be challenged on. M checks if F (ID*) = 0 mod q then reports failure and aborts if not. Otherwise M runs [I.sub.1] now as a cheating prover on [ID.sup.*]. M obtains (X, Y, R, [c.sub.1], [z.sub.1]) then resets [I.sub.1] to its previous state where it just sent its commitment to obtain (X, Y, R, [c.sub.2], [z.sub.2]). In both cases, it must hold that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for all public values of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Based on the Reset Lemma [22], Mis then able to extract the full private key as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (19)

By using the knowledge of exponent assumption from [19], M can either extract [sigma] if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] were generated from g, [g.sup.a], or extract [??] if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] were generated from [g.sup.[sigma]], [g.sup.a[sigma]].

For the first case, M calculates the solution to the CDH problem as:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (20)

For the second case, M calculates the solution to the CDH problem as:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (21)

Recall that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is provided by [I.sub.1] for every m-th Identification query for the corresponding public key of [ID.sub.i] being used, both for original or replaced. M then proceeds to calculate the solutions for the challenges [W.sub.1], ..., [W.sub.m] as:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (22)

The probability of M winning the OMCDHP is the same as in the IMP-PA-1 game, except that [epsilon]', the advantage of M in solving the CDH problem is substituted with [epsilon]", the advantage of M in solving the OMCDHP game.

4.3 Security Against Type-2 Impersonation under Passive Attacks

Theorem 1. The certificateless identification scheme is (t, [q.sub.I], [epsilon])-secure against Strong-Type-2 impersonators under passive attack in the standard model if the CDHP is (t', [epsilon]')-hard where

t' = t + 0([rho](2n([q.sub.e]) + [tau]([q.sub.I])), (23)

[epsilon] [less than or equal to] [square root of 4[q.sub.e](n + 1)[epsilon]'] + [q.sup.-1] (24)

where [rho] represents time taken to do a multiplication in G, [tau] is the time taken to do an exponentiation in G, [q.sub.e] represents the number of extract queries made, [q.sub.i] represents the number of transcript queries made and [q.sub.I] = [q.sub.e] + [q.sub.i].

Proof Suppose there exists an impersonator [I.sub.2] who (t, [q.sub.I], [epsilon])-breaks the IBI scheme. Then we show an algorithm M which (t', [epsilon]')-breaks the CDH problem by running [I.sub.2] as a subroutine. M is given a group G, a generator g [member of] G and, to keep with the consistency of scheme definitions, elements defined as [g.sup.s], [g.sup.b]. Without loss of generality, it can be assumed any RequestPK, ExtrFullSK and Identification queries are preceded by a CreateUser query, while Identification and ExtrFullSK queries are preceded by a RequestPK query. M simulates the challenger for [I.sub.2] as follows:

1. Setup([1.sup.k]). Taking in the security parameter [1.sub.k], M sets l = 2[q.sub.e] and randomly chooses [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Assume that l(n + 1) < q for the given values of [q.sub.e] and n. Furthermore, M randomly chooses [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] a vector <X> of length n with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for all l, a randomly selected [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and a vector <y> of length n with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for all l. Define the following functions:

F(ID) = x' + [summation over ([iota][member of]ID)][x.sub.l] - lk (25)

J(ID) = y' + [summation over ([iota][member of]ID)][y.sub.l] (26)

M now selects [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], sets [g.sub.1] = [g.sup.a] and [g.sub.2] = [g.sup.b]. M also sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and a vector <u> of length n consisting of n elements [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. M passes the system parameters mpkto [I.sub.2] as (G, [G.sub.T], e, g, [g.sub.1], [g.sub.2], u', <u>, H> but does not have the master secret key [g.sup.a.sub.2] = [g.sup.ab]. Note that with functions F (ID) and J (ID), we have:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (27)

In Type-2 games, M knows the master secret key [g.sup.a.sub.2] = [g.sup.ab] and is able to create partial private keys, therefore ExtrPartSK queries are not necessary.

2. CreateUser([ID.sub.i]) query: For any RequestPK, ExtrFullSK and Identification query, M first checks if the user [ID.sub.i] is created. If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. If not, M first selects [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], pre-computes [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and the public key components [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and sets a flag [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] denoting that the public key is still the original for [ID.sub.i]. M stores these values for future use.

3. RequestPK([ID.sub.i]) query. M finds [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and returns it to [I.sub.2].

4. ExtrFullSK([ID.sub.i]) query. If F([ID.sub.i]) = 0 mod l then Maborts the simulation. Otherwise, M retrieves [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], selects [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and calculates [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. M returns [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to [I.sub.2].

5. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] query. For F([ID.sub.i]) [not equal to] 0 mod l, M checks if the new public key satisfies [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and replaces [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] if true. Note that the new corresponding secret value is not required here. Otherwise for F([ID.sub.i]) = 0 mod l, M replies with [perpendicular to] since [I.sub.2] is not allowed to replace the challenge identity's public key.

6. Identification([ID.sub.i]) query. [I.sub.2] will act as a cheating verifier to learn information from valid conversation transcripts from M. M retrieves [ID.sub.i]'s stored details to construct the transcript. For Strong-Type-2 attacks, [I.sub.2] needs to supply [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for replaced public keys. M can create a valid transcript for each of the following cases:

a) If F([ID.sub.i]) = 0 mod l, then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (if not yet created) and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], sets the transcript as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and passes the transcript to [I.sub.2] x [I.sub.2] can check that this is a valid transcript since:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (28)

b) If F([ID.sub.i]) [not equal to] 0 mod l, then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. For this case M can build the full private key for any user other than those with F([ID.sub.i]) = 0 mod l since it has access to the msk and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. If (p = 0 then M requests the new secret value [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. for the replaced public key from [I.sub.2]. M then constructs the transcript by picking [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII](if not yet created), [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and setting [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as the transcript. Once again, [I.sub.2] can check the second verifying equation:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (29)

Note that for both cases the public keys need to hold for the verifier's first check equation [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. In other words, the new public values of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of all IDs must fulfill the check equation even with the replaced public keys, thus requiring [I.sub.2] to submit valid public key replacement values for ReplacePK queries and a valid sv for Identification queries.

Eventually [I.sub.2] stops phase 1 and outputs the challenge identity, [ID.sup.*], on which it wishes to be challenged on. M checks if F (ID*) = 0 mod q then reports failure and aborts if not. Otherwise M runs [I.sub.2] now as a cheating prover on [ID.sup.*]. M obtains (X, Y, R, [c.sub.1], [z.sub.1]) then resets [I.sub.2] to its previous state where it just sent its commitment to obtain (X, Y, R, [c.sub.2], [z.sub.2]). In both cases, it must hold that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for all public values of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Based on the Reset Lemma [22], M is then able to extract the full private key as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (30)

Since [I.sub.2] is not allowed to replace the public key of [ID.sup.*], M calculates the solution to the CDH problem as:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (31)

For the second case, M calculates the solution to the CDH problem as:

It remains to calculate the probability of M solving the CDH problem and winning the game. The probability of M successfully extracting 2 valid transcripts from [I.sub.1] is given by [([epsilon] - 1/q).sup.2] as given by the Reset Lemma [21]. Upon extraction of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], M will be able to compute [g.sup.bs]. We break down the probability of M winning the CDHP to:

Pr[M wins CDHP] = Pr[M commutes [g.sup.bs] [conjunction][logical not]abort] = Pr[M commutes [g.sup.bs]|[logical not]abort]Pr[[logical not]abort] (32) [epsilon]' [greater than or equal to] [([epsilon - [q.sup.-1]).sup.2]Pr[[logical not]abort]

Finally, calculate Pr[[logical not]abort]. Define the following events:

3) Event [A.sub.i] where M answers all queries F([ID.sub.i]) [not equal to] 0 mod l and

4) Event [A.sup.*] where I outputs the challenge identity [ID.sup.*] where F(ID) = 0 mod q.

Calculate the probability of [A.sup.*] as:

Pr[[A.sup.*]] = Pr[F([ID.sup.*]) = 0 mod q [disjunction] F([ID.sup.*] = 0 mod l] = Pr[F([ID.sup.*]) = 0 mod l] Pr[F([ID.sup.*]) = 0 mod q | F([ID.sup.*]) = 0 mod l] = 1/l(1/n + 1) (33)

Notice that:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (34)

Since l = 2[q.sub.e] in the simulation, therefore

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (35)

Putting them together, the advantage of M in breaking CDHP is:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (36)

4.4 Security Against Type-2 Active/Concurrent Attacks

Theorem 1. The certificateless identification scheme is (t, [q.sub.I], [epsilon]) -secure against Strong-Type-2 impersonators under active/concurrent attack in the standard model if the OMCDHP is (t", q", [epsilon]")-hard where

t' = t + 0([rho]{2n([q.sub.e]) + [tau]([q.sub.I])), (37)

[epsilon] [less than or equal to] [square root of 4[q.sub.e](n + 1)[epsilon]" + [q.sup.-1]] (38)

where [rho] represents time taken to do a multiplication in G, t is the time taken to do an exponentiation in G, [q.sub.e] represents the number of extract queries made, qt represents the number of transcript queries made and [q.sub.I] = [q.sub.e] + [q.sub.i].

Proof. Define the following game as the impersonation under active/concurrent attack (IMP-AA/CA-2) game. Assume that the certificateless identification scheme is (t, [q.sub.I], [epsilon]) -breakable by an impersonator [I.sub.2], then we can show a simulator M that (t", q", [epsilon]") -breaks the OMCDHP. M is given a challenge oracle CHALL which provides random points in [G.sub.1] and a solution oracle CDH that upon input h outputs [h.sup.a]. M has to provide the solutions to n queries to CHALL by using strictly less queries to CDH in order to win the game. To begin, M is given (g, [g.sub.1] = [g.sup.a]). M then queries CHALL for the initial challenge [W.sub.0] and runs the Type-2 impersonator [I.sub.2] as a subroutine. Without loss of generality, it can be assumed any RequestPK, ExtrFullSK and Identification queries are preceded by a CreateUser query, while Identification and ExtrFullSK queries are preceded by a RequestPK query. The way the environment is simulated for [I.sub.2] is similar to that of the IMP-PA-2 game, and hence only the differences are shown.

1. Setup([1.sup.k]) is similar to the one in the IMP-PA-2 game.

2. CreateUser([ID.sub.i]) query is similar to the one in the IMP-PA-2 game, except for F([ID.sub.i]) = 0 mod l, M [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] instead.

3. RequestPK([ID.sub.i]) query is similar to the one in the IMP-PA-2 game.

4. ExtrFullSK([ID.sub.i]) query is similar to the one in the IMP-PA-2 game.

5. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] query is similar to the one in the IMP-PA-2 game.

6. Identification([ID.sub.i]) query. This is where the game differs significantly from the one in the IMP-PA-2 game. Once again, [I.sub.2] will act as a cheating verifier but this time by requesting a valid conversation with M. M retrieves [ID.sub.i]'s stored details to conduct the conversation. There are two cases to consider:

a) If F([ID.sub.i]) = 0 mod l, then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. M starts with a counter m = 0 that is incremented every Identification query for F([ID.sub.i]) = 0 mod l, then does the following:

i) M queries CHALL for a random [W.sub.m] and additionally chooses [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (if not yet created) and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and passes them as a commitment to to [I.sub.2].

ii) [I.sub.2] selects a random challenge [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and sends it back to M.

iii) M responds by querying [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and sends it to [I.sub.2]x [I.sub.2] can check the validity of the second checking equation by:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (39)

b) If F([ID.sub.i]) = 0 mod l, then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. If p = 0 then M requests the new secret value [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and the replaced public key [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. from [I.sub.2], otherwise M just retrieves the original [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. value. Since M can then construct the full [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], M just builds [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and uses it to run the Identification query. For both cases of [phi], the check equation [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] must hold.

Eventually [I.sub.2] stops phase 1 and outputs the challenge identity, [ID.sup.*], on which it wishes to be challenged on. M checks if F([ID.sup.*]) = 0 mod q then reports failure and aborts if not. Otherwise M runs 12 now as a cheating prover on [ID.sup.*]. M obtains (X, Y, R, [c.sub.1], [z.sub.1]) then resets [I.sub.2] to its previous state where it just sent its commitment to obtain (X, Y, R, [c.sub.2], [z.sub.2]). In both cases, it must hold that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for all public values of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of [ID.sup.*]. Based on the Reset Lemma [22], M is then able to extract the full private key as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (40)

Since [I.sub.2] is not allowed to replace the public key of [ID.sup.*], M calculates the solution to the OMCDHP as:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (41)

M then proceeds to calculate the solutions for the challenges [W.sub.1], ..., [W.sub.m] as:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (42)

The probability of M winning the OMCDHP is the same as IMP-PA-2 game, except that [epsilon]', the advantage of M in solving the CDH problem is substituted with [epsilon]", the advantage of M in solving the OMCDHP game.

5. Efficiency Analysis

We give the operational cost of the certificateless identification scheme in Table 1.

Since the certificateless identification scheme is constructed based on an extension of the identity-based identification scheme from [23] to the certificateless setting, similar pre-computations are able to be conducted in order to reduce operation costs.

One can pre-compute the value of [??] = e([U.sub.ID], [USK.sub.2,ID]) beforehand, since this value is fixed, then calculate X = [[??].sup.z] for Prover each time the protocol is run. This will reduce up to n + 1 times of multiplication in [G.sub.1] for both Prover and Verifier, and one pairing operation on Prover.

Another pre-computation operation available is to pre-compute and store U = (u'[[Pi].sub.[iota][member of]ID][u.sub.[iota]]) within Prover. This can later be sent as part of the commitment to Verifier so that Verifier does not require a second calculation. This saves another n + 1 multiplications in [G.sub.1] for Verifier.

The operation costs of Prover and Verifier with pre-computation is given in Table 2.

6. Conclusion

In this paper, we proposed a certificateless identification scheme with provable security in the standard model. This scheme provides a stronger security guarantee due to its non-reliance on the existence of random oracles. It is also the first ceritficateless identification scheme to have provable security in the standard model. The scheme is provable secure against both Type-1 and Type-2 impersonators, both passive and active/concurrent alike assuming the CDHP and OMCDHP is hard. It is secure against Super-Type-1 and Strong-Type-2 adversaries with regard to passive adversaries and secure against Strong-Type-1 and Strong-Type-2 adversaries with regard to active/concurrent security.

One interesting problem is to increase the security even more to propose a certificateless identification scheme provable secure in the standard model against Super-Type adversaries for active/concurrent attacks. Another direction the research on certificateless identification can take is to apply formal methods for proving certificateless identification schemes secure.

http://dx.doi.org/10.3837/tiis.2014.07.019

Received November 8, 2013; revised April 8, 2014; accepted June 5, 2014; published July 29, 2014

Acknowledgement

The authors would like to thank Ministry of Higher Education for aiding this research financially through the Exploratory Research Grant Scheme (ERGS/1/2011/PK/MMU/03/1) and the Fundamental Research Grant Scheme (FRGS/2/2013/ICT07/MMU/03/5). We also thank the anonymous reviewers for their kind comments.

References

[1] Shamir, A.. "Identity-based cryptosystems and signature schemes," Advances in cryptology, Springer Berlin Heidelberg, pp. 47-53, January, 1985. Article (CrossRef Link)

[2] Al-Riyami, S. S., & Paterson, K. G., "Certificateless public key cryptography," Advances in Cryptology-ASIACRYPT2003, Springer Berlin Heidelberg, pp. 452-473, 2003. Article (CrossRef Link)

[3] Bellare, M., Namprempre, C., & Neven, G., "Security proofs for identity-based identification and signature schemes," Journal of Cryptology, 22(1), 1-61, 2009. Article (CrossRef Link)

[4] Kurosawa, K., & Heng, S. H., "From digital signature to ID-based identification/signature" Public Key Cryptography-PKC 2004, Springer Berlin Heidelberg, pp. 248-261, 2004. Article (CrossRef Link)

[5] Kurosawa, K., & Heng, S. H., "Identity-based identification without random oracles," Computational Science and Its Applications-ICCSA 2005, Springer Berlin Heidelberg, pp. 603-613, 2005. Article (CrossRef Link)

[6] Kurosawa, K., & Heng, S. H., "The power of identification schemes," Public Key Cryptography-PKC 2006, Springer Berlin Heidelberg, pp. 364-377, 2006. Article (CrossRef Link)

[7] Yang, G., Chen, J., Wong, D. S., Deng, X., & Wang, D., "A new framework for the design and analysis of identity-based identification schemes," Theoretical Computer Science, 407(1), 370-388, 2008. Article (CrossRef Link)

[8] Chin, J. J., Heng, S. H., & Goi, B. M., "An efficient and provable secure identity-based identification scheme in the standard model," Public Key Infrastructure, Springer Berlin Heidelberg, pp. 60-73, 2008. Article (CrossRef Link)

[9] Chin, J. J., Heng, S. H., & Goi, B. M., "Hierarchical identity-based identification schemes," Security Technology, Springer Berlin Heidelberg, pp. 93-99, 2009. Article (CrossRef Link)

[10] Thorncharoensri, P., Susilo, W., & Mu, Y., "Identity-based identification scheme secure against concurrent-reset attacks without random oracles," Information Security Applications, Springer Berlin Heidelberg, pp. 94-108, 2009. Article (CrossRef Link)

[11] Fujioka, A., Saito, T., & Xagawa, K., "Security enhancements by OR-proof in identity-based identification," Applied Cryptography and Network Security, Springer Berlin Heidelberg, pp. 135-152, January, 2012. Article (CrossRef Link)

[12] Fujioka, A., Saito, T., & Xagawa, K., "Security enhancement of identity-based identification with reversibility," Information and Communications Security, Springer Berlin Heidelberg, pp. 202-213, 2012. Article (CrossRef Link)

[13] Dehkordi, M. H., & Alimoradi, R., "Certificateless identification protocols from super singular elliptic curve," Security and Communication Networks, 2013. Article (CrossRef Link)

[14] Chin, J. J., Behnia, R., Heng, S. H. and Phan, R. P. C., "Cryptanalysis of a certificateless identification scheme," Security and Communication Networks, 2014. Article (CrossRef Link)

[15] Chin, J. J., Heng, S. H., Phan, R. P. C & Behnia, R., "An Efficient and Provably Secure Certificateless Identification Scheme," in Proc. of Proceedings of the 10th International Conference on Security and Cryptography, SECRYPT, pp. 371-378, 2013.

[16] Bellare, M., & Rogaway, P., "Random oracles are practical: A paradigm for designing efficient protocols," in Proc. of Proceedings of the 1st ACM conference on Computer and communications security, ACM, pp. 62-73, December, 1993. Article (CrossRef Link)

[17] Canetti, R., Goldreich, O., & Halevi, S., "The random oracle methodology, revisited," Journal of the ACM (JACM), 51(4), 557-594, 2004. Article (CrossRef Link)

[18] Boldyreva, A., "Threshold signatures, multisignatures and blind signatures based on the gap-Diffie-Hellman-group signature scheme," Public key cryptography--PKC 2003, Springer Berlin Heidelberg, pp. 31-46. 2002. Article (CrossRef Link)

[19] Damgard, I., "Towards practical public key systems secure against chosen ciphertext attacks," Advances in Cryptology--CRYPTO'91, Springer Berlin Heidelberg, pp. 445-456, January, 1992. Article (CrossRef Link)

[20] Huang, X., Mu, Y., Susilo, W., Wong, D. S., & Wu, W., "Certificateless signature revisited," Information Security and Privacy, Springer Berlin Heidelberg, pp. 308-322, January, 2007. Article (CrossRef Link)

[21] Huang, X., Mu, Y., Susilo, W., Wong, D. S., & Wu, W., "Certificateless signatures: new schemes and security models," The Computer Journal, 55(4), 457-474, 2012. Article (CrossRef Link)

[22] Bellare, M., & Palacio, A., "GQ and Schnorr identification schemes: Proofs of security against impersonation under active/concurrent attacks," Advances in Cryptology--CRYPTO 2002, Springer Berlin Heidelberg, pp. 162-177, 2002. Article (CrossRef Link)

[23] Tan, S. Y., Chin, J. J., Heng, S. H., & Goi, B. M., "An improved efficient provable secure identity-Based identification scheme in the standard model," KSII Transactions on Internet and Information Systems (TIIS), 7(4), 910-922, 2013.

Ji-Jian Chin (1), Swee-Huay Heng (2) and Raphael C.-W. Phan (1)

(1) Faculty of Engineering, Multimedia University, Cyberjaya, Selangor, Malaysia

(2) Faculty of Information Science and Technology, Multimedia University, Melaka, Malaysia

[{e-mail: jjchin,shheng,raphael}@mmu.edu.my]

* Corresponding author: Ji-Jian Chin

Ji-Jian Chin received his Bachelor of Science majoring in Computer Science and Computational Mathematics from Campbell University and his Master of Engineering Science from Multimedia University. He is currently is a PhD student at the Faculty of Information Science and Technology, Multimedia University while also teaching at t he Faculty of Engineering, Multimedia University. His research interest is in cryptography, particularly in the area of public key cryptography.

Swee-Huay Heng received her B.Sc (Hons) and M.Sc degrees from University Putra Malaysia (UPM), and her Doctor of Engineering degree from the Tokyo Institute of Technology, Japan. She is currently the Dean and a Professor in the Faculty of Information Science and Technology, Multimedia University, Malaysia. Her research interests include Cryptography and Information Security. She was the Programme Chair of ProvSec 2010 and CANS 2010. She has been actively involved in technical Programme Committees of several international security conferences.

Raphael Phan received his B.Eng (Hons), M.Eng.Sc, and PhD degrees from Multi media University and currently holds a professor position at the Faculty of Engineering, Multimedia University. Each year he serves in numerous technical Program Committees of international security conferences. He researches on diverse security and privacy topics ranging from cryptology to human-involved processes.

Table 1. Operation Costs for the Certificateless Identification Scheme Algorithm Multiplication Exponentiation Multiplication in [G.sub.1] in [G.sub.1] in [G.sub.2] Setup 0 2 0 Set-User-Key 0 2 0 PPK-Extract n + 2 3 0 Set-Priv-Key n + 1 1 1 Prover n + 1 2 0 Verifier n + 2 2 2 Algorithm Exponentiation Pairing in [G.sub.2] Setup 0 0 Set-User-Key 0 0 PPK-Extract 0 0 Set-Priv-Key 0 3 Prover 1 1 Verifier 0 5 Table 2. Operation Costs for the Identification Protocol with Pre-computation Algorithm Multiplication Exponentiation Multiplication in [G.sub.1] in [G.sub.1] in [G.sub.1] Prover 0 2 0 Verifier 1 2 2 Algorithm Exponentiation Pairing in [G.sub.1] Prover 1 0 Verifier 0 5

Printer friendly Cite/link Email Feedback | |

Author: | Chin, Ji-Jian; Heng, Swee-Huay; Phan, Raphael C.-W. |
---|---|

Publication: | KSII Transactions on Internet and Information Systems |

Article Type: | Report |

Date: | Jul 1, 2014 |

Words: | 9637 |

Previous Article: | Defending HTTP web servers against DDoS attacks through busy period-based attack flow detection. |

Next Article: | Provably secure certificate-based signcryption scheme without pairings. |

Topics: |