Advanced
A pairing-free key-insulated certificate-based signature scheme with provable security
A pairing-free key-insulated certificate-based signature scheme with provable security
KSII Transactions on Internet and Information Systems (TIIS). 2015. Mar, 9(3): 1246-1259
Copyright © 2015, Korean Society For Internet Information
  • Received : October 02, 2014
  • Accepted : January 21, 2015
  • Published : March 31, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Hu Xiong
School of Computer Science and Engineering, University of Electronic Science and Technology of China Chengdu, Sichuan 610054 - CHINA
Shikun Wu
School of Computer Science and Engineering, University of Electronic Science and Technology of China Chengdu, Sichuan 610054 - CHINA
Ji Geng
School of Computer Science and Engineering, University of Electronic Science and Technology of China Chengdu, Sichuan 610054 - CHINA
Emmanuel Ahene
School of Computer Science and Engineering, University of Electronic Science and Technology of China Chengdu, Sichuan 610054 - CHINA
Songyang Wu
Third Research Institute, Ministry of Public Security Shanghai, 201204 – CHINA
Zhiguang Qin
School of Computer Science and Engineering, University of Electronic Science and Technology of China Chengdu, Sichuan 610054 - CHINA

Abstract
Certificate-based signature (CBS) combines the advantages of both public key-based signature and identity-based signature, while saving from the disadvantages of drawbacks in both PKS and IBS. The insecure deployment of CBS under the hostile circumstances usually causes the exposure of signing key to be inescapable. To resist the threat of key leakage, we present a pairing-free key insulated CBS scheme by incorporating the idea of key insulated mechanism and CBS. Our scheme eliminates the costly pairing operations and as a matter of fact outperforms the existing key insulated CBS schemes. It is more suitable for low-power devices. Furthermore, the unforgeability of our scheme has been formally proven to rest on the discrete logarithm assumption in the random oracle model.
Keywords
1. Introduction
T he digital signature, as a counterpart to ink signature in the electronic world, can be used to authenticate a digital message or document. A valid signature provides an enough evidence for a receiver to believe that the message or document was indeed issued by the claimed signer [1] . The digital signature was originally introduced in traditional asymmetric cryptography. In this environment, a certificate generated by the trusted certificate authority (CA) is needed to establish the connection between the public key (usually an unreadable random string) and the identity of the signer [2 - 4] . The extremely expensive overhead of certificate generation, distribution and revocation impedes digital signature from wide adoption in the government affair, financial transaction and software distribution. To lower the maintenance costs of certificates in traditional public key cryptography (PKC), Shamir [5] creatively put forward the notion of Identity-based (ID-based) cryptosystem. In ID-based cryptosystem, the certificates in the traditional PKC is no longer demanded due to the fact that the public key of the signer can be effortlessly derived from signer’s known identity information (phone number, email address and so on). For this reason, digital signature is extensively studied in ID-based cryptosystems [6 - 8] . However, the merits of ID-based cryptosystem are associated with the notorious key escrow problem. Specifically, the private key of the signer will be generated by a fully trusted private key generator (PKG) according to his/her identity and the PKG can impersonate all of the signers in the system without being detected and punished.
By incorporating the basic idea of both ID-based cryptosystem and conventional PKC simultaneously, certificate-based cryptography (CBC) [9] has been suggested to save from their disadvantages simultaneously. In CBC, the public and private key pair of the user is generated by the user himself/herself and a corresponding certificate of his/her public key is requested from the CA. On one hand, the certificate can guarantee the connection between the user and his/her public key as in traditional PKC. On the other hand, this certificate in CBC acts as part of the user’s private key such that the cryptographic operation such as signing or decrypting can only be performed by using user’s private key and certificate together. Featured with implicit certification, CBC revokes the need of third-party query in traditional PKC, and thus simplifies the complex certificate management. Also, CBC does not inherit key escrow problem from ID-based cryptosystem because the private key is generated and kept by the user himself/herself. Certificate-based signature (CBS) [10 - 14] , the combination of digital signature and CBC, has been naturally investigated.
It could be very disastrous if the private key is exposed in case CBS is insecurely deployed in a hostile environment. In the light of this, the key-insulated CBS [15 - 16] has been proposed. In the key-insulated mechanism, the life cycle of user’s private key is partitioned into different time slices. The private key of the user will evolve from one time period to the next with the aid of a physically secure device (helper) while the public key of the user will be fixed during the whole lifetime. As such, the corruption of private key in some time periods will not affect the security of private key in the other time periods. The first concrete key-insulated CBS scheme [17] has been proposed recently based on the costly bilinear pairing operation [18 , 19] . Hence, the construction of pairing-free key insulated CBS along with formal security proof is still an interesting and challenging problem.
In this paper, a pairing-free key-insulated CBS scheme has been presented. Our scheme eliminates the costly pairing operations and as a matter of fact outperforms the existing key insulated CBS schemes. It is more suitable for low-power devices. Furthermore, the unforgeability of our scheme is formally proven under the discrete logarithm assumption in the random oracle model [20] .
2. Preliminaries
In this section, we review the formal definition of CBS scheme and the building blocks of our scheme.
- 2.1 Mathematical Assumption
Definition 1. (Discrete Logarithm (DL) Assumption) Given a group
PPT Slide
Lager Image
with prime order p along with a generator P , the DL problem refers to compute x
PPT Slide
Lager Image
with the presence of a random element Q
PPT Slide
Lager Image
such that Q = xP . The DL assumption means that the DL problem in
PPT Slide
Lager Image
cannot be solved by an adversary
PPT Slide
Lager Image
with a non-negligible probability.
- 2.2 Modeling key-insulated CBS
According to [17] , a key insulated CBS scheme involves a CA, and a signer equipped with a helper, and consists of following eight algorithms: Setup , UserKeyGen , CertGen , SetInitialKey , UpdH , UpdS , Sign , and Verify .
  • Setup: This algorithm is carried out by the CA to generate the system public parametersparamsand master private keymskby taking a security parameter 1kas input.
  • UserKeyGen: This algorithm is performed by the user associated with the identityI Ditself to generate the public and private key pair (pkID,skID) by taking the system parametersparamsas input.
  • CertGen: This algorithm is executed by the CA to generate the certificateCertIDfor the user associated with the identityI Dand the public keypkIDby taking the master secret keymsk, the system public parametersparamsand {ID,pkID} as input.
  • SetInitialKey: This algorithm is run by the user to generate the initial temporary secret keyTSKID,0and helper keyHKIDby taking the system public parametersparams, the identityI D, the public keypkIDand the certificateCertIDof the user as input. After that, the helper keyHKIDwill be stored in a exclusive helper and the initial temporary secret keyTSKID,0will be kept by the user itself.
  • UpdH: To assist the user to update the temporary secret key from periodttot', an update keyUKID,t,t'will be generated by the helper by taking the system public parametersparams, the identityI D, the helper keyHKID, and (t,t') as input.
  • UpdS: This algorithm will be executed by the user to update the temporary secret keyTSKID,tcorresponding to the time periodtto the temporary secret keyTSKID,t'corresponding to the time periodt'by taking the system public parametersparams, the identityI Dof the user, (t,t'), and an update keyUKID,t,t'as input.
  • Sign: This algorithm is performed by the signer associated with the identityI Dand the public keypkIDto generate the signature (t,σ) by taking the temporary secret keyTSKID,t, the certificateCertID, the system public parametersparams, a messagem, and a period indextas input.
  • Verify: This algorithm can be executed by anyone to verify the validity of the signature pair (t,σ) by taking a messagem, the system public parametersparams, the identityI Dand the public keypkIDof the user as input.
- 2.3 Security definitions
Motivated by the security models for key insulated signature in traditional PKI [15 , 16] , ID-based cryptosystems [21 , 22] , and certificate-based signature [12 - 14] , Li et al . [17] formalized the security model for key insulated CBS scheme as follows: Two types of adversaries, type I adversary
PPT Slide
Lager Image
1 and type II adversary
PPT Slide
Lager Image
2 , along with two security games is considered to capture the attacks launched by the outside attacker and the malicious CA respectively.
PPT Slide
Lager Image
1 is an adversary who acts as an outsider and wants to forge a valid signature with the ability to replace the public key. The restriction for
PPT Slide
Lager Image
1 is that the master secret key cannot be accessed and the certificate of the replaced public key cannot be obtained by this kind of adversary.
PPT Slide
Lager Image
2 models the malicious CA as an adversary who wants to forge a valid signature by using the master secret key. The restriction for
PPT Slide
Lager Image
2 is that this kind of adversary cannot replace the public key of the target user. The security games against
PPT Slide
Lager Image
1 and
PPT Slide
Lager Image
2 are described as follows.
Game I (for the adversary
PPT Slide
Lager Image
1 ):
Setup : In this phase, the Setup algorithm is run by the challenger C . After that, params will be sent to
PPT Slide
Lager Image
1 and msk will be kept by C itself secretly.
Queries : C will answer the adaptive queries issued by
PPT Slide
Lager Image
1 as follows.
  • UserKeyGenoracle:Cmaintains an initially empty listLwith the item (IDi,skIDi,pkIDi). If the item associated with the identityIDihas not been created,Cgenerates {skIDi,pkIDi} by executing theUserKeyGenalgorithm, and inserts (IDi,skIDi,pkIDi) into the listL,Cdoes nothing otherwise. In both cases,pkIDiis returned to1.
  • ReplacePKoracle: Given a user’s identityIDialong with a public key,Cchecks the listLto confirm whether the item associated withIDihas been created or not. If this item has already been created,Creplaces the user’s original public keypkIDiwithby updating the item (IDi,skIDi,pkIDi) as (IDi, ⊥,) in listL. Otherwise,Cadds (IDi, ⊥,) into the listL.
  • Corruptionoracle: Given a user’s identityIDi,Cchecks whether the item associated withIDihas been created or not. If this item has already been created,CreturnsskIDias the answer. Otherwise,Cgenerates {skIDi,pkIDi} by executing theUserKeyGenalgorithm and inserts (IDi,skIDi,pkIDi) into the listL. After that,skIDiis returned as the answer.
  • Certificationoracle: Given a user’s identityIDialong with a public keypkIDi,Cexecutes the algorithmCertGenand returns the certificateCertIDias the answer.
  • Temporary secret keyoracle: Given a user's identityIDialong with a period indext,Creturns the temporary secret keyTSKID,tas the answer by executing the algorithmUpdS.
  • Signoracle: Given a tuple {ID,pkID,t,m},Creturns the signature (t,σ) as the answer by performing the algorithmSign.
Forgery :
PPT Slide
Lager Image
1 outputs a signature σ * on message m * in time period t * under the identity ID * and public key
PPT Slide
Lager Image
. We say that
PPT Slide
Lager Image
1 wins the game if: (a) Verify ( params , ( t *, σ *), m *, ID *,
PPT Slide
Lager Image
) = 1 . (b) { ID *,
PPT Slide
Lager Image
} has never been submitted to the Certification query. (c) { ID *, t *} has never been submitted to the Temporary secret key query. (d) { ID *,
PPT Slide
Lager Image
, m *, t *} has never been submitted to the Sign query.
Game II : (for the adversary
PPT Slide
Lager Image
2 )
Setup : In this phase, the Setup algorithm is run by the challenger C . After that, params and msk will be sent to
PPT Slide
Lager Image
2 .
Queries : Similar to Game I , the UserKeyGen , Corruption , Temporary secret key and Sign oracles can be queried adaptively by
PPT Slide
Lager Image
2 in this phase. Different from Game I , the Certification oracle is no longer needed to be queried due to the fact that the master secret key can be accessed by
PPT Slide
Lager Image
2 itself. In addition, the ReplacePK oracle can not be accessed by
PPT Slide
Lager Image
2 .
Forgery :
PPT Slide
Lager Image
2 outputs a signature σ * on message m * in time period t * under the identity ID * and public key
PPT Slide
Lager Image
. We say that
PPT Slide
Lager Image
2 wins the game if: (a) Verify ( params , ( t *, σ *), m *, ID *,
PPT Slide
Lager Image
) = 1. (b) ID * has never been submitted to the Corruption query. (c) { ID *, t *} has never been submitted to the Temporary secret key query. (d) { ID *,
PPT Slide
Lager Image
, m *, t *} has never been submitted to the Sign query.
Definition 2 . We say that a key insulated key CBS can achieve existential unforgeability against the adaptively chosen-message attack iff no adversary can win the Game I and Game II with non-negligible probability.
3. Our Proposed Scheme
In this section, the concrete construction of our key insulated CBS scheme is presented based on the idea in [14 , 21] .
  • Setup: CA generates a primepand determines the tuple {p,E/p,,P} according to the definition in[23]. Here,Erepresents a elliptic curve defined over a prime finite fieldp, andis a cyclic additive group with generatorP. After that, CA selectsx∈Ras the master secret key and computes the master public keyY=xP. Four hash functionsH0,H1,H2andH3are also picked up such thatH0: {0,1}* →,H1: {0,1}* →,H2: {0,1}* →andH3: {0,1}* →. Finally, CA publishesparams= {p,E/p,,P,Y,H0,H1,H2,H3} and keepsxsecret.
  • UserKeyGen: The userIDigenerates his user public/private key pair (uskIDi=xIDi,upkIDi=xIDiP) such thatxIDiis a secret value randomly chosen from.
  • CertGen: Given the public system parameterparams, master secret keyxalong with the user public keyupkIDiand identityIDi, CA randomly choosessIDi∈Rand computes the certificate (WIDi,dIDi) such thatWIDi=sIDiPanddIDi=sIDi+xH0(IDi║upkIDi║WIDi).
  • SetInitialKey: The userIDichooses the helper keyhkIDi∈Rand computes the initial secret keyTSKIDi,0= (SIDi,0,TIDi) such thatTIDi=hkIDiPandSIDi,0=xIDiH1(TIDi,IDi,upkIDi,WIDi) +hkIDiH2(TIDi,IDi,upkIDi,WIDi, 0) After that, the helper keyhkIDiwill be stored in the helper and the initial temporary secret keyTSKIDi,0will be kept by the user.
  • UpdH: The helper generates the update keyUKID,t,t'for the userIDfrom time periodttot'as follows:
  • UKID,t,t'=hkIDi(H2(TIDi,IDi,upkIDi,WIDi,t') -H2(TIDi,IDi,upkIDi,WIDi,t))
  • UpdS: Given the update keyUKID,t,t', and the temporary secret keyTSKIDi,t= (SIDi,t,TIDi) for a time periodt, the userIDicomputes his temporary secret key for time periodt'asTSKIDi,t= (SIDi,t,TIDi) , whereSIDi,t'=SIDi,t+UKID,t,t'.
  • Sign: Given the temporary secret keyTSKIDi,t= (SIDi,t,TIDi) in time periodt, and a messagem∈ {0,1}*, the signerIDiassociated with the user public keyupkIDiand certificate (WIDi,dIDi) performs the following steps:
  • 1. Randomly chooser∈Rand computeU=rP.
  • 2. Computez=dIDi+SIDi,t+rH3(m,t,TIDi,IDi,upkIDi,WIDi,U).
  • 3. Output (z,U,WIDi,TIDi) as the signature onmin time periodt.
  • Verify: To verify a signature (z,U,WIDi,TIDi) under the identityIDiand public keyupkIDion messagesm, the verifier performs the following steps:
  • 1. Computesh3=H3(m,TIDi,IDi,upkIDi,WIDi,U).
  • 2. Checks whether the following equation holds or not:
PPT Slide
Lager Image
If it holds, accept the signature; else reject it.
4. Analysis of our scheme
- 4.1 Security analysis
We show that the unforgeability of our key insulated CBS scheme against chosen-message attack rests on the discrete logarithm assumption in this section.
Theorem 1. (Unforgeability against adversary
PPT Slide
Lager Image
1 ) If a Type I adversary
PPT Slide
Lager Image
1 has forged a valid key insulated CBS scheme successfully in Game I defined in Section 2.3, then the DL problem can be solved. If a Type I adversary
PPT Slide
Lager Image
1 has an advantage ε in forging a certificate-based signature in Game I defined in Section 2.3 and making qHi (i=0, 1, 2, 3) queries to Hi queries, qu queries to the UserKeyGen request oracle, qcert queries to the Certification extraction oracle, qr queries to the ReplacePK extraction oracle, qcor queries to the Corruption extraction oracle, qt queries to the Temporary secret key extraction oracle, and qs queries to the Sign oracle, then the discrete logarithm problem can be solved with probability
PPT Slide
Lager Image
.
Proof . The basic idea of our security proof, borrowed from [14 , 17] , is that the simulator C can use the type I adversary
PPT Slide
Lager Image
1 as a function to solve the DL problem. C is given a tuple {
PPT Slide
Lager Image
p , E /
PPT Slide
Lager Image
p ,
PPT Slide
Lager Image
, P } according to the definition in [23] . The task of C is to find α R
PPT Slide
Lager Image
in the presence of Y = αP .
Setup : C chooses four hash functions H 0 : {0,1}* →
PPT Slide
Lager Image
, H 1 : {0,1}* →
PPT Slide
Lager Image
, H 2 : {0,1}* →
PPT Slide
Lager Image
and H 3 : {0,1}* →
PPT Slide
Lager Image
, and sends the system parameter params = {
PPT Slide
Lager Image
p , E /
PPT Slide
Lager Image
p ,
PPT Slide
Lager Image
, P , Y , H 0 , H 1 , H 2 , H 3 } to
PPT Slide
Lager Image
1 . Also, C will simulate these four hash functions as random oracles and keep α secret.
Queries : Seven initially empty lists
PPT Slide
Lager Image
and L will be maintained by C to avoid the conflict of the simulation. A random index j will also be chosen by C such that 1 ≤ j q H0 and q H0 is the maximum times
PPT Slide
Lager Image
1 can query the oracle H 0 . After that, C sets IDi = ID * where IDj is the j -th query to the oracle H 0 . Finally, C answers the following adaptive queries issued by
PPT Slide
Lager Image
1 .
H 0 oracle: Given a tuple ( IDi , upkIDi , WIDi ) as the query, C first searches the list H 0 to confirm whether the hash function of H 0 on this tuple has already been created or not. If not, C randomly chooses h i0
PPT Slide
Lager Image
as a hash function of ( IDi , upkIDi , WIDi ) and inserts the item ( IDi , upkIDi , WIDi , h i0 ) into the list H 0 , and C does nothing otherwise. In both cases, h i0 will be returned as the answer.
H 1 oracle: Given a tuple ( TIDi , IDi , upkIDi , WIDi ) as the query, C first searches the list H 1 to confirm whether the hash function of H 1 on this tuple has already been created or not. If not, C randomly chooses h i1
PPT Slide
Lager Image
as a hash function of ( TIDi , IDi , upkIDi , WIDi ) and inserts the item ( TIDi , IDi , upkIDi , WIDi , h i1 ) into the list H 1 , and C does nothing otherwise. In both cases, h i1 will be returned as the answer.
H 2 oracle: Given a tuple ( TIDi , IDi , upkIDi , WIDi , t ) as the query, C first searches the list H 2 to confirm whether the hash function of H 2 on this tuple has already been created or not. If not, C randomly chooses h i2
PPT Slide
Lager Image
as a hash function of ( TIDi , IDi , upkIDi , WIDi , t ) and inserts the item ( TIDi , IDi , upkIDi , WIDi , t , h i2 ) to H 2 , and C does nothing otherwise. In both cases, h i2 will be returned as the answer.
H 3 oracle: Given a tuple ( m , t , TIDi , IDi , upkIDi , WIDi , U ) as the query, C first searches the list H 3 to confirm whether the hash function of H 3 on this tuple has already been created or not. If not, C randomly chooses h i3
PPT Slide
Lager Image
as a hash function of ( m , t , TIDi , IDi , upkIDi , WIDi , U ) and inserts the item ( m , t , TIDi , IDi , upkIDi , WIDi , U , h i3 ) to H 3 , and C does nothing otherwise. In both cases, h i3 will be returned as the answer.
  • Certificationoracle: Given an identityIDialong with the user public keyupkIDi,Ccan generate the certificate for this user by performing the following steps.
1. If i j , C scans the list M to confirm whether the certificate associated with ( IDi , upkIDi ) has already been created or not. If not, C chooses h i0 , dIDi
PPT Slide
Lager Image
at random and computes WIDi = dIDi P - h i0 Y . Then C searches the list H 0 to confirm whether the item ( IDi , upkIDi , WIDi ) has already been created or not. If so, C will rechoose h i0 , dIDi
PPT Slide
Lager Image
to avoid collision, otherwise C further inserts ( IDi , upkIDi , WIDi , h i0 ) into the list H 0 and ( IDi , upkIDi , WIDi , dIDi ) into the list M respectively. In both cases, C then returns ( WIDi , dIDi ) as the answer.
2. If i = j , the simulation will be aborted.
  • UserKeyGenoracle: Given a queryIDi,Cfirst searches the listKto confirm whether the item associated withIDihas already been created or not. If not,CselectsxIDi∈at random as user secret keyuskIDi, and computes the corresponding public keyupkIDi=xIDiP. After that,Cinserts the item {IDi,uskIDi,upkIDi} into the listK. Otherwise,Cdoes nothing. In both cases,upkIDiwill be returned as the answer.
  • ReplacePKoracle: Given an identityIDialong with a user public key,Csearches the listKto confirm whetherIDihas already been created or not. If so,Cupdates the item (IDi,upkIDi,uskIDi) as (IDi,, ⊥). Otherwise,Cinserts the item (IDi,, ⊥) into listK.
  • Corruptionoracle: Given the identityIDi,1performs the following steps to generate the user secret key for this user.
  • 1. If there is an item (IDi,upkIDi,uskIDi) in the listK,CreturnsuskIDias the answer.
  • 2. OtherwiseCchoosesxIDi∈as his secret keyuskIDi, and computesupkIDi1=xIDiP. ThenCreturnsuskIDias the answer and inserts the item (IDi,upkIDi,uskIDi) into the listK.
  • Temporary secret keyoracle: Given an identityIDiand time indext,Cfirst searches the listLto confirm whether the item associated withIDihas already been created or not. If not,CselectshkIDi∈at random as the helper key, computesTIDi=hkIDiP, and inserts the item (IDi,hkIDi,TIDi) into the listL. Otherwise,Cextracted thehkIDifrom the item (IDi,hkIDi,TIDi) in the listL. After that,Cextracted thexIDiby querying theUserKeyGenoracle. Finally,Cchooseshi1,hi2∈at random and computesSIDi,t=xIDihi1+hkIDihi2. Then,Csets (TIDi,IDi,upkIDi,WIDi) =hi1and (TIDi,IDi,upkIDi,WIDi,t) =hi2. If the hash functionsH1andH2have already been defined,Cneed to rechoose these random values until the collision is avoided. Otherwise,Cinserts the item {IDi,upkIDi,uskIDi} into the listK, the item (IDi,hkIDi,TIDi) into the listL, the item (TIDi,IDi,upkIDi,WIDi) into the list, the item (TIDi,IDi,upkIDi,WIDi,t) into the listH2respectively, and returns (TIDi,SIDi,t) as the answer.
  • Signoracle: Given a tuple (m,t,IDi,upkIDi) as the query,Cqueries theTemporary secret keyoracle to get (TIDi,SIDi,t). After that,Ccreates a valid signature as follow.
  • 1. Ifi=j,Cchooseshj0,hj1,hj2,hj3,zj∈at random and computesandWIDj=hj0Y. After that,CsetsH0(IDj║upkIDi║WIDj) =hj0,H1(TIDi,IDi,upkIDi,WIDi) =hj1,H2(TIDi,IDi,upkIDi,WIDi,t) =hj2andH3(m,t,TIDi,IDi,upkIDi,WIDi,U) =hj3. If the hash functionsH0,H1,H2andH3have already been defined,Cneeds to rechoose these random values until the collision is avoided. Otherwise,Cinserts the item (IDj,upkIDj,WIDj,hj0) into the list, the item (TIDi,IDi,upkIDi,WIDi,hj1) into the listH1, the itemTIDi,IDi,upkIDi,WIDi,t,hj2) into the list, the item (m,t,TIDi,IDi,upkIDi,WIDi,Uj,hj3) into the list. Finally, the signature (zj,Uj,WIDj,TIDj) is returned as the answer.
  • 2. Ifi≠j,Cqueries theCertificationoracle to get (WIDi,dIDi), and generates the signature by performing theSignalgorithm using the certificate (WIDi,dIDi) and the temporary secret key (TIDi,SIDi,t).
Forgery : Finally,
PPT Slide
Lager Image
1 outputs a valid signature ( z *, U *, WID* , TID* ) on message m * on behalf of the identity ID * and the corresponding public key
PPT Slide
Lager Image
in time period t *. If ID * ≠ IDj , C aborts. Otherwise, C can replay
PPT Slide
Lager Image
1 with the same random tape in the simulation of H 1 , H 2 and H 3 but different choice of the hash function H 0 based on the forking lemma [24] . After that, C can get another valid signature ( z' , U *, WID* , TID* ). From these two valid ring signatures, C obtain
PPT Slide
Lager Image
and
PPT Slide
Lager Image
According to the above two equations we observe that
PPT Slide
Lager Image
. It is obvious that the DL problem can be solved by C successfully.
This completes the descripton of the simulation and it remains to analyze the probability of C ’s advantage. Define the event E 1 as that C does not abort when answering oracle queres, the event E 2 as that
PPT Slide
Lager Image
1 outputs a valid signature successfully and the event E 3 as that the identity of the forged signature output by the
PPT Slide
Lager Image
1 in the forgery phase is IDj . Observations from the simulation demonstrate that
PPT Slide
Lager Image
, Pr[ E 2 ] = ε and
PPT Slide
Lager Image
. Thus, the success probability of C solving the DL problem is
PPT Slide
Lager Image
.
Theorem 2 . (Unforgeability against adversary
PPT Slide
Lager Image
2 ) If a Type II adversary
PPT Slide
Lager Image
2 has an advantage ε in forging a certificate-based signature in Game II defined in Section 2.3 and making qHi (i=0, 1, 2, 3) queries to Hi queries, qu queries to the UserKeyGen request oracle, qcert queries to the Certification extraction oracle, qr queries to the ReplacePK extraction oracle, qcor queries to the Corruption extraction oracle, qt queries to the Temporary secret key extraction oracle, and qs queries to the Sign oracle, then the discrete logarithm problem can be solved with probability
PPT Slide
Lager Image
.
The security proof is similar to Theorem 1 and is omitted here.
Theorem 3 . Our key insulated CBS scheme can offer secure key-updates.
This theorem follows from the fact that for any target identity IDi , public key upkIDi and the time indices i and j , the update key UK ID,t,t' can be derived from the temporary secret key S IDi,t and S IDi,t' .
- 4.2 Performance evaluation
We compare our approach with Li et al .’s key insulated CBS scheme [17] in terms of communication overhead and the computation cost. To offer the security level equal to 1024-bit RSA in Li et al .’s pairing-based scheme, a Tate pairing defining on the supersingular elliptic curve E /
PPT Slide
Lager Image
p : y 2 = x 3 + x is adopted. Here, the embedding degree of curve E /
PPT Slide
Lager Image
p is 2, q = 2 159 + 2 17 +1 refers to a 160-bit Solinas prime, and p = 12 qr - 1 is a 512-bit prime. To achieve the similar level of security for our pairing-free approach, the Koblitz elliptic curve y 2 = x 3 + ax 2 + b defined on
PPT Slide
Lager Image
2163 can be used. Here, a = 11 and b is a randomly chosen prime with the length of 163-bit. The running time of the cryptographic operation listed in Table 1 can be derived using the standard cryptographic library MIRACAL [25] , and the hardware and OS for the experiment is PIV 3 GHZ processor with 512 M bytes storage capacity, and the Windows XP operating system respectively [26] .
Cryptographic operation time in milliseconds
PPT Slide
Lager Image
Cryptographic operation time in milliseconds
The computation and communication efficiency is evaluated based on the method proposed in [27] . For example, in the Verify algorithm of Li et al .’s scheme [17] , five pairing operations are needed, and thus the computation time is 5 × 20.01 = 100.05 ms. The signature Li et al .’s scheme [17] consists of three points in the pairing-based group, and thus the bandwidth for Li et al .’s scheme [17] is 512 × 3/8 = 192 byte. Observing the comparison results listed in Table 2 , our scheme outperforms the existing key insulated CBS scheme and is more suitable for the low power device.
Performance comparisons with existing work
PPT Slide
Lager Image
Performance comparisons with existing work
5. Conclusion
In this paper, a pairing-free key insulated CBS scheme has been proposed. The proposal can achieve unforgeability in the random oracle model provided that the discrete logarithm problem is hard. Our approach can trigger the deployment of CBS in the hostile and resource-limited scenarios.
BIO
Hu Xiong received his Ph.D. degrees from University of Electronic Science and Technology of China (UESTC) in 2009. He is now an associate professor in the UESTC. His research interests include cryptography and ad hoc networks security.
Shikun Wu received his B.S. degree in the School of Computer Science and Engineering, Anhui University of Science and Technology (AUST) in Jun 2009. He is currently pursuing his M.S. degree in the School of Computer Science and Engineering, UESTC. His research interests include cryptographic protocols and network security.
Ji Geng is a professor in the School of Computer Science and Engineering, UESTC. He received his Ph.D. degrees from UESTC in 2014. His research interests include: information security and system software.
Emmanuel Ahene received his B.S degree in computer science from the University for Development Studies, Ghana in 2012. He is currently pursuing his M.S degree in Computer Science and Technology at the School of computer science and Engineering, University of Electronic Science and Technology of China. His research interest include Cloud computing and Information security.
Songyang Wu is an associate professor at The Third Research Institute of Ministry of Public Security, China .Vice director. He received his Ph.D. Degree in computer Science from TongJi University, China in 2011. His current research interests are in information security, cloud computing and digital forensics.
Zhiguang Qin is a full professor in the School of Computer Science and Engineering and now with the president of School of Computer Science and Engineering, UESTC. He received his Ph.D. degree from UESTC in 1996. His research interests include: information security and wireless networks.
References
Diffie W. , Hellman M. E. 1976 “New directions in cryptography” IEEE Transactions on Information Theory 22 (6) 644 - 654    DOI : 10.1109/TIT.1976.1055638
Rivest R. L. , Shamir A. , Adleman L. 1978 “A method for obtaining digital signatures and public-key cryptosystems” Communications of the ACM 21 (2) 120 - 126    DOI : 10.1145/359340.359342
ElGamal T. “A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms” Springer-Verlag Advances in Cryptology-CRYPTO 1984 1984 LNCS 196 10 - 18
Boneh D. , Lynn B. , Shacham H. “Short signatures from the weil pairing” Springer-Verlag Advances in Cryptology- ASIACRYPT 2001 2001 LNCS 2248 514 - 532
Shamir A. “Identity-based cryptosystems and signature schemes” Springer-Verlag Advances in Cryptology-CRYPTO 1984 1984 LNCS 196 47 - 53
Hess F. “Efficient identity based signature schemes based on pairings” Springer-Verlag Selected Areas in Cryptography-SAC 2002 2003 LNCS 2595 310 - 324
Paterson K. G. 2002 “ID-based signatures from pairings on elliptic curves” Electronics Letters 38 (18) 1025 - 1026    DOI : 10.1049/el:20020682
Bellare M. , Namprempre C. , Neven G. 2009 “Security Proofs for Identity-Based Identification and Signature Schemes” Journal of Cryptology 22 (1) 1 - 61    DOI : 10.1007/s00145-008-9028-8
Gentry C. “Certificate-based encryption and the certificate revocation problem” Springer-Verlag Advances in Cryptology- EUROCRYPT 2003 2003 LNCS 2656 272 - 293
Kang B. G. , Park J. H. , Hahn S. G. “A certificate-based signature scheme,” Springer-Verlag in Proc. of Topics in Cryptology-CT-RSA 2004, The Cryptographers’ Track at the RSA Conference 2004 2004 LNCS 2964 99 - 111
Joseph K. , Liu J. B. , Willy S. , Zhou J. “Certificate-Based Signature Schemes without Pairings or Random Oracles” Springer-Verlag in Proc. of 11th International Conference on Information Security (ISC 2008) 2008 LNCS 5222 285 - 297
Li J. , Huang X. , Mu Y. , Susilo W. , Wu Q. “Certificate-based signature: Security model and efficient construction” Springer-Verlag in Proc. of 4th European PKIWorkshop: Theory and Practice (EuroPKI’ 07) 2007 LNCS 4582 110 - 125
Li J. , Huang X. , Zhang X. , Xu L. 2012 “An efficient short certificate-based signature scheme” Journal of Systems and Software 85 (2) 314 - 322    DOI : 10.1016/j.jss.2011.08.014
Li J. , Wang Z. , Zhang Y. 2013 “Provably secure certificate-based signature scheme without pairings” Information Sciences 233 (1) 313 - 320    DOI : 10.1016/j.ins.2013.01.013
Dodis Y. , Katz J. , Xu S. , Yung M. “Key-insulated public key cryptosystems” Springer-Verlag in Advances in Cryptology- Eurocrypt’02 2002 LNCS 2332 65 - 82
Dodis Y. , Katz J. , Xu S. , Yung M. “Strong key-insulated signature scheme” Springer-Verlag in Proc. of 6th International Workshop on Practice and Theory in Public Key Cryptography(PKC 2003) 2003 LNCS 2567 130 - 144
Li J. , Du H. , Zhang Y. , Li T. , Zhang Y. 2014 “Provably Secure Certificate-based Key-Insulated Signature Scheme” Concurrency and Computation Practice and Experience 26 (8) 1546 - 1560    DOI : 10.1002/cpe.3019
Hofheinz D. , Jager T. , Kiltz E. “Short signatures from weaker assumptions” Springer-Verlag Berlin Advances in Cryptology-ASIACRYPT 2011 2011 LNCS 7073 647 - 666
Chen L. , Cheng Z. , Smart N. P. 2007 “Identity-based key agreement protocols from pairings” International Journal of Information Security 6 (4) 213 - 241    DOI : 10.1007/s10207-006-0011-9
Bellare M. , Rogaway P. “Random oracles are practical: a paradigm for designing efficient protocols” in Proc. of 1st ACM Conf. on Computer and Communications Security (CCS 1993) 1993 62 - 72
Weng J. , Liu S. , Chen K. , Li X. “Identity-Based Key-Insulated Signature with Secure Key-Updates” Springer-Verlag in Proc. of 2nd SKLOIS Conference on Information Security and Cryptology-Inscrypt 2006 2006 LNCS 4318 13 - 26
Zhou Y. , Cao Z. , Chai Z. “Identity based key insulated signature” Springer-Verlag in Proc. of 2nd International Conference on Information Security Practice and Experience (ISPEC 2006) 2006 LNCS 3903 226 - 234
Cilardo A. , Coppolino L. , Mazzocca N. , Romano L. 2006 “Elliptic curve cryptography engineering” Proceedings of the IEEE 94 (2) 395 - 406    DOI : 10.1109/JPROC.2005.862438
Pointcheval D. , Stern J. 2000 “Security arguments for digital signatures and blind signatures” Journal of Cryptology 13 (3) 361 - 369    DOI : 10.1007/s001450010003
Shamus Software Ltd “Multiprecision Integer and Rational Arithmetic Cryptographic Library (Miracl)” http://www.certivox.com/miracl/
Cao X. , Kou W. , Du X. 2010 “A pairing-free identity-based authenticated key agreement protocol with minimal message exchanges” Information Sciences 180 (15) 2895 - 2903    DOI : 10.1016/j.ins.2010.04.002
Ren K. , Lou W. , Zeng K. , Moran P. J. 2007 “On broadcast authentication in wireless sensor networks” IEEE Trans. Wireless Commun. 6 (11) 4136 - 4144    DOI : 10.1109/TWC.2007.060255