Advanced
An Efficient and Provable Secure Certificateless Identification Scheme in the Standard Model
An Efficient and Provable Secure Certificateless Identification Scheme in the Standard Model
KSII Transactions on Internet and Information Systems (TIIS). 2014. Jul, 8(7): 2532-2553
Copyright © 2014, Korean Society For Internet Information
  • Received : November 08, 2013
  • Accepted : June 05, 2014
  • Published : July 28, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Ji-Jian Chin
Faculty of Engineering, Multimedia University, Cyberjaya, Selangor, Malaysia
Swee-Huay Heng
Faculty of Information Science and Technology, Multimedia University, Melaka, Malaysia
Raphael C.-W. Phan
Faculty of Engineering, Multimedia University, Cyberjaya, Selangor, Malaysia

Abstract
In Asiacrypt 2003, Al-Riyami and Paterson proposed the notion of certificateless cryptography, a technique to remove key escrow from traditional identity-based 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.
Keywords
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 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 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 GT is an admissible bilinear map if it satisfies
  • 1) Bilinearity:e(ga, gb) =e(g, g)abfor all generatorsg∈Ganda, b∈Z*q
  • 2) Non-degenaracy: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 Diffie-Hellman problem (CDHP):Giveng, ga, gbfor somea, b∈Z*q, computegab.
  • 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, 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 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|〈 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 ga , 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 = xa gr x ] ≤
PPT Slide
Lager Image
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)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)Set-User-Keyis 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)Partial-Private-Key-Extractis 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)Set-Private-Keyis 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 three-steρ 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 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 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)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 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 runPartial-Private-Key-Extractand returns the user's partial private keyPPKIDtoI1.
  • b)ExtrFullSK(ID). On request for the full private key on userID,Cwill runPartial-Private-Key-Extract, Set-Secret-Value,Set-Private-Keyalgorithms 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 runSet-User-Keyto 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)Normal-type adversaries cannot make an identification query for a prover if its public key is replaced.
  • ii)Strong-type 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)Super-type 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, qI, ε )-secure under passive or active/concurrent attacks if for any passive or active/concurrent Type-1 impersonator I 1 who runs in time t , Pr [ I 1 can impersonate ] < ε , where I 1 can make at most qI extract queries on full private keys.
Game II . The game played between a challenger C and the Type-2 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 runPartial-Private-Key-Extract,Set-Secret-Value,Set-Private-Keyalgorithms 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 runSet-User-Keyto 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)Normal-type adversaries cannot make an identification query for a prover if its public key is replaced.
  • ii)Strong-type 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)Super-type 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, qI, ε )-secure under passive or active/concurrent attacks if for any passive or active/concurrent Type-2 impersonator I 2 who runs in time t , Pr [ I 2 can impersonate ] < ε , where I 2 can make at most qI extract queries on full private keys.
3. Construction
In this section we show the construction of the new certificateless identification scheme. Let G and GT 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}* → {0,1} n to hash identity strings of arbitrary length to size n .
  • 1.Setup(1k): SelectaZq,g2,u'Gand ann-length 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.Set-User-Key(1k,mpk): SelectsIDZqand setupkID=〈UPK1,ID,UPK2,ID〉=
  • 3.Partial-Private-Key-Extract(mpk,msk,ID,upkID): ParseIDas ann-bit identity string withdidenoting thei-th 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. Set-Private-Key(mpk, ID, sID, upkID, ppkID):
  • First check ife(SID, UPK1,ID) =e(g2, UPK2,ID)e(UID, RID). This is according to the equation:
PPT Slide
Lager Image
  • 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:
PPT Slide
Lager Image
and
PPT Slide
Lager Image
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, qI, ε )- secure against Super-Type-1 impersonators under passive attack in the standard model if the CDHP is ( t', ε' )- hard where
PPT Slide
Lager Image
PPT Slide
Lager Image
where ρ represents time taken to do a multiplication in G, τ is the time taken to do an exponentiation in G, qe represents the number of extract queries made, qi represents the number of transcript queries made and qI = qe + qi .
Proof . Suppose there exists an impersonator I 1 who ( t, qI, ε )-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 ga , gb . 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)
PPT Slide
Lager Image
PPT Slide
Lager Image
  • 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:
PPT Slide
Lager Image
  • 2.CreateUser(IDi) query:For anyExtrPartSK,RequestPK,ExtrFullSKandIdentificationquery,Mfirst checks if the userIDiis created. If not,Mfirst selectssIDiZq, pre-computesand 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 eachm-th 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:
PPT Slide
Lager Image
  • 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
PPT Slide
Lager Image
By using the knowledge of exponent assumption from [19] , M can either extract σ if 〈 UPK 1,ID* , UPK 2,ID* 〉 = 〈 gσ, g 〉 were generated from g, ga , or extract ϱ if 〈 UPK 1,ID* , UPK 2,ID* 〉 = 〈 gσϱ, gaσϱ 〉 were generated from gσ, g .
For the first case, M calculates the solution to the CDH problem as:
PPT Slide
Lager Image
For the second case, M calculates the solution to the CDH problem as:
PPT Slide
Lager Image
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
PPT Slide
Lager Image
as given by the Reset Lemma [21] . Upon extraction of USK 1,ID* , M will be able to compute gab .
We break down the probability of M winning the CDHP to:
PPT Slide
Lager Image
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:
PPT Slide
Lager Image
Notice that:
PPT Slide
Lager Image
Since l = 2 qe in the simulation, therefore
PPT Slide
Lager Image
Putting them together, the advantage of M in breaking CDHP is:
PPT Slide
Lager Image
- 4.2 Security Against Type-1 Active/Concurrent Attacks
Theorem 1. The certificateless identification scheme is ( t, qI, ε )- secure against Strong-Type-1 impersonators under active/concurrent attack in the standard model if the OMCDHP is ( t " , q " , ε ")- hard where
PPT Slide
Lager Image
PPT Slide
Lager Image
where ρ represents time taken to do a multiplication in G, τ is the time taken to do an exponentiation in G, – qe represents the number of extract queries made, qi represents the number of transcript queries made and qI = qe + qi .
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, qI, ε )-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 ha . 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 = ga ). M then queries CHALL for the initial challenge W 0 and runs the Type-1 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 IMP-PA-1 game, and hence only the differences are shown.
  • 1.Setup(1k)is similar to the one in the IMP-PA-1 game, exceptMsetsg2=W0instead,
  • 2.CreateUser(IDi) queryis similar to the one in the IMP-PA-1 game.
  • 3.ExtrPartSK(IDi) queryis similar to the one in the IMP-PA-1 game.
  • 4.RequestPK(IDi) queryis similar to the one in the IMP-PA-1 game.
  • 5.ExtrFullSK(IDi) queryis similar to the one in the IMP-PA-1 game.
  • 6.ReplacePK(IDi,upk'IDi=〈UPK'1,IDi, UPK'2,IDi〉) queryis similar to the one in the IMP-PA-1 game.
  • 7.Identification(IDi) query.This is where the game differs significantly from that of the IMP-PA-1 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:
PPT Slide
Lager Image
  • 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
PPT Slide
Lager Image
By using the knowledge of exponent assumption from [19] , M can either extract σ if 〈 UPK 1,ID* , UPK 2,ID* 〉=〈 gσ, g 〉 were generated from g, ga , or extract ϱ if 〈 UPK 1,ID * , UPK 2,ID* 〉=〈 g σϱ , g ϱ 〉 were generated from gσ, g .
For the first case, M calculates the solution to the CDH problem as:
PPT Slide
Lager Image
For the second case, M calculates the solution to the CDH problem as:
PPT Slide
Lager Image
Recall that sIDi is provided by I 1 for every m -th Identification query for the corresponding public key of IDi being used, both for original or replaced. M then proceeds to calculate the solutions for the challenges W 1 , ,Wm as:
PPT Slide
Lager Image
The probability of M winning the OMCDHP is the same as in the IMP-PA-1 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 Type-2 Impersonation under Passive Attacks
Theorem 1. The certificateless identification scheme is ( t, qI, ε )- secure against Strong-Type-2 impersonators under passive attack in the standard model if the CDHP is ( t', ε' )- hard where
PPT Slide
Lager Image
PPT Slide
Lager Image
where ρ represents time taken to do a multiplication in G, τ is the time taken to do an exponentiation in G , qe represents the number of extract queries made, qi represents the number of transcript queries made and qI = qe + qI .
Proof . Suppose there exists an impersonator I 2 who ( t, qI, ε )-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 gs, gb . 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)
PPT Slide
Lager Image
PPT Slide
Lager Image
  • 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:
PPT Slide
Lager Image
  • In Type-2 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, pre-computesand 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 Strong-Type-2 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:
PPT Slide
Lager Image
  • 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:
PPT Slide
Lager Image
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
PPT Slide
Lager Image
Since I 2 is not allowed to replace the public key of ID *, M calculates the solution to the CDH problem as:
PPT Slide
Lager Image
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
PPT Slide
Lager Image
as given by the Reset Lemma [21] . Upon extraction of USK 1,ID *, M will be able to compute gbs . We break down the probability of M winning the CDHP to:
PPT Slide
Lager Image
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:
PPT Slide
Lager Image
Notice that:
PPT Slide
Lager Image
Since l = 2 qe in the simulation, therefore
PPT Slide
Lager Image
Putting them together, the advantage of M in breaking CDHP is:
PPT Slide
Lager Image
- 4.4 Security Against Type-2 Active/Concurrent Attacks
Theorem 1. The certificateless identification scheme is ( t, qI, ε )- secure against Strong-Type-2 impersonators under active/concurrent attack in the standard model if the OMCDHP is ( t " , q " , ε ")- hard where
PPT Slide
Lager Image
PPT Slide
Lager Image
where ρ represents time taken to do a multiplication in G, τ is the time taken to do an exponentiation in G, qe represents the number of extract queries made, qi represents the number of transcript queries made and qI = qe + qi .
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, qI, ε )-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 ha . 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 = ga ). M then queries CHALL for the initial challenge W 0 and runs the Type-2 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 IMP-PA-2 game, and hence only the differences are shown.
  • 1.Setup(1k)is similar to the one in the IMP-PA-2 game.
  • 2.CreateUser(IDi) queryis similar to the one in the IMP-PA-2 game, except forF(IDi) = 0mod l,MsetsUPK1,IDi=W0instead.
  • 3.RequestPK(IDi) queryis similar to the one in the IMP-PA-2 game.
  • 4.ExtrFullSK(IDi) queryis similar to the one in the IMP-PA-2 game.
  • 5.ReplacePK(IDi),upk'IDi= 〈UPK'1,IDi, UPK'2,IDi〉) queryis similar to the one in the IMP-PA-2 game.
  • 6.Identification(IDi) query.This is where the game differs significantly from the one in the IMP-PA-2 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:
PPT Slide
Lager Image
  • 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
PPT Slide
Lager Image
Since I 2 is not allowed to replace the public key of ID *, M calculates the solution to the OMCDHP as:
PPT Slide
Lager Image
M then proceeds to calculate the solutions for the challenges W 1 , ,Wm as:
PPT Slide
Lager Image
The probability of M winning the OMCDHP is the same as IMP-PA-2 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
PPT Slide
Lager Image
Operation Costs for the Certificateless Identification Scheme
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
PPT Slide
Lager Image
= e ( UID, USK 2,ID ) beforehand, since this value is fixed, then calculate X =
PPT Slide
Lager Image
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 pre-computation operation available is to pre-compute and store U = ( u' Π ɩID ) 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 pre-computation is given in Table 2 .
Operation Costs for the Identification Protocol with Pre-computation
PPT Slide
Lager Image
Operation Costs for the Identification Protocol with Pre-computation
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.
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
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 the 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 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 human-involved processes.
References
Shamir A. 1985 “Identity-based cryptosystems and signature schemes” Advances in cryptology Springer Berlin Heidelberg Article (CrossRef Link) 47 - 53
Al-Riyami S. S. , Paterson K. G. 2003 “Certificateless public key cryptography” Springer Berlin Heidelberg Advances in Cryptology-ASIACRYPT 2003 Article (CrossRef Link) 452 - 473
Bellare M. , Namprempre C. , Neven G. 2009 “Security proofs for identity-based identification and signature schemes” Journal of Cryptology Article (CrossRef Link) 22 (1) 1 - 61    DOI : 10.1007/s00145-008-9028-8
Kurosawa K. , Heng S. H. 2004 “From digital signature to ID-based identification/signature” Springer Berlin Heidelberg Public Key Cryptography-PKC 2004 Article (CrossRef Link) 248 - 261
Kurosawa K. , Heng S. H. 2005 “Identity-based identification without random oracles” Springer Berlin Heidelberg Computational Science and Its Applications-ICCSA 2005 Article (CrossRef Link) 603 - 613
Kurosawa K. , Heng S. H. 2006 “The power of identification schemes” Springer Berlin Heidelberg Public Key Cryptography-PKC 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 identity-based 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 identity-based 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 identity-based identification schemes” Security Technology Springer Berlin Heidelberg Article (CrossRef Link) 93 - 99
Thorncharoensri P., , Susilo W , Mu Y. 2009 “Identity-based identification scheme secure against concurrent-reset 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 OR-proof in identity-based identification” Applied Cryptography and Network Security Springer Berlin Heidelberg Article (CrossRef Link) 135 - 152
Fujioka A. , Saito T. , Xagawa K. 2012 “Security enhancement of identity-based 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 gap-Diffie-Hellman-group signature scheme” Springer Berlin Heidelberg Public key cryptography-PKC 2003 Article (CrossRef Link) 31 - 46
Damgard I. 1992 “Towards practical public key systems secure against chosen ciphertext attacks” Springer Berlin Heidelberg Advances in Cryptology-CRYPTO’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 Cryptology-CRYPTO 2002 Article (CrossRef Link) 162 - 177
Tan S. Y. , Chin J. J. , Heng S. H. , Goi B. M. 2013 “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    DOI : 10.3837/tiis.2013.04.018