In Asiacrypt 2003, AlRiyami and Paterson proposed the notion of certificateless cryptography, a technique to remove key escrow from traditional identitybased cryptography as well as circumvent the certificate management problem of traditional public key cryptography. Subsequently much research has been done in the realm of certificateless encryption and signature schemes, but little to no work has been done for the identification primitive until 2013 when Chin et al. rigorously defined certificateless identification and proposed a concrete scheme. However Chin et al.’s scheme was proven in the random oracle model and Canetti et al. has shown that certain schemes provable secure in the random oracle model can be insecure when random oracles are replaced with actual hash functions. Therefore while having a proof in the random oracle model is better than having no proof at all, a scheme to be proven in the standard model would provide stronger security guarantees. In this paper, we propose the first certificateless identification scheme that is both efficient and show our proof of security in the standard model, that is without having to assume random oracles exist.
1. Introduction
I
n 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 identitybased cryptography, first proposed by Shamir in
[1]
, a user can implicitly certify himself through the use of a unique identitystring 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 AlRiyami 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. Identitybased 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 identitybased 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 Type1 and Type2 adversaries, as well as active/concurrent security against Type1 and Type2 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
_{1}
and
G
_{2}
be cyclic multiplicative groups of prime order
q
where the discrete logarithm problems are intractable. Then
e
:
G
_{1}
×
G
_{1}
→
G_{T}
is an admissible bilinear map if it satisfies

1) Bilinearity:e(ga, gb) =e(g, g)abfor all generatorsg∈Ganda, b∈Z*q

2) Nondegenaracy:e(g, g) ≠ 1.

3) Computability: computation of the bilinear mapeshould be efficient.
 2.2. Problems and Assumptions
We use the following hard problems to prove our certificateless identification scheme is secure

a) Computational DiffieHellman problem (CDHP):Giveng, ga, gbfor somea, b∈Z*q, computegab.

b) OneMore computational DiffieHellman Problem (OMCDHP): The OneMore Computational DiffieHellman Problem is modeled as a game played by an adversary where the adversary is given 1k, G, GT, g, gaas input and access to two oraclesCHALLandCDH.CHALLon any input returns a random pointWi, whileCDHon any inputhwill returnha. The adversary is required to findW0a,…,Wnawhile using theCDHoracle onlyi

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 onemore problems frequently to achieve active/concurrent level security for identification schemes.
The Computational DiffieHellman assumption and the OneMore Computational DiffieHellman assumption state that there are no polynomial time algorithms for solving the discrete logarithm problem and the onemore discrete logarithm problems with nonnegligible probability respectively.
 2.3. The Knowledge of Exponent Assumption[19]
We use the Knowledge of Exponent Assumption for the proof against Type1 adversaries, for the case when a target identity’s public key is replaced. Let
k
= log〈
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^{a}
, where
a
is chosen from [0,〈
g
〉  1] uniformly at random, and which produces as output a pair of the form (
x, y
)
, x
∈〈
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^{a}
∧
g^{r}
≠
x
] ≤
for any polynomial
Q
.
 2.4. Definition for Certificateless Identification Schemes
A certificateless scheme consists of six probabilistic polynomial time algorithms
(Setup, SetUserKey, PartialPrivateKeyExtract, SetPrivateKey, Prove and Verify)
.

1)Setupis run by the key generation center. Taking in the security parameter 1kas input, it returns the master public keyMPKand the master secret keyMSK. It publishesMPKand securely storesMSK.

2)SetUserKeyis run by the user when creating his own account. Taking in the security parameter 1kand the user's identityIDas input, it generates the secret value for a userSVIDas well as a corresponding public keyUPKIDwhich it publishes.

3)PartialPrivateKeyExtractis run by the key generation center upon a user's request for a partial private key. It takes inMPK,MSK, a user's identityIDand the user's public keyUPKIDIt returns the partial private keyPPKIDfor the user via a secure channel.

4)SetPrivateKeyis done by the user to combine the user's identityID, partial private keyPPKID, user public keyUPKIDand secret valueSVIDinto the full private key. It returns the user private key asUSKID.

5)Identification Protocolis the interactive protocol run by the 2 algorithmsProveandVerify. Both algorithms take in the master public keyMPK,Prove's identity stringID, user public keyUPKID.Provetakes in the user private keyUSKIDas auxiliary input. They perform the threesteρ canonical honest verifier zero knowledge proof of knowledge protocol with the following steps:

(a) Commitment:Provesends a commitmentCMTtoVerify.

(b) Challenge:Verifysends toProvea challengeCHArandomly chosen from a predefined set.

(c) Response:Provereturns a responseRSPwhereVerifywill 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 Type1 passive impersonator (IMPPA1) and the active/concurrent impersonator (IMPAA/CA1) model malicious users attacking the scheme. Type1 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 Type2 passive impersonator (IMPPA2) and the active/concurrent impersonator (IMPAA/CA2) model malicious key generation centers attacking a particular user. Type2 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 eavesdroρ 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)Normaltype adversaries cannot use a prover to converse with a verifier once its public key is replaced.

2)Strongtype 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)Supertype 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 supertype adversaries, it is secure against normaltype adversaries as well.
We describe the security model of CLI schemes against Type1 and Type2 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 Type1 impersonator
I
_{1}
for the CLI scheme is as follows:

1)Setup.CrunsSetup, generates and passes the system parametersparamstoI1and keeps the master secret keyMSK.

2) Phase 1:I1is allowed to make the following queries adaptively toC.

a)ExtrPartSK(ID). On request for the partial private key on userID,Cwill runPartialPrivateKeyExtractand returns the user's partial private keyPPKIDtoI1.

b)ExtrFullSK(ID). On request for the full private key on userID,Cwill runPartialPrivateKeyExtract, SetSecretValue,SetPrivateKeyalgorithms to generate the user's full private key and pass it toI1.

c)RequestPK(ID). On request for the user public key on userID,Cwill runSetUserKeyto generate the user's public keyUPKIDand pass it toI1.

d)ReplacePK(ID,UPK’ID).I1will replace the userID's public keyUPKIDwith the public keyUPK’IDchosen by him. The corresponding secret value is not required for public key replacement queries.

e)Identification(ID). For passiveI1,Cwill generate a valid transcript between userIDand itself as the verifier and return the transcript toI1. For active/concurrentI1,Cwill play the role of the prover to interact withI1as the cheating verifier.

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

ii)Strongtype adversaries have to additionally supplysvwhich is the corresponding secret value for the public key. Ifsv= ⊥ then the user’s public key is the original one. OtherwiseCwill usesvin the conversation for the replaced public key.

iii)Supertype adversaries can continue to make identification queries, even for replaced public keys, without supplyingsv.
3)
Phase 2
.
I
_{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
_{1}
wins the game if it manages to convince
C
to accept.
We say a CLI scheme is (
t, q_{I}, ε
)secure under passive or active/concurrent attacks if for any passive or active/concurrent Type1 impersonator
I
_{1}
who runs in time
t
, Pr [
I
_{1}
can impersonate
] <
ε
, where
I
_{1}
can make at most
q_{I}
extract queries on full private keys.
Game II
. The game played between a challenger
C
and the Type2 Impersonator
I
_{2}
for the CLI scheme is as follows:

1)Setup.CrunsSetupand passes both the system parametersparamsand the master secret keyMSKtoI2.

2)Phase 1:I2will be allowed to make the following queries adaptively toC.

a)ExtrFullSK(ID).On request for the full private keyUSKIDon userID,Cwill runPartialPrivateKeyExtract,SetSecretValue,SetPrivateKeyalgorithms to generate the user's full private key. It passes the full private key toI2.

b)RequestPK(ID). On request for the user public key on userID,Cwill runSetUserKeyto generate the user's public keyUPKIDand pass it toI2.

c)ReplacePK(ID,UPK′ID).I2is able to replace the userID's public keyUPKIDwith the public keyUPK′IDchosen by him. Once again, the corresponding secret value is not required for public key replacement queries. The only exceptions are the targetsIDandID*, otherwise it will be trivial to win the game.

d)Identification(ID). For passiveI2,Cwill generate a valid transcript between userIDand itself as the verifier and return the transcript toI2. For active/concurrentI2,Cwill play the role of the prover to interact withI2as the cheating verifier.

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

ii)Strongtype adversaries have to additionally supplysvwhich is the corresponding secret value for the public key. Ifsv= ⊥ then the public key is the original one. OtherwiseCwill usesvin the conversation for the replaced public key.

iii)Supertype adversaries can continue to make identification queries, even for replaced public keys, without supplyingsv.

3)Phase 2.I2will eventually output the challenge identity,ID* and change roles to then play the role of the cheating prover.Cwill assume the role of the verifier.I2wins the game if it manages to convinceCto accept.
Note that
I
_{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
_{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_{I}, ε
)secure under passive or active/concurrent attacks if for any passive or active/concurrent Type2 impersonator
I
_{2}
who runs in time
t
, Pr [
I
_{2}
can impersonate
] <
ε
, where
I
_{2}
can make at most
q_{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_{T}
be finite cyclic groups of large prime order
q
and let
g
be a generator of
G
. Use a collisionresistant hash function
H
:{0,1}* → {0,1}
^{n}
to hash identity strings of arbitrary length to size
n
.

1.Setup(1k): SelectaZq,g2,u'Gand annlength vector 〈u〉 consisting of elementsu1,…,un∈G. Setg1=gaand publish master public key asmpk=〈G, GT, e, g, g1, u',〈u〉,H〉. The master secret key is

2.SetUserKey(1k,mpk): SelectsIDZqand setupkID=〈UPK1,ID,UPK2,ID〉=

3.PartialPrivateKeyExtract(mpk,msk,ID,upkID): ParseIDas annbit identity string withdidenoting theith bit ofID. LetID= {1,…,n} be the set of alliin whichdi= 1. Define the Waters hash function asU= (u'Πi∈IDui). SelectrZqand construct the user partial private key as

4. SetPrivateKey(mpk, ID, sID, upkID, ppkID):

First check ife(SID, UPK1,ID) =e(g2, UPK2,ID)e(UID, RID). This is according to the equation:

If the partial private key is correct, then proceed to calculateusk=〈USK1,ID=, USK2,ID=RID〉

5.Identification protocolis run byProver(mpk, ID, upkID, uskID)andVerifier(mpk, ID, upkID) as such:

a) Proverchooses a randomzZq, computesX=e(UID,USK2,ID)z,and sendsX, Y, USK2,IDtoVerifier.

b) Verifierpicks a random challengecZqand sends it toProver.

c) Provercalculatesand sendsZas a response toV.

Vaccepts if

1)e(g1, USK1,ID) =e(USK2,ID, g) and

2)
To check for completeness:
and
4. Security Analysis
In this section, a security analysis on the certificateless identification scheme is presented. The scheme manages to achieve security against SuperType1 and SuperType2 adversaries for impersonation under passive attacks, and security against StrongType1 and StrongType2 adversaries for impersonation under active/concurrent attacks, all in the standard model.
 4.1 Security Against Type1 Impersonation under Passive Attacks
Theorem 1.
The certificateless identification scheme is
(
t, q_{I}, ε
)
secure against SuperType1 impersonators under passive attack in the standard model if the CDHP is
(
t', ε'
)
hard where
where ρ represents time taken to do a multiplication in G, τ is the time taken to do an exponentiation in G, q_{e} represents the number of extract queries made, q_{i} represents the number of transcript queries made and q_{I}
=
q_{e}
+
q_{i}
.
Proof
. Suppose there exists an impersonator
I
_{1}
who (
t, q_{I}, ε
)breaks the IBI scheme. Then we show an algorithm
M
which (
t', ε'
)breaks the
CDH
assumption by running
I
_{1}
as a subroutine.
M
is given a group
G
, a generator
g
∈
G
and elements
g^{a}
,
g^{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
_{1}
as follows:

1.Setup(1k).Taking in the security parameter 1k,Msetsl= 2qeand randomly chooseskZn. Assume thatl(n+ 1)

Mnow setsg1=gaandg2=gb.Malso setsand a vector 〈u〉 of lengthnconsisting ofnelementsMpasses the system parametersmpktoI1as 〈G, GT, e, g, g1, g2, u',〈u〉, H〉 but does not have the master secret key. Note that with functionsF(ID) andJ(ID), we have:

2.CreateUser(IDi) query:For anyExtrPartSK,RequestPK,ExtrFullSKandIdentificationquery,Mfirst checks if the userIDiis created. If not,Mfirst selectssIDiZq, precomputesand the public key componentsand sets a flagφIDi= 1 denoting that the public key is still the original forIDi.Mstores these values for future use.

3.ExtrPartSK(IDi) query.WhenI1queriesMfor the partial private key ofIDi,Mchecks ifF(IDi) = 0mod land aborts if it is. This is because given the assumptionl(n+1)

M returnstoI1.

4.RequestPK(IDi) query.MfindsupkIDi=〈UPK1,IDi, UPK2,IDi〉 and returns it toI1.

5.ExtrFullSK(IDi) query. IfF(IDi) = 0mod lthenMaborts the simulation. OtherwiseMreturnstoI1.

6.ReplacePK(IDi, upk'IDi= 〈UPK'1,IDi, UPK'2,IDi) query.If the new public key satisfiese(g1, UPK'1,IDi) =e(UPK'2,IDi, g),Mthen replaces 〈UPK1,IDi, UPK2,IDi〉 with 〈UPK1,IDi, UPK2,IDi〉 and setsφIDi= 0. Note that the new corresponding secret value is not required here.

7.Identification(IDi) query.I1will act as a cheating verifier to learn information from valid conversation transcripts fromM.MretrievesIDi’s stored details to construct the transcript. Once again, note thatsv=sIDiis not necessary for passive attacks.Mcan create a valid transcript for eachmth query by pickingrIDiZq(if not yet created) andcm, zmZq.Msets the transcript as=e(UIDi,RIDi)zm,and passes the transcript toI1.I1can check that this is a valid transcript since:

Note thatsIDiis not needed byMeven for replaced public keys forIDiwhile conductingIdentificationqueries since the public keys need to hold for the verifier’s first check equatione(g1, UPK1,IDi) =e(UPK2,IDi, g). In other words, the new public values ofUPK'1,IDi, UPK'2,IDiof allIDs must fulfill the check equation even with the replaced public keys, thus requiringI1to submit valid public key replacement values forReplacePKqueries.
Eventually
I
_{1}
stops phase 1 and outputs the challenge identity,
ID
*, 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
_{1}
now as a cheating prover on
ID
*.
M
obtains (
X, Y, R, c
_{1}
, z
_{1}
) then resets
I
_{1}
to its previous state where it just sent its commitment to obtain (
X, Y, R, c
_{2}
, z
_{2}
). In both cases, it must hold that
e
(
g
_{1}
, UPK
_{1,ID*}
) =
e
(
UPK
_{2,ID*}
, g
) for all public values of
, UPK
_{1,ID*}
, UPK
_{2,ID*}
of
ID
*. Based on the Reset Lemma
[22]
,
M
is then able to extract the full private key as
By using the knowledge of exponent assumption from
[19]
,
M
can either extract
σ
if 〈
UPK
_{1,ID*}
, UPK
_{2,ID*}
〉 = 〈
g^{σ}, g^{aσ}
〉 were generated from
g, g^{a}
, or extract
ϱ
if 〈
UPK
_{1,ID*}
, UPK
_{2,ID*}
〉 = 〈
g^{σϱ}, g^{aσϱ}
〉 were generated from
g^{σ}, g^{aσ}
.
For the first case,
M
calculates the solution to the CDH problem as:
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
_{1}
is given by
as given by the Reset Lemma
[21]
. Upon extraction of
USK
_{1,ID*}
,
M
will be able to compute
g^{ab}
.
We break down the probability of
M
winning the CDHP to:
Finally, calculate Pr [¬
abort
]. Define the following events:

1) EventAiwhereManswers all queriesF(IDi) ≠ 0mod land

2) EventA* whereIoutputs the challenge identityID* whereF(ID) = 0mod q.
Calculate the probability of
A
* as:
Notice that:
Since
l
= 2
q_{e}
in the simulation, therefore
Putting them together, the advantage of
M
in breaking CDHP is:
 4.2 Security Against Type1 Active/Concurrent Attacks
Theorem 1.
The certificateless identification scheme is (
t, q_{I}, ε
)
secure against StrongType1 impersonators under active/concurrent attack in the standard model if the OMCDHP is
(
t
"
, q
"
, ε
")
hard where
where ρ represents time taken to do a multiplication in G, τ is the time taken to do an exponentiation in G, – q_{e} represents the number of extract queries made, q_{i} represents the number of transcript queries made and q_{I}
=
q_{e}
+
q_{i}
.
Proof
. Define the following as the impersonation under active/concurrent attack (IMPAA/CA1) game. Assume that if the certificateless identification scheme is (
t, q_{I}, ε
)breakable by an impersonator
I
_{1}
, then we can show a simulator
M
that (
t
"
, q
"
, ε
")breaks the OMCDHP.
M
is given a challenge oracle
CHALL
which provides random points in
G
_{1}
and a solution oracle
CDH
that upon an input
h
outputs
h^{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
_{1}
=
g^{a}
).
M
then queries
CHALL
for the initial challenge
W
_{0}
and runs the Type1 impersonator
I
_{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
_{1}
is similar to that of the IMPPA1 game, and hence only the differences are shown.

1.Setup(1k)is similar to the one in the IMPPA1 game, exceptMsetsg2=W0instead,

2.CreateUser(IDi) queryis similar to the one in the IMPPA1 game.

3.ExtrPartSK(IDi) queryis similar to the one in the IMPPA1 game.

4.RequestPK(IDi) queryis similar to the one in the IMPPA1 game.

5.ExtrFullSK(IDi) queryis similar to the one in the IMPPA1 game.

6.ReplacePK(IDi,upk'IDi=〈UPK'1,IDi, UPK'2,IDi〉) queryis similar to the one in the IMPPA1 game.

7.Identification(IDi) query.This is where the game differs significantly from that of the IMPPA1 game. Once again,I1will act as a cheating verifier to learn information, but this time by requesting a valid conversation withM.MretrievesIDi’s stored details to conduct the conversation. Ifφ= 0,Mthen requests the new secret valuesv=sIDiand the replaced public keyupkIDifromI1.Mstarts with a counterm= 0 that is incremented everyIdentificationquery, then does the following:

i)MqueriesCHALLfor a randomWmand additionally choosesrIDiZq(if not yet created) andzmZq.MsetsXm=e(UIDi,RIDi)zm,Ym=WmandRIDi==gsIDirIDiand passes them as a commitment to toI1.

ii)I1selects a random challengecmZqand sends it back toM.

iii)Mresponds by queryingsets, and sends it toI1. One can check the validity of the second checking equation by:

Additionally the verifier’s first check equatione(g1, UPK1,IDi) =e(UPK2,IDi, g) for public values ofUPK'1,IDi,UPK'2,IDiof allIDs must hold even with the replaced public keys.
Eventually
I
_{1}
stops phase 1 and outputs the challenge identity,
ID
*, 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
_{1}
now as a cheating prover on
ID
*.
M
obtains (
X, Y, R, c
_{1}
, z
_{1}
) then resets
I
_{1}
to its previous state where it just sent its commitment to obtain (
X, Y, R, c
_{2}
, z
_{2}
). In both cases, it must hold that
e
(
g
_{1}
, UPK
_{1,ID*}
) =
e
(
UPK
_{2,ID*}
, g
) for all public values of
UPK
_{1,ID*}
, UPK
_{2,ID*}
of
ID
*. Based on the Reset Lemma
[22]
,
M
is then able to extract the full private key as
By using the knowledge of exponent assumption from
[19]
,
M
can either extract
σ
if 〈
UPK
_{1,ID*}
, UPK
_{2,ID*}
〉=〈
g^{σ}, g^{aσ}
〉 were generated from
g, g^{a}
, or extract ϱ if 〈
UPK
_{1,ID}
*
, UPK
_{2,ID*}
〉=〈
g
^{σϱ}
, g
^{aσϱ}
〉 were generated from
g^{σ}, g^{aσ}
.
For the first case,
M
calculates the solution to the CDH problem as:
For the second case,
M
calculates the solution to the CDH problem as:
Recall that
s_{IDi}
is provided by
I
_{1}
for every
m
th
Identification
query for the corresponding public key of
ID_{i}
being used, both for original or replaced.
M
then proceeds to calculate the solutions for the challenges
W
_{1}
,
…
,W_{m}
as:
The probability of
M
winning the OMCDHP is the same as in the IMPPA1 game, except that
ε'
, the advantage of
M
in solving the CDH problem is substituted with
ε
", the advantage of
M
in solving the OMCDHP game.
 4.3 Security Against Type2 Impersonation under Passive Attacks
Theorem 1.
The certificateless identification scheme is
(
t, q_{I}, ε
)
secure against StrongType2 impersonators under passive attack in the standard model if the CDHP is
(
t', ε'
)
hard where
where ρ represents time taken to do a multiplication in G, τ is the time taken to do an exponentiation in G , q_{e} represents the number of extract queries made, q_{i} represents the number of transcript queries made and q_{I}
=
q_{e}
+
q_{I}
.
Proof
. Suppose there exists an impersonator
I
_{2}
who (
t, q_{I}, ε
)breaks the IBI scheme. Then we show an algorithm
M
which (
t', ε'
)breaks the CDH problem by running
I
_{2}
as a subroutine.
M
is given a group
G
, a generator
g
∈
G
and, to keep with the consistency of scheme definitions, elements defined as
g^{s}, g^{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
_{2}
as follows:

1.Setup(1k).Taking in the security parameter 1k,Msetsl= 2qeand randomly chooseskZn. Assume thatl(n+ 1)

Mnow selectsaZq, setsg1=gaandg2=gb.Malso setsand a vector 〈u〉 of lengthnconsisting ofnelementsMpasses the system parametersmpktoI2as 〈G, GT, e, g, g1, g2, u',〈u〉, H〉 but does not have the master secret key. Note that with functionsF(ID) andJ(ID), we have:

In Type2 games,Mknows the master secret keyand is able to create partial private keys, thereforeExtrPartSKqueries are not necessary.

2.CreateUser(IDi) query:For anyRequestPK,ExtrFullSKandIdentificationquery,Mfirst checks if the userIDiis created. IfF(IDi) = 0mod l,MsetsUPK1,IDi=gsandIf not,Mfirst selectssIDiZq, precomputesand the public key componentsand sets a flagφIDi= 1 denoting that the public key is still the original forIDi.Mstores these values for future use.

3.RequestPK(IDi) query.MfindsupkIDi=〈UPK1,IDi, UPK2,IDi〉 and returns it toI2.

4.ExtrFullSK(IDi) query. IfF(IDi) = 0mod lthenMaborts the simulation. Otherwise,MretrievessIDi, selectsrIDiZqand calculatesUSK1,IDi=andUSK2,IDi=.MreturnstoI2.

5.ReplacePK(IDi, upk'IDi= 〈UPK'1,IDi, UPK'2,IDi〉) query.ForF(IDi) ≠ 0mod l,Mchecks if the new public key satisfiese(g1, UPK'1,IDi) =e(UPK'2,IDi, g),andreplaces 〈UPK1,IDi, UPK2,IDi〉 with 〈UPK'1,IDi, UPK'2,IDi〉 and setsφIDi= 0 if true. Note that the new corresponding secret value is not required here. Otherwise forF(IDi) = 0mod l,Mreplies with ⊥ sinceI2is not allowed to replace the challenge identity’s public key.

6.Identification(IDi) query.I2will act as a cheating verifier to learn information from valid conversation transcripts fromM.MretrievesIDi’s stored details to construct the transcript. For StrongType2 attacks,I2needs to supplysv=sIDifor replaced public keys.Mcan create a valid transcript for each of the following cases:

a) IfF(IDi)=0mod l, thenUIDi=gJ(IDi)andMpicksrIDiZq(if not yet created) andcm, zmZq, sets the transcript as=e(UIDi, RIDi)zm,and passes the transcript toI2.I2can check that this is a valid transcript since:

b) IfF(IDi) ≠ 0mod l, then. For this caseMcan build the full private key for any user other than those withF(IDi) = 0mod lsince it has access to the msk andsIDi. Ifφ= 0 thenMrequests the new secret valuesv=sIDifor the replaced public key fromI2.Mthen constructs the transcript by pickingrIDiZq(if not yet created),cm, zmZqand setting=e(UIDi, RIDi)zm,as the transcript. Once again,I2can check the second verifying equation:
Note that for both cases the public keys need to hold for the verifier’s first check equation
e
(
g
_{1}
, UPK
_{1,IDi}
) =
e
(
UPK
_{2,IDi}
, g
). In other words, the new public values of
UPK'
_{1,IDi}
, UPK'
_{2,IDi}
of all
ID
s must fulfill the check equation even with the replaced public keys, thus requiring
I
_{2}
to submit valid public key replacement values for
ReplacePK
queries and a valid
sv
for
Identification
queries.
Eventually
I
_{2}
stops phase 1 and outputs the challenge identity,
ID
*, 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
_{2}
now as a cheating prover on
ID
*.
M
obtains (
X, Y, R, c
_{1}
, z
_{1}
) then resets
I
_{2}
to its previous state where it just sent its commitment to obtain (
X, Y, R, c
_{2}
, z
_{2}
). In both cases, it must hold that
e
(
g
_{1}
, UPK
_{1,ID}
*) =
e
(
UPK
_{2,ID}
*
, g
) for all public values of
UPK
_{1,ID}
*,
UPK
_{2,ID}
* of
ID
*. Based on the Reset Lemma
[22]
,
M
is then able to extract the full private key as
Since
I
_{2}
is not allowed to replace the public key of
ID
*,
M
calculates the solution to the CDH problem as:
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
_{1}
is given by
as given by the Reset Lemma
[21]
. Upon extraction of
USK
_{1,ID}
*,
M
will be able to compute
g^{bs}
. We break down the probability of
M
winning the CDHP to:
Finally, calculate Pr [¬
abort
]. Define the following events:

3) EventAiwhereManswers all queriesF(IDi) ≠ 0mod land

4) EventA* whereIoutputs the challenge identityID* whereF(ID) = 0mod q.
Calculate the probability of
A
* as:
Notice that:
Since
l
= 2
q_{e}
in the simulation, therefore
Putting them together, the advantage of
M
in breaking CDHP is:
 4.4 Security Against Type2 Active/Concurrent Attacks
Theorem 1.
The certificateless identification scheme is
(
t, q_{I}, ε
)
secure against StrongType2 impersonators under active/concurrent attack in the standard model if the OMCDHP is
(
t
"
, q
"
, ε
")
hard where
where ρ represents time taken to do a multiplication in G, τ is the time taken to do an exponentiation in G, q_{e} represents the number of extract queries made, q_{i} represents the number of transcript queries made and q_{I}
=
q_{e}
+
q_{i}
.
Proof
. Define the following game as the impersonation under active/concurrent attack (IMPAA/CA2) game. Assume that the certificateless identification scheme is (
t, q_{I}, ε
)breakable by an impersonator
I
_{2}
, then we can show a simulator
M
that (
t
"
, q
"
, ε
")breaks the OMCDHP.
M
is given a challenge oracle
CHALL
which provides random points in
G
_{1}
and a solution oracle
CDH
that upon input
h
outputs
h^{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
_{1}
=
g^{a}
).
M
then queries
CHALL
for the initial challenge
W
_{0}
and runs the Type2 impersonator
I
_{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
_{2}
is similar to that of the IMPPA2 game, and hence only the differences are shown.

1.Setup(1k)is similar to the one in the IMPPA2 game.

2.CreateUser(IDi) queryis similar to the one in the IMPPA2 game, except forF(IDi) = 0mod l,MsetsUPK1,IDi=W0instead.

3.RequestPK(IDi) queryis similar to the one in the IMPPA2 game.

4.ExtrFullSK(IDi) queryis similar to the one in the IMPPA2 game.

5.ReplacePK(IDi),upk'IDi= 〈UPK'1,IDi, UPK'2,IDi〉) queryis similar to the one in the IMPPA2 game.

6.Identification(IDi) query.This is where the game differs significantly from the one in the IMPPA2 game. Once again,I2will act as a cheating verifier but this time by requesting a valid conversation withM.MretrievesIDi’s stored details to conduct the conversation. There are two cases to consider:

a) IfF(IDi) = 0mod l, thenUIDi=gJ(IDi).Mstarts with a counterm= 0 that is incremented everyIdentificationquery forF(IDi) = 0mod l, then does the following:

i)MqueriesCHALLfor a randomWmand additionally choosesrIDiZq(if not yet created) andzmZq.MsetsXm=e(UIDi, RIDi)zm,Ym=WmandRIDi=and passes them as a commitment to toI2.

ii)I2selects a random challengecmZqand sends it back toM.

iii)Mresponds by queryingsetsand sends it toI2.I2can check the validity of the second checking equation by:

b) IfF(IDi) = 0mod l, then. Ifφ= 0 thenMrequests the new secret valuesv=sIDiand the replaced public keyupk'IDifromI2, otherwiseMjust retrieves the originalsIDivalue. SinceMcan then construct the fulluskIDi,Mjust buildsUSK1,IDi=andUSK2,IDi=gsIDirIDiand uses it to run theIdentificationquery. For both cases ofφ, the check equatione(g,UPK2,IDi) =e(g1, UPK1,IDi) must hold.
Eventually
I
_{2}
stops phase 1 and outputs the challenge identity,
ID
*, 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
_{2}
now as a cheating prover on
ID
*.
M
obtains (
X, Y, R, c
_{1}
, z
_{1}
) then resets
I
_{2}
to its previous state where it just sent its commitment to obtain (
X, Y, R, c
_{2}
, z
_{2}
). In both cases, it must hold that
e
(
g
1
, UPK
_{1,ID}
*) =
e
(
UPK
_{2,ID}
*
, g
) for all public values of
UPK
_{1,ID}
*
, UPK
_{2,ID}
* of
ID
*. Based on the Reset Lemma
[22]
,
M
is then able to extract the full private key as
Since
I
_{2}
is not allowed to replace the public key of
ID
*,
M
calculates the solution to the OMCDHP as:
M
then proceeds to calculate the solutions for the challenges
W
_{1}
,
…
,W_{m}
as:
The probability of
M
winning the OMCDHP is the same as IMPPA2 game, except that
ε'
, the advantage of
M
in solving the CDH problem is substituted with
ε
", 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
.
Operation Costs for the Certificateless Identification Scheme
Operation Costs for the Certificateless Identification Scheme
Since the certificateless identification scheme is constructed based on an extension of the identitybased identification scheme from
[23]
to the certificateless setting, similar precomputations are able to be conducted in order to reduce operation costs.
One can precompute the value of
=
e
(
U_{ID},
USK
_{2,ID}
) beforehand, since this value is fixed, then calculate
X
=
for
Prover
each time the protocol is run. This will reduce up to
n
+ 1 times of multiplication in
G
_{1}
for both
Prover
and
Verifier
, and one pairing operation on
Prover
.
Another precomputation operation available is to precompute and store
U
= (
u'
Π
_{ɩ∈ID}
uɩ
) 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
_{1}
for
Verifier
.
The operation costs of
Prover
and
Verifier
with precomputation is given in
Table 2
.
Operation Costs for the Identification Protocol with Precomputation
Operation Costs for the Identification Protocol with Precomputation
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 nonreliance 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 Type1 and Type2 impersonators, both passive and active/concurrent alike assuming the CDHP and OMCDHP is hard. It is secure against SuperType1 and StrongType2 adversaries with regard to passive adversaries and secure against StrongType1 and StrongType2 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 SuperType 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.
Acknowledgements
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.
BIO
JiJian 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 the Faculty of Engineering, Multimedia University. His research interest is in cryptography, particularly in the area of public key cryptography.
SweeHuay 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 Multimedia 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 humaninvolved processes.
Shamir A.
1985
“Identitybased cryptosystems and signature schemes” Advances in cryptology
Springer Berlin Heidelberg
Article (CrossRef Link)
47 
53
AlRiyami S. S.
,
Paterson K. G.
2003
“Certificateless public key cryptography”
Springer Berlin Heidelberg
Advances in CryptologyASIACRYPT 2003
Article (CrossRef Link)
452 
473
Bellare M.
,
Namprempre C.
,
Neven G.
2009
“Security proofs for identitybased identification and signature schemes”
Journal of Cryptology
Article (CrossRef Link)
22
(1)
1 
61
DOI : 10.1007/s0014500890288
Kurosawa K.
,
Heng S. H.
2004
“From digital signature to IDbased identification/signature”
Springer Berlin Heidelberg
Public Key CryptographyPKC 2004
Article (CrossRef Link)
248 
261
Kurosawa K.
,
Heng S. H.
2005
“Identitybased identification without random oracles”
Springer Berlin Heidelberg
Computational Science and Its ApplicationsICCSA 2005
Article (CrossRef Link)
603 
613
Kurosawa K.
,
Heng S. H.
2006
“The power of identification schemes”
Springer Berlin Heidelberg
Public Key CryptographyPKC 2006
Article (CrossRef Link)
364 
377
Yang G.
,
Chen J.
,
Wong D. S.
,
Deng X.
,
Wang D.
2008
“A new framework for the design and analysis of identitybased identification schemes”
Theoretical Computer Science
Article (CrossRef Link)
407
(1)
370 
388
DOI : 10.1016/j.tcs.2008.07.001
Chin J. J.
,
Heng S. H.
,
Goi B. M.
2008
“An efficient and provable secure identitybased identification scheme in the standard model” Public Key Infrastructure
Springer Berlin Heidelberg
Article (CrossRef Link)
60 
73
Chin J. J.
,
Heng S. H.
,
Goi B. M.
2009
“Hierarchical identitybased identification schemes” Security Technology
Springer Berlin Heidelberg
Article (CrossRef Link)
93 
99
Thorncharoensri P.,
,
Susilo W
,
Mu Y.
2009
“Identitybased identification scheme secure against concurrentreset attacks without random oracles” Information Security Applications
Springer Berlin Heidelberg
Article (CrossRef Link)
94 
108
Fujioka A.
,
Saito T.
,
Xagawa K.
2012
“Security enhancements by ORproof in identitybased identification” Applied Cryptography and Network Security
Springer Berlin Heidelberg
Article (CrossRef Link)
135 
152
Fujioka A.
,
Saito T.
,
Xagawa K.
2012
“Security enhancement of identitybased identification with reversibility” Information and Communications Security
Springer Berlin Heidelberg
Article (CrossRef Link)
202 
213
Dehkordi M. H.
,
Alimoradi R.
2013
“Certificateless identification protocols from super singular elliptic curve”
Security and Communication Networks
Article (CrossRef Link)
Chin J. J.
,
Behnia R.
,
Heng S. H.
,
Phan R. P. C.
2014
“Cryptanalysis of a certificateless identification scheme”
Security and Communication Networks
Article (CrossRef Link)
Chin J. J.
,
Heng S. H.
,
Phan R. P. C
,
Behnia R.
2013
“An Efficient and Provably Secure Certificateless Identification Scheme”
in Proc. of Proceedings of the 10th International Conference on Security and Cryptography, SECRYPT
371 
378
Bellare M.
,
Rogawa P.
1993
“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
December
Article (CrossRef Link)
62 
73
Canetti R.
,
Goldreich O.
,
Halevi S.
2004
“The random oracle methodology, revisited”
Journal of the ACM (JACM)
Article (CrossRef Link)
51
(4)
557 
594
DOI : 10.1145/1008731.1008734
Boldyreva A.
2002
“Threshold signatures, multisignatures and blind signatures based on the gapDiffieHellmangroup signature scheme”
Springer Berlin Heidelberg
Public key cryptographyPKC 2003
Article (CrossRef Link)
31 
46
Damgard I.
1992
“Towards practical public key systems secure against chosen ciphertext attacks”
Springer Berlin Heidelberg
Advances in CryptologyCRYPTO’91
January
Article (CrossRef Link)
445 
456
Huang X.
,
Mu Y.
,
Susilo W.
,
Wong D. S.
,
Wu W.
2007
“Certificateless signature revisited” Information Security and Privacy
Springer Berlin Heidelberg
Article (CrossRef Link)
308 
322
Huang X.
,
Mu Y.
,
Susilo W.
,
Wong D. S.
,
Wu W.
2012
“Certificateless signatures: new schemes and security models”
The Computer Journal
Article (CrossRef Link)
55
(4)
457 
474
DOI : 10.1093/comjnl/bxr097
Bellare M.
,
Palacio A.
2002
“GQ and Schnorr identification schemes: Proofs of security against impersonation under active/concurrent attacks”
Springer Berlin Heidelberg
Advances in CryptologyCRYPTO 2002
Article (CrossRef Link)
162 
177
Tan S. Y.
,
Chin J. J.
,
Heng S. H.
,
Goi B. M.
2013
“An improved efficient provable secure identityBased identification scheme in the standard model”
KSII Transactions on Internet and Information Systems (TIIS)
7
(4)
910 
922
DOI : 10.3837/tiis.2013.04.018