Key exposure is a major threat to secure cryptosystems. To mitigate the impact caused by keycompromise attacks, a keyinsulated cryptographic mechanism is a better alternative. For securing the large message communication in peertopeer networks, in this paper, we propose the first novel identitybased keyinsulated encryption (IBKIE) scheme with message linkages. Our scheme has the properties of unbounded time periods and randomaccess keyupdates. In the proposed scheme, each client can periodically update his private key while the corresponding public one remains unchanged. The essential security assumption of our proposed scheme is based on the wellknown bilinear DiffieHellman problem (BDHP). To ensure the practical feasibility, we also formally prove that the proposed scheme achieves the security requirement of confidentiality against indistinguishability under adaptive chosenciphertext attacks (INDCCA2) in the random oracle model.
1. Introduction
T
he first public key cryptosystem was introduced by Diffie and Hellman
[1]
in 1976. In such a system, each user has a selfchosen private key and a corresponding public one. Two important techniques, the public key encryption and the digital signature scheme
[2

4]
, are commonly adopted for ensuring the properties of integrity, confidentiality
[5]
, authenticity
[6]
and nonrepudiation
[7]
. In 1984, Shamir
[8]
proposed an identitybased system in which each user’s public key is explicitly his own identity information (such as the name and email address, etc.) while the corresponding private key is computed by a private key generation center (PKG). The derived private key is then sent to each user via a secure channel. Compared with the traditional public key system, an identitybased system is unnecessary to maintain public key certificates. Yet, in practice the key exposure is a major threat to system security and it sometimes imposes extra burdens to reset the whole system again.
To deal with the issue of key exposure, in 2002, Dodis
et al
.
[9]
proposed a keyinsulated cryptosystem in which each user has a longterm private key and a shortterm one, respectively. The former is stored in a physicallysecure but computation limited device (called base or helper) while the latter is kept secret by the user. The general idea of keyinsulated systems is that at different time periods each user can periodically update his shortterm private key with the assistance of helper while the corresponding public key remains unchanged. The next year, they
[10]
further presented the notion of strongly keyinsulated systems, i.e., even if the helper is corrupted by a malicious adversary, he cannot perform any operation with respect to the user’s private key.
Considering identitybased systems, in 2005, Hanaoka
et al
.
[11]
proposed the first identitybased keyinsulated system from bilinear maps. They also showed how to construct a partially collusion resistant hierarchical identitybased encryption (HIBEI) from arbitrary IBE in the random oracle model. In 2006, Zhou
et al
.
[12]
proposed an identitybased keyinsulated signature scheme based on the computational DiffieHellman (CDH) problem. The formal security proof is also realized in the random oracle model. Later, Hanaoka
et al
.
[13]
proposed a parallel keyinsulated public key encryption scheme in which two independent helpers are involved for updating user’s private keys alternatively. Such a mechanism helps with reducing the possibility of helper exposure and increasing the security of helpers. In 2008, Weng
et al
.
[14]
addressed an identitybased (
k
,
n
) threshold keyinsulated encryption scheme in which at least
k
out of
n
helpers are sufficient to update the user’s shortterm private key. Besides, the security of their scheme is proved in the standard model. For facilitating the delegation operation in an organization, in 2009, Wan
et al
.
[15]
proposed a strongly identitybased keyinsulated proxy signature scheme with secure keyupdates. Their scheme also supports unbounded time periods and randomaccess keyupdates. Recently, Yu
et al
.
[16]
proposed a new identitybased keyinsulated signature scheme and applied it to a novel application called full delegation proxy signature scheme with time restriction. Their scheme has the advantages of efficient keyupdate procedures and low computational costs for the verifier.
In a peertopeer network, each computer is served as both a server and a client. With an adhoc manner, communications can be directly established by two end computers. Consider the real situation that the communication message in a peertopeer file transmission system might be large. It therefore causes the difficulty in encrypting such a large plaintext due to the limited system bandwidth. Furthermore, in an identitybased system, the key exposure attack is considered the most serious one, as the corresponding user identity has to be removed from the system. Although previous mentioned works
[11

16]
have addressed some solutions using keyinsulted systems, their schemes are not suitable for large file transmission in peertopeer networks. It thus can be seen that extending the capability of current IBKIE scheme for facilitating the peertopeer file transmission system is vital. In this paper, we propose the first identitybased keyinsulated encryption (IBKIE) scheme with message linkages. In our scheme, we first divide a large plaintext into lots of smaller message blocks and then encrypt them, respectively. Each ciphertext of message blocks is chained with its preceding one using a collisionresistant oneway hash function and the exclusiveOR operation. The bilinear computation is only employed to derive the mutual shared private key, rather than chaining all ciphertext blocks. Consequently, the number of required pairing operations remains a constant when the message blocks increase. The division of large files not only benefits the encryption process with limited system bandwidth, but also reduces the retransmission overheads in case of some erroneous blocks. In a peertopeer file transmission system, the division of large files enables a client to simultaneously download blocks from one peer and upload previously received blocks to another, as so to save the overall transmission time. The gains obtained through our proposed scheme include lower computational efforts (compared with previous works) and the capability of large file transmission. With our proposed scheme, the impact of key exposure can be minimized and two end computers can encrypt and transfer a large plaintext without increasing extra computational costs, i.e., only one mutual shared private key will be generated for transmitting multiple blocks in one communication session. Additionally, the formal security proof of confidentiality against indistinguishability under adaptive chosenciphertext attacks (INDCCA2) is presented in the random oracle model.
The rest of this paper is organized as follows. Section 2 states some preliminaries. We introduce the proposed IBKIE scheme with message linkages in Section 3. The security proof is detailed in Section 4. Finally, a conclusion is made in Section 5.
2. Preliminaries
In this section, we briefly review some security notions and the computational assumptions. The proposed scheme is based on the bilinear pairing from elliptic curve systems. A commonly adopted security assumption comes from the Bilinear DiffieHellman problem (BDHP). We state the basic operations of bilinear pairing and the BDH assumption below:
 Bilinear Pairing
Let (
G
_{1}
, +) and (
G
_{2}
, ×) denote two groups of the same prime order
q
and
e
:
G
_{1}
×
G
_{1}
→
G
_{2}
be a bilinear map which satisfies the following properties:
(i)
Bilinearity:
e
(
P
_{1}
+
P
_{2}
,
Q
) =
e
(
P
_{1}
,
Q
)
e
(
P
_{2}
,
Q
);
e
(
P
,
Q
_{1}
+
Q
_{2}
) =
e
(
P
,
Q
_{1}
)
e
(
P
,
Q
_{2}
);
(ii)
Nondegeneracy:
If
P
is a generator of
G
_{1}
,
e
(
P
,
P
) is a generator of
G
_{2}
.
(iii)
Computability:
Given
P
,
Q
∈
G
_{1}
, the value of
e
(
P
,
Q
) can be efficiently computed by a polynomialtime algorithm.
 Bilinear DiffieHellman Problem; BDHP
The BDHP is, given an instance (
P
,
A
,
B
,
C
) ∈
G
_{1}
^{4}
where
P
is a generator,
A
=
aP
,
B
=
bP
and
C
=
cP
for some
a, b, c
∈
Z_{q}
, to compute
e
(
P
,
P
)
^{abc}
∈
G
_{2}
.
 Bilinear DiffieHellman (BDH) Assumption
For every probabilistic polynomialtime algorithm
A
, every positive polynomial
Q
(·) and all sufficiently large
k
, the algorithm
A
can solve the BDHP with an advantage at most 1/
Q
(
k
), i.e.,
Pr[
A
(
P
,
aP
,
bP
,
cP
) =
e
(
P
,
P
)
^{abc}
;
a
,
b
,
c
←
Z_{q}
, (
P
,
aP
,
bP
,
cP
) ←
G
_{1}
^{4}
] ≤ 1/
Q
(
k
).
The probability is taken over the uniformly and independently chosen instance and over the random choices of
A
.
Definition 1.
The
(
t
,
ε
)
BDH assumption holds if there is no polynomialtime adversary that can solve the BDHP in time at most t and with the advantage ε
.
3. Proposed IBKIE Scheme with Message Linkages
In this section, we first address involved parties and algorithms of our proposed scheme and then give concrete constructions. Some performance analyses with previous works are also demonstrated.
 3.1 Involved Parties
An IBKIE scheme has four involved parties: a private key generation center (PKG), a helper (device) and two communication clients. Each one is a Probabilistic Polynomialtime Turing Machine (PPTM). The PKG is responsible for generating each user’s initial private key and a master helper key. Each client can periodically update his
i
th private key at time period
i
with the assistance of his helper.
 3.2 Algorithms
The proposed IBKIE scheme consists of the following algorithms:
–
Setup:
Taking as input 1
^{k}
where
k
is a security parameter, the PKG generates system’s public parameters
params
and a master helper key.
–
KeyExtract (KE):
The KE algorithm takes as input the system parameters
params
, an identity
ID
, the master secret key of PKG. It generates an initial private key
S
_{ID, 0}
with respect to the identity
ID
.
–
KeyUpdate (KU):
The KU algorithm takes as input the system parameters
params
, a time period
i
, a helper key
HK_{ID,i}
and a private key
S
_{ID, i1}
. It generates a private key
S
_{ID,i}
for the time period
i
.
–
Encryption (Enc):
The Enc algorithm takes as input the system parameters
params
, a time period
i
, a plaintext and the identity of receiver. It generates a corresponding ciphertext
δ
.
–
Decryption (Dec):
The Dec algorithm takes as input the system parameters
params
, a ciphertext
δ
and the private key of receiver. It outputs the recovered plaintext or an error symbol ⊥.
 3.3 Basic Construction of IBKIE Scheme
Motivated by Wan
et al
.’s
[15]
and Yu
et al
.’s
[16]
schemes, in this subsection, we first give a basic construction of our IBKIE scheme without message linkages. Details of each algorithm are described below:
–
Setup:
Taking as input 1
^{k}
, the private key generation center (PKG) chooses a master secret key
s
∈
_{R}
Z_{q}
along with a master helper key
w
∈
_{R}
Z_{q}
, and then computes the corresponding public keys
P_{TA}
=
sP
and
P_{HK}
=
wP
, respectively. The master helper key
w
is sent to the helper via a secure channel. The PKG also selects two groups (
G
_{1}
, +) and (
G
_{2}
, ×) of the same prime order
q
where 
q
 =
k
. Let
P
be a generator of order
q
over
G
_{1}
,
e
:
G
_{1}
×
G
_{1}
→
G
_{2}
a bilinear pairing,
H
: {0, 1}
^{k}
→
G
_{1}
and
F
:
G
_{1}
×
G
_{2}
→
Z_{q}
collision resistant hash functions. The PKG announces public parameters
params
= {
P_{TA}
,
P_{HK}
,
G
_{1}
,
G
_{2}
,
q
,
P
,
e
,
H
,
F
}.
–
KeyExtract (KE):
Given an identity, say
ID_{A}
of the client Alice, the PKG computes the initial private key as
and then returns it to Alice via a secure channel.
–
KeyUpdate (KU):
Given an identity
ID_{A}
and a time period
i
∈ {1, …,
N
}, the helper first generates a helper key as
and then sends it to Alice who can therefore update her private key by computing
The values (
S
_{A,i1}
,
HK_{A,i}
) are deleted subsequently.
–
Encryption (Enc):
At time period
i
∈ {1, …,
N
}, to encrypt a plaintext
M
for Alice, a sender first chooses
t
∈
_{R}
Z_{q}
and then computes
The ciphertext is
δ
= (
i
,
T
,
C
) which is then delivered to Alice.
–
Decryption (Dec):
Upon receiving the ciphertext
δ
= (
i
,
T
,
C
), Alice decrypts it with her private key
S_{A, i}
at time period
i
∈ {1, …,
N
} by computing
If the recovered redundancy in
M
is valid, Alice accepts the plaintext. Otherwise, an error symbol ⊥ is returned to signal that
δ
is invalid. We show that Eq. (7) works correctly. From the righthand side of Eq. (7), we have
which leads to the lefthand side of Eq. (7).
 3.4 Construction of IBKIE Scheme with Message Linkages
Based on our basic IBKIE scheme, we introduce an IBKIE scheme with message linkages to benefit the encryption of a large plaintext by dividing it into lots of small blocks. Let
F
_{1}
:
Z_{q}
→
Z_{q}
be a collision resistant hash function. The construction is similar as our basic IBKIE scheme stated in Section 3.3. We only describe the different parts as follows:
–
Encryption (Enc):
At time period
i
∈ {1, …,
N
}, to encrypt a large plaintext
M
for Alice, a sender first divides
M
into
l
pieces, i.e.,
M
=
M
_{1}
║
M
_{2}
║ … ║
M_{l}
,
M_{r}
’s ∈
Z_{q}
, and then chooses
t
∈
_{R}
Z_{q}
and
C
_{0}
= 0 to compute (
T
,
σ
) as Eqs. (4) and (5). The sender further computes
The ciphertext is
δ
= (
i
,
T
,
C
_{1}
,
C
_{2}
, …,
C_{l}
) which is then delivered to Alice.
–
Decryption (Dec):
Upon receiving
δ
= (
i
,
T
,
C
_{1}
,
C
_{2}
, …,
C_{l}
), Alice first decrypts it with her private key
S_{A}
,
_{i}
at time period
i
∈ {1, …,
N
} by computing
and then recovers the original plaintext
M
as
M
_{1}
║
M
_{2}
║ … ║
M_{l}
. If the recovered redundancy in
M
is valid, Alice accepts the plaintext. Otherwise, an error symbol ⊥ is returned to signal that
δ
is invalid.
We show that Alice can recover
M
with her private key by Eq. (7*). From the righthand side of Eq. (7*), we have
Which leas to the lefthand side of Eq.(7*).
 3.5 Performance Analyses
In a pairingbased IBKIE scheme, it will incur more computational efforts to extend such an algorithm to the scheme with message linkages when the encrypted message is tightly combined with the pairing computation. For example, the pairing computation of Hanaoka
et al
.’s scheme
[11]
takes as input the encrypted message. When we extend their algorithm to the scheme with message linkages by our construction, a sender has to employ the pairing operation for chaining all ciphertext blocks. That is to say, the number of bilinear pairing will be proportional to that of message blocks. Yet, in our proposed scheme, the bilinear computation is only adopted to derive the mutual shared private key.
Table 1
demonstrates the efficiency comparisons among the proposed and previous works including Hanaoka
et al
.’s
[11]
(HHS for short) and Weng
et al
.’s
[14]
(WLC for short) schemes in terms of the number of required pairing computation which is considered the most timeconsuming operation. It can be seen that both HHS and WLC schemes incur more computational efforts as the message blocks increase while ours remains a constant, i.e., 3.
Comparisons of required pairing computation
Comparisons of required pairing computation
4. Security Proof
In this section, we define the crucial security requirement of our proposed IBKIE scheme and prove it in the random oracle model. Since our IBKIE scheme with message linkages has almost the same structures as those in the basic scheme, it is sufficient to show the security of our basic scheme. The security of the proposed IBKIE scheme with message linkages is directly implied by it.
 4.1 Security Requirement
The crucial security requirement of proposed IBKIE scheme is confidentiality against indistinguishability under adaptive chosenciphertext attacks (INDCCA2). We define the notion as follows:
Definition 2.
An IBKIE scheme is said to achieve the security requirement of confidentiality against indistinguishability under adaptive chosenciphertext attacks (INDCCA2) if there is no probabilistic polynomialtime adversary A with nonnegligible advantage in the following game played with a challenger B
:
Setup:
B
first runs the Setup(1
^{k}
) algorithm and sends the system’s public parameters
params
to the adversary
A
.
Phase 1:
The adversary
A
can issue several queries adaptively, i.e., each query might be based on the result of previous queries:
–
KeyExtract (KE) queries
:
A
makes a KE query for some identity
ID
.
B
returns the initial private key
S
_{ID, 0}
.
–
HelperKeye (HK) queries
:
A
makes an HK query for some identity
ID
and the time period
i
∈ {1, …,
N
}.
B
returns the corresponding helper key
HK_{ID,i}
.
–
KeyUpdate (KU) queries
:
A
makes a KU query for some identity
ID
and the time period
i
∈ {1, …,
N
}.
B
returns the corresponding private key
S_{ID,i}
.
–
Encryption (Enc) queries
:
A
makes an Enc query for a plaintext
M
, a time period
i
∈ {1, …,
N
} and an identity
ID
.
B
returns the corresponding ciphertext
δ
to
A
.
–
Decryption (Dec) queries
:
A
makes a Dec query for a ciphertext
δ
with respect to an identity
ID
. If the decrypted plaintext has correct redundancy,
B
returns it. Otherwise, an error symbol ⊥ is returned as a result.
Challenge:
The adversary
A
produces two messages,
M
_{0}
and
M
_{1}
, of the same length and chooses a fresh identity
ID
^{*}
along with a time period
i
^{*}
∈ {1, …,
N
}. The challenger
B
flips a coin
λ
← {0, 1} and generates a ciphertext
δ
^{*}
in relation to (
i
^{*}
,
M
_{λ}
,
ID
^{*}
). The ciphertext
δ
^{*}
is then delivered to
A
as a target challenge.
Phase 2:
The adversary
A
can issue new queries as those in Phase 1 except the KE(
ID
^{*}
), HK(
i
^{*}
,
ID
^{*}
), KU(
i
^{*}
,
ID
^{*}
) and Dec(
δ
^{*}
,
ID
^{*}
) queries.
Guess:
At the end of the game,
A
outputs a bit
λ
’. The adversary
A
wins this game if
λ
’=
λ
. We define
A
’s advantage as
Adv
(
A
) =  Pr[
λ
’=
λ
] − 1/2 .
 4.2 Security Proof
We prove that the proposed scheme achieves the INDCCA2 security in the random oracle model as Theorem 1.
Theorem 1.
The proposed IBKIE scheme is
(
t
,
q_{H}
,
q_{F}
,
q_{KE}
,
q_{HK}
,
q_{KU}
,
q_{Enc}
,
q_{Dec}
,
ε
)
secure against indistinguishability under adaptive chosenciphertext attacks
(
INDCCA2
)
in the random oracle model if there is no probabilistic polynomialtime adversary that can
(
t
',
ε
')
break the BDHP
,
where
Here N is the number of total time periods and
t_{λ}
is the time for performing one bilinear pairing operation
.
The proof structure of Theorem 1
Proof
:
Fig. 1
depicts the proof structure of this theorem. Suppose that a probabilistic polynomialtime adversary
A
can (
t
,
q_{H}
,
q_{F}
,
q_{KE}
,
q_{HK}
,
q_{KU}
,
q_{Enc}
,
q_{Dec}
,
ε
)break the proposed IBKIE scheme with nonnegligible advantage
ε
under adaptive chosen ciphertext attacks after running at most
t
steps and making at most
q_{H}
H
,
q_{F}
F
,
q_{KE}
KE,
q_{HK}
HK,
q_{KU}
KU,
q_{Enc}
Enc and
q_{Dec}
Dec queries. Then we can construct another algorithm
B
that (
t
',
ε
')breaks the BDHP by taking
A
as a subroutine. The objective of
B
is to obtain
e
(
P
,
P
)
^{xyz}
by taking (
P
,
xP
,
yP
,
zP
) as inputs. In this proof,
B
simulates a challenger to
A
in the following game.
Setup:
The challenger
B
runs the Setup(1
^{k}
) algorithm to obtain the system’s public parameters
params
= {
G
_{1}
,
G
_{2}
,
q
,
P
,
e
}. Then
B
sets
P_{TA}
=
xP
and
P_{HK}
=
dP
where
d
∈
_{R}
Z_{q}
. After that,
B
returns (
params
,
P_{TA}
,
P_{HK}
) to the adversary
A
.
Phase 1:
A
makes the following queries adaptively:
–
H oracle:
When
A
queries an
H
oracle of
H
(
ID_{j}
),
B
first checks H_list for a matched entry. Otherwise,
B
chooses
h_{j}
∈
_{R}
Z_{q}
, adds the entry (
ID_{j}
,
h_{j}
,
h_{j}P
) to H_list, and returns
h_{j}P
as a result.
–
F oracle:
When
A
queries an
F
oracle of
F
(
T_{j}
,
σ_{j}
),
B
first checks F_list for a matched entry. Otherwise,
B
chooses
f_{j}
∈
_{R}
Z_{q}
and adds the entry (
T_{j}
,
σ_{j}
,
f_{j}
) to F_list. Finally,
B
returns
f_{j}
as a result.
–
KE queries:
When
A
makes a KE query for
ID_{j}
,
B
returns the initial private key
S
_{j, 0}
=
h_{j}
(
xP
) +
(
h_{j}
,
_{0}
P
) to
A
.
–
HK queries:
When
A
makes an HK query for (
i
,
ID_{j}
) where
i
∈ {1, …,
N
} is the time period,
B
returns the helper key
HK_{j,i}
=
d
[
H
(
ID_{j}
,
i
) 
H
(
ID_{j}
,
i
1)] to
A
.
–
KU queries:
When
A
makes a KU query for (
i
,
ID_{j}
) where
i
∈ {1, …,
N
} is the time period,
B
returns the corresponding private key
S_{j,i}
=
h_{j}
(
xP
) +
d
(
h_{j}
,
_{i}P
) to
A
.
–
Enc queries:
When
A
makes an Enc query with respect to (
i
,
M
,
ID
) where
i
∈ {1, …,
N
} is the time period,
B
follows the steps in Section 3.3 to return the ciphertext
δ
= (
i
,
T
,
C
).
–
Dec queries:
When
A
makes a Dec query for some pair (
ID_{j}
,
δ
= (
i
,
T
,
C
)) where
δ
= (
i
,
T
,
C
),
B
first derives the private key
S_{j,i}
=
h_{j}
(
xP
) +
d
(
h_{j}
,
_{i}P
) to run the Decryption algorithm in Section 3.3 and then returns the corresponding result.
Challenge:
The adversary
A
produces two messages,
M
_{0}
and
M
_{1}
, of the same length and chooses a fresh identity
ID
^{*}
along with a time period
i
^{*}
∈ {1, …,
N
}. The challenger
B
flips a coin
λ
← {0, 1} and generates a ciphertext
δ
^{*}
in relation to (
i
^{*}
,
M_{λ}
,
ID
^{*}
) as follows:

Step 1 Add the entry (ID*, null,yP) to H_list, i.e., implicitly defineH(ID*) =yPwhereyis unknown toB.

Step 2 SetT*=zP;

Step 3 Choosef*∈RZqand add the entry (T*, null,f*) to F_list, i.e., implicitly defineF(T*,σ*) =f*whereσ*is unknown toB.

Step 4 ComputeC*=Mλ·f*.
The ciphertext
δ
^{*}
= (
i
^{*}
,
T
^{*}
,
C
^{*}
) is then delivered to
A
as a target challenge.
Phase 2:
A
makes new queries as those stated in Phase 1 except the KE(
ID
^{*}
), HK(
i
^{*}
,
ID
^{*}
), KU(
i
^{*}
,
ID
^{*}
) and Dec(
δ
^{*}
,
ID
^{*}
) queries. When A makes a KU query for (
i
,
ID
*) where
i
∈ {1, …,
i
^{*}
1,
i
^{*}
+ 1, …,
N
},
B
directly terminates. When
A
makes a Dec query for some pair (
ID
^{*}
,
δ
) where
δ
= (
i
,
T
,
C
),
B
searches F_list for a matched entry (
T_{j}
,
δ_{j}
,
f_{j}
) where
T_{j}
=
T
and then returns
M
=
C
·
f_{j}
^{1}
to
A
. Otherwise, an error symbol ⊥ is returned as a result.
δ
^{*}
Analysis of the game:
We first evaluate the simulation of Dec queries. One can observe that it is possible for a Dec query of some valid pair (
ID
^{*}
,
δ
) where
δ
= (
i
,
T
,
C
) to return the error symbol ⊥ on condition that
A
doesn’t query the corresponding
F
(
T
,
σ
) random oracle. However, such the probability for any Dec query is not greater than 2
^{k}
. Since
A
is allowed to make at most
q_{Dec}
Dec queries, the above situation happens during the entire simulation game, denoted by Dec_ERR, would be less than (
q_{Dec}
)2
^{k}
, i.e., Pr[Dec_ERR]≤(
q_{Dec}
)2
^{k}
. Also note that
B
terminates for some KU queries with respect to (
i
,
ID
^{*}
) where
i
∈ {1, …,
i
^{*}
1,
i
^{*}
+ 1, …,
N
}. We express such an event during the entire simulation game as KU_ERR and Pr[KU_ERR]≤(
N
1)(
q_{KU}
)
^{1}
. Additionally, in the challenge phase,
B
has returned a simulated ciphertext
δ
^{*}
= (
i
^{*}
,
T
^{*}
,
C
^{*}
) where
H
(
ID
^{*}
) =
yP
and
T
^{*}
=
zP
, which implies the parameter
σ
^{*}
is implicitly defined as
Let NA be the event that the entire simulation game does not abort. Obviously, if the adversary
A
never asks an
F
(
T
^{*}
,
σ
^{*}
) oracle query in Phase 2, the entire simulation game could be normally terminated. We denote the event that
A
does ask such an oracle query in Phase 2 by QF*. When the entire simulation game does not abort, it can be seen
A
gains no advantage in guessing
λ
due to the randomness of random oracles, i.e.,
Rewriting the expression of Pr[
λ
’=
λ
], we have
On the other hand, we can also derive that
With inequalities (9) and (10), we know that
Recall that in Definition 2,
A
’s advantage is defined as
Adv
(
A
) =  Pr[
λ
’=
λ
] − 1/2 . By assumption,
A
has nonnegligible probability
ε
to break the proposed scheme. We therefore have
Rewriting the above inequality, we get
If the event QF* happens, we claim that
σ
^{*}
=
e
(
P
,
P
)
^{xyz}
e
(
dP
, (
h
^{*}
,
_{i*}
)(
zP
)) will be left in some entry of F_list. Consequently,
B
has nonnegligible probability
to solve the BDHP by computing
e
(
dP
, (
h
^{*}
,
_{i*}
)(
zP
))
^{1}
σ
^{*}
. The computational time required for
B
is
t
'≈
t
+
t_{λ}
(2
q_{Enc}
+
q_{Dec}
).
Q.E.D.
5. Conclusions
Keyinsulated cryptosystems aim at reducing the damage caused by the key exposure. In this paper, we combine identitybased and keyinsulated systems to propose the first novel IBKIE scheme with message linkages for facilitating the encryption of a large plaintext in peertopeer communication networks. In addition to the inherent property of keyinsulated systems that each client can periodically update his private key while the public one remains unchanged, the proposed scheme also supports unbounded time periods and randomaccess keyupdates. By integrating with identitybased systems, it is unnecessary to maintain public key certificates. The underlining computational assumption of our scheme is based on the wellknown bilinear DiffieHellman problem (BDHP) which is believed to be no harder than the computational DiffieHellman (CDH) problem and is intractable in polynomial time. Furthermore, the security requirement of confidentiality against indistinguishability under adaptive chosenciphertext attacks (INDCCA2) is realized in the random oracle model. Our proposed scheme is also suitable for the encryption and transmission of DNA/RNA biological sequences and the data structure such as linked list. In the future research, we will attempt to develop an enhanced variant with error correction capability. That is, the receiving client can identify the erroneous ciphertext blocks during the transmission and request to resend only these blocks again, rather than all ones, which helps gain more bandwidth saving.
Acknowledgements
We would like to thank anonymous referees for their valuable suggestions. We thank Healthy Aging Research Center (HARC) of Chang Gung University for excellent technical assistance. This work was supported in part by the Chang Gung University Grant UARPD3B0061 and in part by the National Science Council of Republic of China under the contract numbers NSC 1002628H182001MY3 and NSC 1022221E019041.
BIO
ChienLung Hsu is a professor and the Chairman of Information Management Department at Chang Gung University (CGU), in Taiwan from August 2011. He was an Associate Professor and an Assistant Professor in the Department of Information Management of Chang Gung University from 2007 to 2011 and 2004 to 2007, respectively. He received a B.S. degree in business administration, an M.S. degree in information management, and a Ph.D. degree in information management from the National Taiwan University of Science and Technology, Taiwan in 1995, 1997, and 2002, respectively. He is also the director of the Ubiquitous Security and Applications Lab, the director of Chinese Cryptology & Information Security Association, the chair of Program of RFID Applications in Logistics Supply Chain Management of CGU, the chair of Program of Information Security with Medical Applications of CGU, the director of Division of Instructional Support of Computer Center of CGU, the researcher of Healthy Aging Research Center (HARC) of CGU, the researcher of Elder Industry Development and Research Center (EIDRC) of CGU, and the senior researcher of Taiwan Information Security Center (TWISC). His current research includes cryptography, information security, wireless sensor network, mobile commerce, digital forensics, vehicular system security, healthcare system and user acceptance, smart home system, etc.
HanYu Lin received his Ph.D. degree in computer science and engineering from the National Chiao Tung University, Taiwan in 2010. He served as a parttime Assistant Professor in both the Department of Information Management, Chang Gung University, Taiwan and the Department of Information Management, Kainan University, Taiwan from 2011. He was an engineer in CyberTrust Technology Institute, Institute for Information Industry, Taiwan from January 2012 to July 2012. Since August 2012, he has been an Assistant Professor in the Department of Computer Science and Engineering, National Taiwan Ocean University, Taiwan. His research interests include Cryptology, Network Security, Digital Forensics, RFID Privacy and Application, Cloud Computing Security and Ecommerce Security.
Diffie W.
,
Hellman M.
1976
“New directions in cryptography”
IEEE Transactions on Information Theory
IT22
(6)
644 
654
DOI : 10.1109/TIT.1976.1055638
ElGamal T.
1985
“A public key cryptosystem and a signature scheme based on discrete logarithms,”
IEEE Transactions on Information Theory
IT31
(4)
469 
472
DOI : 10.1109/TIT.1985.1057074
Rivest R.
,
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
Schnorr C. P.
1991
“Efficient signature generation by smart cards”
Journal of Cryptology
4
(3)
161 
174
DOI : 10.1007/BF00196725
Delfs H.
,
Knebl H.
2002
Introduction to Cryptography: Principles and Applications
Springer
Stallings W.
2005
Cryptography and Network Security: Principles and Practices
4th. Ed.
Pearson
Meng B.
,
Wang S.
,
Xiong Q.
2002
“A fair nonrepudiation protocol”
in Proc. of the 7th International Conference on Computer Supported Cooperative Work in Design (CSCW’02)
Brazil
68 
73
Shamir A.
1984
“Identitybased cryptosystems and signature schemes”
Advances in Cryptology CRYPTO’84, SpringerVerlag
SpringerVerlag
47 
53
Dodis Y.
,
Katz J.
,
Xu S.
,
Yung M.
2002
“Keyinsulated public key cryptosystems,” Advances in Cryptology − EUROCRYPT’02
SpringerVerlag
65 
82
Dodis Y.
,
Katz J.
,
Xu S.
,
Yung M.
2003
“Strong keyinsulated signature schemes”
SpringerVerlag
in Proc. of Public Key Cryptography 2003 (PKC’03), LNCS 2567
130 
144
Hanaoka Y.
,
Hanaoka G.
,
Shikata J.
,
Imai H.
2005
“Identitybased hierarchical strongly keyinsulated encryption and its application,” Advances in Cryptology ASIACRYPT’05
SpringerVerlag
495 
514
DOI : 10.1007/11593447_27
Zhou Y.
,
Cao Z.
,
Chai Z.
2006
“Identity based key insulated signature”
in Proc. of ISPEC 2006, LNCS 3903
226 
234
DOI : 10.1007/11689522_21
Hanaoka G.
,
Hanaoka Y.
,
Imai H.
2006
“Parallel keyinsulated public key encryption”
in Proc. of Public Key Cryptography 2006 (PKC’06), LNCS 3958
105 
122
DOI : 10.1007/11745853_8
Weng J.
,
Liu S.
,
Chen K.
,
Zheng D.
,
Qiu W.
2008
“Identitybased threshold keyinsulated encryption without random oracles”
in Proc. of CTRSA 2008, LNCS 4964
203 
220
DOI : 10.1007/9783540792635_13
Wan Z.
,
Lai X.
,
Weng J.
,
Liu S.
,
Hong X.
2009
“Identitybased keyinsulated proxy signature”
Journal of Electronics
26
(6)
853 
858
DOI : 10.1007/s1176700801282
Yu C. W.
,
Tseng Y. M.
,
Wu T. Y.
2010
“A new keyinsulated signature and its novel application”
in Proc. of Cryptology and Information Security Conference (CISC 2010)
DOI : 10.1007/s1176700801282