Certificatebased signature (CBS) combines the advantages of both public keybased signature and identitybased 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 pairingfree 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 lowpower devices. Furthermore, the unforgeability of our scheme has been formally proven to rest on the discrete logarithm assumption in the random oracle model.
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 Identitybased (IDbased) cryptosystem. In IDbased 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 IDbased cryptosystems
[6

8]
. However, the merits of IDbased 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 IDbased cryptosystem and conventional PKC simultaneously, certificatebased 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 thirdparty query in traditional PKC, and thus simplifies the complex certificate management. Also, CBC does not inherit key escrow problem from IDbased cryptosystem because the private key is generated and kept by the user himself/herself. Certificatebased 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 keyinsulated CBS
[15

16]
has been proposed. In the keyinsulated 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 keyinsulated CBS scheme
[17]
has been proposed recently based on the costly bilinear pairing operation
[18
,
19]
. Hence, the construction of pairingfree key insulated CBS along with formal security proof is still an interesting and challenging problem.
In this paper, a pairingfree keyinsulated 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 lowpower 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
with prime order
p
along with a generator
P
, the DL problem refers to compute
x
∈
with the presence of a random element
Q
∈
such that
Q
=
xP
. The DL assumption means that the DL problem in
cannot be solved by an adversary
with a nonnegligible probability.
 2.2 Modeling keyinsulated 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]
, IDbased cryptosystems
[21
,
22]
, and certificatebased 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
_{1}
and type II adversary
_{2}
, along with two security games is considered to capture the attacks launched by the outside attacker and the malicious CA respectively.
_{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
_{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.
_{2}
models the malicious CA as an adversary who wants to forge a valid signature by using the master secret key. The restriction for
_{2}
is that this kind of adversary cannot replace the public key of the target user. The security games against
_{1}
and
_{2}
are described as follows.
Game I
(for the adversary
_{1}
):
Setup
: In this phase, the
Setup
algorithm is run by the challenger
C
. After that, params will be sent to
_{1}
and
msk
will be kept by
C
itself secretly.
Queries
:
C
will answer the adaptive queries issued by
_{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
:
_{1}
outputs a signature
σ
* on message
m
* in time period
t
* under the identity
ID
* and public key
. We say that
_{1}
wins the game if: (a)
Verify
(
params
, (
t
*,
σ
*),
m
*,
ID
*,
) = 1 . (b) {
ID
*,
} has never been submitted to the
Certification
query. (c) {
ID
*,
t
*} has never been submitted to the
Temporary secret key
query. (d) {
ID
*,
,
m
*,
t
*} has never been submitted to the
Sign
query.
Game II
: (for the adversary
_{2}
)
Setup
: In this phase, the
Setup
algorithm is run by the challenger
C
. After that,
params
and
msk
will be sent to
_{2}
.
Queries
: Similar to
Game I
, the
UserKeyGen
,
Corruption
,
Temporary secret key
and
Sign
oracles can be queried adaptively by
_{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
_{2}
itself. In addition, the
ReplacePK
oracle can not be accessed by
_{2}
.
Forgery
:
_{2}
outputs a signature
σ
* on message
m
* in time period
t
* under the identity
ID
* and public key
. We say that
_{2}
wins the game if: (a)
Verify
(
params
, (
t
*,
σ
*),
m
*,
ID
*,
) = 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
*,
,
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 chosenmessage attack iff no adversary can win the
Game I
and
Game II
with nonnegligible 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:
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 chosenmessage attack rests on the discrete logarithm assumption in this section.
Theorem 1. (Unforgeability against adversary
_{1}
) If a Type I adversary
_{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
_{1}
has an advantage
ε
in forging a certificatebased signature in Game I defined in Section 2.3 and making
q_{Hi}
(i=0, 1, 2, 3) queries to
H_{i}
queries,
q_{u}
queries to the
UserKeyGen
request oracle,
q_{cert}
queries to the
Certification
extraction oracle,
q_{r}
queries to the
ReplacePK
extraction oracle,
q_{cor}
queries to the
Corruption
extraction oracle,
q_{t}
queries to the
Temporary secret key
extraction oracle, and
q_{s}
queries to the Sign oracle, then the discrete logarithm problem can be solved with probability
.
Proof
. The basic idea of our security proof, borrowed from
[14
,
17]
, is that the simulator
C
can use the type I adversary
_{1}
as a function to solve the DL problem.
C
is given a tuple {
_{p}
,
E
/
_{p}
,
,
P
} according to the definition in
[23]
. The task of
C
is to find
α
∈
_{R}
in the presence of
Y
=
αP
.
Setup
:
C
chooses four hash functions
H
_{0}
: {0,1}* →
,
H
_{1}
: {0,1}* →
,
H
_{2}
: {0,1}* →
and
H
_{3}
: {0,1}* →
, and sends the system parameter
params
= {
_{p}
,
E
/
_{p}
,
,
P
,
Y
,
H
_{0}
,
H
_{1}
,
H
_{2}
,
H
_{3}
} to
_{1}
. Also,
C
will simulate these four hash functions as random oracles and keep
α
secret.
Queries
: Seven initially empty lists
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
_{1}
can query the oracle
H
_{0}
. After that,
C
sets
ID_{i}
=
ID
* where
ID_{j}
is the
j
th query to the oracle
H
_{0}
. Finally,
C
answers the following adaptive queries issued by
_{1}
.
H
_{0}
oracle: Given a tuple (
ID_{i}
,
upk_{IDi}
,
W_{IDi}
) 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}
∈
as a hash function of (
ID_{i}
,
upk_{IDi}
,
W_{IDi}
) and inserts the item (
ID_{i}
,
upk_{IDi}
,
W_{IDi}
,
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 (
T_{IDi}
,
ID_{i}
,
upk_{IDi}
,
W_{IDi}
) 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}
∈
as a hash function of (
T_{IDi}
,
ID_{i}
,
upk_{IDi}
,
W_{IDi}
) and inserts the item (
T_{IDi}
,
ID_{i}
,
upk_{IDi}
,
W_{IDi}
,
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 (
T_{IDi}
,
ID_{i}
,
upk_{IDi}
,
W_{IDi}
,
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}
∈
as a hash function of (
T_{IDi}
,
ID_{i}
,
upk_{IDi}
,
W_{IDi}
,
t
) and inserts the item (
T_{IDi}
,
ID_{i}
,
upk_{IDi}
,
W_{IDi}
,
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
,
T_{IDi}
,
ID_{i}
,
upk_{IDi}
,
W_{IDi}
,
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}
∈
as a hash function of (
m
,
t
,
T_{IDi}
,
ID_{i}
,
upk_{IDi}
,
W_{IDi}
,
U
) and inserts the item (
m
,
t
,
T_{IDi}
,
ID_{i}
,
upk_{IDi}
,
W_{IDi}
,
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 (
ID_{i}
,
upk_{IDi}
) has already been created or not. If not,
C
chooses
h
_{i0}
,
d_{IDi}
∈
at random and computes
W_{IDi}
=
d_{IDi}
P

h
_{i0}
Y
. Then
C
searches the list
H
_{0}
to confirm whether the item (
ID_{i}
,
upk_{IDi}
,
W_{IDi}
) has already been created or not. If so,
C
will rechoose
h
_{i0}
,
d_{IDi}
∈
to avoid collision, otherwise
C
further inserts (
ID_{i}
,
upk_{IDi}
,
W_{IDi}
,
h
_{i0}
) into the list
H
_{0}
and (
ID_{i}
,
upk_{IDi}
,
W_{IDi}
,
d_{IDi}
) into the list
M
respectively. In both cases,
C
then returns (
W_{IDi}
,
d_{IDi}
) 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,
_{1}
outputs a valid signature (
z
*,
U
*,
W_{ID*}
,
T_{ID*}
) on message
m
* on behalf of the identity
ID
* and the corresponding public key
in time period
t
*. If
ID
* ≠
ID_{j}
,
C
aborts. Otherwise,
C
can replay
_{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
*,
W_{ID*}
,
T_{ID*}
). From these two valid ring signatures,
C
obtain
and
According to the above two equations we observe that
. 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
_{1}
outputs a valid signature successfully and the event
E
_{3}
as that the identity of the forged signature output by the
_{1}
in the forgery phase is
ID_{j}
. Observations from the simulation demonstrate that
, Pr[
E
_{2}
] =
ε
and
. Thus, the success probability of
C
solving the DL problem is
.
Theorem 2
. (Unforgeability against adversary
_{2}
) If a Type II adversary
_{2}
has an advantage
ε
in forging a certificatebased signature in Game II defined in Section 2.3 and making
q_{Hi}
(i=0, 1, 2, 3) queries to
H_{i}
queries,
q_{u}
queries to the
UserKeyGen
request oracle,
q_{cert}
queries to the
Certification
extraction oracle,
q_{r}
queries to the
ReplacePK
extraction oracle,
q_{cor}
queries to the
Corruption
extraction oracle,
q_{t}
queries to the
Temporary secret key
extraction oracle, and
q_{s}
queries to the
Sign
oracle, then the discrete logarithm problem can be solved with probability
.
The security proof is similar to Theorem 1 and is omitted here.
Theorem 3
. Our key insulated CBS scheme can offer secure keyupdates.
This theorem follows from the fact that for any target identity
ID_{i}
, public key
upk_{IDi}
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 1024bit RSA in Li
et al
.’s pairingbased scheme, a Tate pairing defining on the supersingular elliptic curve
E
/
_{p}
:
y
^{2}
=
x
^{3}
+
x
is adopted. Here, the embedding degree of curve
E
/
_{p}
is 2,
q
= 2
^{159}
+ 2
^{17}
+1 refers to a 160bit Solinas prime, and
p
= 12
qr
 1 is a 512bit prime. To achieve the similar level of security for our pairingfree approach, the Koblitz elliptic curve
y
^{2}
=
x
^{3}
+
ax
^{2}
+
b
defined on
_{2163}
can be used. Here,
a
= 11 and
b
is a randomly chosen prime with the length of 163bit. 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
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 pairingbased 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
Performance comparisons with existing work
5. Conclusion
In this paper, a pairingfree 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 resourcelimited 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.
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 publickey 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”
SpringerVerlag
Advances in CryptologyCRYPTO 1984
1984
LNCS 196
10 
18
Boneh D.
,
Lynn B.
,
Shacham H.
“Short signatures from the weil pairing”
SpringerVerlag
Advances in Cryptology ASIACRYPT 2001
2001
LNCS 2248
514 
532
Shamir A.
“Identitybased cryptosystems and signature schemes”
SpringerVerlag
Advances in CryptologyCRYPTO 1984
1984
LNCS 196
47 
53
Hess F.
“Efficient identity based signature schemes based on pairings”
SpringerVerlag
Selected Areas in CryptographySAC 2002
2003
LNCS 2595
310 
324
Paterson K. G.
2002
“IDbased 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 IdentityBased Identification and Signature Schemes”
Journal of Cryptology
22
(1)
1 
61
DOI : 10.1007/s0014500890288
Gentry C.
“Certificatebased encryption and the certificate revocation problem”
SpringerVerlag
Advances in Cryptology EUROCRYPT 2003
2003
LNCS 2656
272 
293
Kang B. G.
,
Park J. H.
,
Hahn S. G.
“A certificatebased signature scheme,”
SpringerVerlag
in Proc. of Topics in CryptologyCTRSA 2004, The Cryptographers’ Track at the RSA Conference 2004
2004
LNCS 2964
99 
111
Joseph K.
,
Liu J. B.
,
Willy S.
,
Zhou J.
“CertificateBased Signature Schemes without Pairings or Random Oracles”
SpringerVerlag
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.
“Certificatebased signature: Security model and efficient construction”
SpringerVerlag
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 certificatebased 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 certificatebased 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.
“Keyinsulated public key cryptosystems”
SpringerVerlag
in Advances in Cryptology Eurocrypt’02
2002
LNCS 2332
65 
82
Dodis Y.
,
Katz J.
,
Xu S.
,
Yung M.
“Strong keyinsulated signature scheme”
SpringerVerlag
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 Certificatebased KeyInsulated 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”
SpringerVerlag
Berlin
Advances in CryptologyASIACRYPT 2011
2011
LNCS 7073
647 
666
Chen L.
,
Cheng Z.
,
Smart N. P.
2007
“Identitybased key agreement protocols from pairings”
International Journal of Information Security
6
(4)
213 
241
DOI : 10.1007/s1020700600119
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.
“IdentityBased KeyInsulated Signature with Secure KeyUpdates”
SpringerVerlag
in Proc. of 2nd SKLOIS Conference on Information Security and CryptologyInscrypt 2006
2006
LNCS 4318
13 
26
Zhou Y.
,
Cao Z.
,
Chai Z.
“Identity based key insulated signature”
SpringerVerlag
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 pairingfree identitybased 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