# Certificateless Public Key Encryption Scheme with Hybrid Problems and Its Application to Internet of Things

Authors: Rui Guo; Qiaoyan Wen; Huixian Shi; Zhengping Jin; Hua Zhang
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Certificateless cryptography aims at combining the advantages of public key cryptography and identity based cryptography to avoid the certificate management and the key escrow problem. In this paper, we present a novel certificateless public key encryption scheme on the elliptic curve over the ring, whose
security is based on the hardness assumption of Bilinear Diffie-Hellman problem and factoring the large number as in an RSA protocol. Moreover, since our scheme requires only one pairing operation in decryption, it is significantly more efficient than other related schemes. In addition, based on our encryption system, we
also propose a protocol to protect the confidentiality and integrity of information in the scenario of Internet of Things with constrained resource nodes.


---

## Body

## 1. Introduction

In a traditional public key cryptography (PKC) scheme, public key certificates signed by a certificate authority (CA) are employed to ensure the authenticity of public keys. Thus, the PKC takes a huge effort to manage the certificates, including revocation, storage, distribution, and verification, which places a computational burden on the whole system. To simplify the complex certificate management process, Shamir proposed the concept of identity-based public key cryptography (ID-PKC) [1], where an entity is allowed to use his identity such as email and IP address as his public key. However, the private keys of users are totally generated by a trusted third party named private key generator (PKG), which enables the PKG to impersonate any user to recover his/her confidential messages.In order to resolve the inherent key escrow problem while preserving the advantage of ID-PKC, Al-Riyami and Paterson [2] introduced a new paradigm called certificateless public key cryptography (CL-PKC), which does not require the management of certificates and resolve the key escrow problem. Specifically, in CL-PKC, there also exists a trusted third party called key generation center (KGC) which supplies a partial private key for entity. Then, the entity takes advantage of this partial private key and a secret value picked by itself to generate the full private key. According to this method, KGC cannot obtain the user’s private key to decrypt his/her ciphertext anymore, and it avoids the escrow problem in ID-PKC. Therefore, CL-PKC is considered as lying in between PKC and ID-PKC. However, it should be emphasized that so far certificateless public key encryption (CL-PKE) schemes have been constructed within the framework of identity-based encryption (IBE) schemes from Weil pairing proposed by Boneh and Franklin [3]. As a result, the CL-PKE schemes in the literature are always based on the bilinear pairings.Recently, the pairings, such as Weil pairing and Tate pairing, have been of essential use in CL-PKE, because of the excellent properties of bilinearity and nondegeneracy [4–7]. The central idea is the construction of a mapping between two useful cryptographic groups that allow for new cryptographic schemes based on the reduction of one problem in one group to a different group and usually is easier problem than the other group. Therefore, the construction based on the bilinear pairing is more concise than the existing methods of cryptographic scheme constructions and it owns the merits of security. In Cheng and Comley’s scheme [4], they constructed a more efficient scheme and then extended it to an authenticated encryption. Shi and Li [5] proposed a CL-PKE scheme which was based on the Weil pairing. That scheme worked in a kind of parallel model and it was more efficient on computation. In [6], Dent et al. presented the first constructions for CL-PKE schemes that were provably secure against strong adversaries in the standard model. For raising efficiency, Sun and Li [7] proposed a short-ciphertext CCA2 secure certificateless encryption scheme under the standard bilinear Diffie-Hellman assumption. Due to short ciphertext and convincing security, their scheme had practical value.The Internet of Things (IoT) [8, 9] is a kind of network, which can connect everything to the Internet by using of the RFID, Infrared Sensors, GPS, Laser Scanner, Sensor Node, and other sensor equipments, thus possessing the ability of identifying, locating, tracking, monitoring, managing, and other intelligent actions. In IoT, it requires sensor nodes to be employed in unprotected and even hostile environments, and therefore IoT brings lots of research challenges; one of the important issues is the security [10, 11].In this paper, we employ use of the bilinear pairing to design a certificateless encryption scheme on the elliptic curves over the ringZ
n [12, 13], which overcomes the security defect of the Koyama et al.’s scheme [14] whose security is only based on the problem of factoring the large number as in RSA. Furthermore, we prove that our scheme is secure in the random oracle model, provided that the BDH assumption and the problem of factoring the large number are intractable. Comparing with the related CL-PKE schemes, our proposal offers better performances than others on the efficiency and security. At last, based on our CL-PKE scheme, we also present another protocol to protect the confidentiality and integrity of data transmitted between the gateway node and the sensor node in IoT.The remainder of this paper is organized as follows. In Section2, we introduce the preliminary concepts, including properties of the elliptic curve over the ring Z
n, the related computational problems, and the formal definition and security model of CL-PKE. In Section 3, we present our CL-PKE scheme and analyze the security and performance of it. Based on our CL-PKE, in Section 4, we propose a scheme to protect the confidentiality and integrity of information in the business of IoT. Finally, we conclude the paper in Section 5.


## 2. Preliminaries

In this section, we summarize the definitions and properties of elliptic curve over a ringZ
n
=
Z
/
n
Z, bilinear pairing, and models of CL-PKE, where n is a RSA modulus.


### 2.1. Elliptic Curve over the Ring

Definition 1.
LetF
q be a field and prime q
>
3; all the points (
x
,
y
)
∈
F
q
×
F
q satisfying the equation y
2
≡
x
3
+
a
x
+
b
(
mod
⁡
q
) compose the elliptic curve over F
q together with the point at infinity denoted 𝒪, where a
,
b
∈
F
q are two parameters satisfying 4
a
3
+
27
b
2
≠
0
(
mod
⁡
q
); such a curve is denoted by E
q
(
a
,
b
).The addition operation on the points ofE
q
(
a
,
b
) can be defined as follows.LetP
=
(
x
1
,
y
1
), Q
=
(
x
2
,
y
2
) be the points of E
q
(
a
,
b
); then -
P
=
(
x
1
,
-
y
1
).(a)
IfP
=
𝒪, then -
P
=
𝒪, and P
+
Q
=
Q;
(b)
ifQ
=
-
P, then P
+
Q
=
𝒪;
(c)
ifQ
≠
-
P, then P
+
Q
=
(
x
3
,
y
3
), where x
3
=
λ
2
-
x
1
-
x
2, y
3
=
λ
(
x
1
-
x
3
)
-
y
1, and
(1)
λ
=
{
y
2
-
y
1
x
2
-
x
1
,
if
P
≠
Q
,
3
x
1
2
+
a
2
y
1
,
if
P
=
Q
.From these definitions, we know the fact that the addition operation on the points ofE
q
(
a
,
b
) can be made as an Abelian group, where 𝒪 is the neutral element of E
q
(
a
,
b
).LetZ
n
=
Z
/
n
Z, where n
=
p
q is the product of two large primes as the RSA modulus. The Chinese Remainder Theorem says that there is an isomorphism of rings
(2)
Z
p
q
≃
Z
p
⊕
Z
q
given by
(3)
x
mod
⁡
p
q
⟷
(
x
mod
⁡
p
,
x
mod
⁡
q
)
.This yields a bijection between elements inZ
p
q and pairs of elements, one in Z
p and the other in Z
q. Thus, the following theorem can be given.Theorem 2.
Letp and q be odd integers with gcd
(
p
,
q
)
=
1; let E be an elliptic curve defined over Z
p
q. Then, there is a group isomorphism
(4)
E
(
Z
p
q
)
≃
E
(
Z
p
)
⊕
E
(
Z
q
)
.Therefore, there is an isomorphism mapping(5)
φ
:
E
(
Z
p
q
)
⟶
E
(
Z
p
)
⊕
E
(
Z
q
)
,
P
p
q
⟼
[
P
p
,
P
q
]
,
where P
p
q
∈
E
(
Z
p
q
), P
p
∈
E
(
Z
p
) and P
q
∈
E
(
Z
q
).LetQ
p
q
∈
E
(
Z
p
q
)
,
Q
p
∈
E
(
Z
p
) and Q
q
∈
E
(
Z
q
); we can get
(6)
φ
(
P
p
q
)
=
[
P
p
,
P
q
]
,
φ
(
Q
p
q
)
=
[
Q
p
,
Q
q
]
,
φ
(
P
p
q
+
Q
p
q
)
=
φ
(
P
p
q
)
+
φ
(
Q
p
q
)
=
[
P
p
,
P
q
]
+
[
Q
p
,
Q
q
]
=
[
P
p
+
Q
p
,
P
q
+
Q
q
]
.Becauseφ is an isomorphism mapping, there is an inverse mapping of it, denoted ψ. Thus,
(7)
ψ
(
φ
(
P
p
q
+
Q
p
q
)
)
=
P
p
q
+
Q
p
q
=
ψ
(
[
P
p
+
Q
p
,
P
q
+
Q
q
]
)
,
which means that the addition law on E
(
Z
p
q
) can be defined as an isomorphism mapping of the addition law in E
(
Z
p
) and E
(
Z
q
), with the convention that the infinity point 𝒪 of E
(
Z
p
q
) can be presented by [
𝒪
p
,
𝒪
q
], where 𝒪
p and 𝒪
q are the points at infinity on E
(
Z
p
) and E
(
Z
q
), respectively. Then, E
(
Z
p
q
) is an Abelian group under this definition of point addition.For more details concerning the addition law on elliptic curves over the ring, see [12, 13, 15]. Besides, there is an important theorem in constructing our CL-PKE over the ring as shown below.Theorem 3.
LetE
n
(
a
,
b
) be an elliptic curve such that gcd
(
4
a
3
+
27
b
2
,
n
)
=
1, n
=
p
q, and let N be lcm
(
♯
E
p
(
a
,
b
)
,
♯
E
q
(
a
,
b
)
). Then, for any P
∈
E
n
(
a
,
b
) and any integer k,
(8)
(
k
·
N
+
1
)
·
P
=
P
o
v
e
r
E
n
(
a
,
b
)
.


### 2.2. Bilinear Pairings

LetG
1 be a cyclic additive group generated by an elliptic curve point P, whose order is N; let G
2 be a multiplicative group of the same order. Assume that bilinear pairing is a map e
:
G
1
×
G
1
→
G
2 with the following properties.(1)
Bilinearity: for all X
,
Y
,
Z
∈
G
1, e
(
X
,
Y
+
Z
)
=
e
(
X
,
Y
)
·
e
(
X
,
Z
) and e
(
X
+
Y
,
Z
)
=
e
(
X
,
Z
)
·
e
(
Y
,
Z
). Consequently, ∀
a
,
b
∈
Z
q, we have e
(
a
X
,
b
Y
)
=
e
(
X
,
Y
)
a
b
=
e
(
a
b
X
,
Y
), and so forth.
(2)
Nondegeneracy: e
(
P
,
P
)
≠
1
G
2, where 1
G
2 denotes the identity element of the group G
2.
(3)
Computability: there exists an efficient algorithm to compute e
(
X
,
Y
) for any X
,
Y
∈
G
1.We also consider the following computational problem in〈
G
1
,
G
2
,
e
〉 as above which will form the basis of security for our CL-PKE scheme.Definition 4.
The Bilinear Diffie-Hellman Problem (BDHP) is given〈
P
,
a
P
,
b
P
,
c
P
〉 with uniformly random choices of a
,
b
,
c
∈
Z
N
*; compute e
(
P
,
P
)
a
b
c
∈
G
2. An algorithm 𝒜 has the advantage ϵ
′ in solving the BDHP in 〈
G
1
,
G
2
,
e
〉 if Pr
[
𝒜
(
〈
P
,
a
P
,
b
P
,
c
P
〉
)
=
e
(
P
,
P
)
a
b
c
]
=
ϵ
′.The BDHP is said to beϵ
′-intractable if there is no algorithm that 𝒜 solves this problem with ϵ
′.


### 2.3. Definition of CL-PKE

According to [2], a CL-PKE scheme consists of seven probabilistic, polynomial time (PPT) algorithms:Setup,Partial-Private-Key-Extract,Set-Secret-Value,Set-Private-Key,Set-Public-Key,Encrypt, andDecrypt.Setup. On input a security parameter 1
k, this algorithm returns the system parametersparam and the master keymsk. The systemparam includes the plaintext space ℳ and the ciphertext space 𝒞. After this algorithm is over, the KGC publishesparam and keeps themsk secret.Partial-Private-Key-Extract. On inputparam,msk, and an identity ID for the entity, KGC executes this algorithm and returns the partial private key D
ID to entity via a confidential and authentic channel.Set-Secret-Value. On inputparam and an identity ID, entity executes this algorithm and returns entity’s secret value x
ID.Set-Private-Key. On inputparam, entity’s partial private key D
ID, and secret value x
ID, this algorithm returns the entity’s full private key SKID. Note that this algorithm is executed by the entity itself.Set-Public-Key. On inputparam and entity’s secret value x
ID, this algorithm returns the public key PKID to the entity. This algorithm is also executed by the entity itself.Encrypt. Running by a sender. On input message M
∈
ℳ, public key PKID, and identity ID of an entity, this algorithm returns a ciphertext C
∈
𝒞.Decrypt. Running this determinate algorithm by a receiver. On inputparam, C
∈
𝒞, and a private key SKID, this algorithm returns a message M
∈
ℳ, which is either a plaintext message or a “Reject” message.


### 2.4. Security Model for CL-PKE

In CL-PKE, there are two types of adversary with different capabilities, Type I and Type II adversaries [2]. A difference between these two attackers is that 𝒜
I does not have access to the master key of KGC, while 𝒜
II does have. Specifically, the adversary 𝒜
I in Type I represents a normal third party attacker against the CL-PKE scheme; that is, 𝒜
I is not allowed to access to the master key but 𝒜
I may request public keys and replace public keys with values of its choice. The adversary 𝒜
II represents a malicious KGC who generates partial private keys of users. The adversary 𝒜
II is allowed to have access to the master key but not replace a public key.Definition 5.
A CL-PKE scheme is IND-CCA secure if neither polynomially bounded adversary𝒜 of Type I nor Type II has a nonnegligible advantage against the challenger in the following game.Setup. The challenger 𝒞
ℋ takes a security parameter 1
k as inputs and runs the Setup algorithm; then it sends the resulting system parametersparam to 𝒜. If 𝒜 is of Type I, 𝒞
ℋ keeps the master secret key m
s
k to itself. Otherwise, it returns m
s
k to 𝒜.Phase 1. 𝒜 is given access to the following oracles.(1)
Partial-Key-Extract-Oracle: upon receiving a partial key query for a user’s identity ID,𝒞
ℋ computes D
ID and returns it to 𝒜. (Note that it is only useful to Type I adversary.)
(2)
Private-Key-Request-Oracle: upon receiving a private key query for a user’s identity ID,𝒞
ℋ computes SKID and returns it to 𝒜. It outputs ⊥ (denotes failure) if the user’s public key has been replaced (in the case of Type I adversary).
(3)
Public-Key-Request-Oracle: upon receiving a public key query for a user’s identity ID,𝒞
ℋ computes PKID and returns it to 𝒜.
(4)
Public-Key-Replace-Oracle: for identity ID and a valid public key,𝒜 replaces the associated user’s public key with the new one of its choice (this is only for Type I adversary). The new value will be recorded and used by 𝒞
ℋ in the coming computations or responses to the adversary’s queries.
(5)
Decryption-Oracle: On input a ciphertext and an identity, it returns the correct decryption of ciphertext, which is encrypted under the private key corresponding to the current value of the public key associated with an identity of the user, even if the corresponding public key for the user ID has been replaced.Challenge Phase. Once 𝒜 decides that Phase 1 is over, it outputs and submits two messages (
M
0
,
M
1
), together with a challenge identity ID
* of the uncorrupted secret key. Note that 𝒜 is not allowed to know the private key of ID
* in anyway. The challenger 𝒞
ℋ picks a random bit β
∈
{
0,1
} and computes C
*, which is the encryption of M
β under the current public key PK
ID
* for ID
*. If the output of the encryption is ⊥, 𝒜 immediately loses the game. Otherwise, C
* is delivered to 𝒜.Phase 2. Now 𝒜 issues a second sequence of queries as inPhase 1. A decryption query on the challenge ciphertext C
* for the combination of ID
* and PK
ID
* is not allowed.Guess. Finally, 𝒜 outputs its guess β
′ for β. The adversary wins the game if β
′
=
β and the advantage of 𝒜 in this game is defined to be Adv
(
𝒜
)
=
|
Pr
(
β
′
=
β
)
-
1
/
2
|. The adversary 𝒜
i
(
i
=
I
,
II
) breaks an IND-CCA secure CL-PKE scheme with (
q
H
,
q
par
,
q
pub
,
q
prv
,
q
D
,
ϵ
) if and only if the guessing advantage of 𝒜
i that makes q
H times the random oracle H
(
·
), q
par times Partial-Key-Extract-Oracle, q
pub times Public-Key-Request-Oracle, q
prv times Private-Key-Request-Oracle, and q
D times Decryption-Oracle queries is greater than ϵ. The scheme is said to be (
q
H
,
q
par
,
q
pub
,
q
prv
,
q
D
,
ϵ
)-IND-CCA secure if there is no attacker 𝒜
i that breaks IND-CCA secure scheme with (
q
H
,
q
par
,
q
pub
,
q
prv
,
q
D
,
ϵ
).


## 2.1. Elliptic Curve over the Ring

Definition 1.
LetF
q be a field and prime q
>
3; all the points (
x
,
y
)
∈
F
q
×
F
q satisfying the equation y
2
≡
x
3
+
a
x
+
b
(
mod
⁡
q
) compose the elliptic curve over F
q together with the point at infinity denoted 𝒪, where a
,
b
∈
F
q are two parameters satisfying 4
a
3
+
27
b
2
≠
0
(
mod
⁡
q
); such a curve is denoted by E
q
(
a
,
b
).The addition operation on the points ofE
q
(
a
,
b
) can be defined as follows.LetP
=
(
x
1
,
y
1
), Q
=
(
x
2
,
y
2
) be the points of E
q
(
a
,
b
); then -
P
=
(
x
1
,
-
y
1
).(a)
IfP
=
𝒪, then -
P
=
𝒪, and P
+
Q
=
Q;
(b)
ifQ
=
-
P, then P
+
Q
=
𝒪;
(c)
ifQ
≠
-
P, then P
+
Q
=
(
x
3
,
y
3
), where x
3
=
λ
2
-
x
1
-
x
2, y
3
=
λ
(
x
1
-
x
3
)
-
y
1, and
(1)
λ
=
{
y
2
-
y
1
x
2
-
x
1
,
if
P
≠
Q
,
3
x
1
2
+
a
2
y
1
,
if
P
=
Q
.From these definitions, we know the fact that the addition operation on the points ofE
q
(
a
,
b
) can be made as an Abelian group, where 𝒪 is the neutral element of E
q
(
a
,
b
).LetZ
n
=
Z
/
n
Z, where n
=
p
q is the product of two large primes as the RSA modulus. The Chinese Remainder Theorem says that there is an isomorphism of rings
(2)
Z
p
q
≃
Z
p
⊕
Z
q
given by
(3)
x
mod
⁡
p
q
⟷
(
x
mod
⁡
p
,
x
mod
⁡
q
)
.This yields a bijection between elements inZ
p
q and pairs of elements, one in Z
p and the other in Z
q. Thus, the following theorem can be given.Theorem 2.
Letp and q be odd integers with gcd
(
p
,
q
)
=
1; let E be an elliptic curve defined over Z
p
q. Then, there is a group isomorphism
(4)
E
(
Z
p
q
)
≃
E
(
Z
p
)
⊕
E
(
Z
q
)
.Therefore, there is an isomorphism mapping(5)
φ
:
E
(
Z
p
q
)
⟶
E
(
Z
p
)
⊕
E
(
Z
q
)
,
P
p
q
⟼
[
P
p
,
P
q
]
,
where P
p
q
∈
E
(
Z
p
q
), P
p
∈
E
(
Z
p
) and P
q
∈
E
(
Z
q
).LetQ
p
q
∈
E
(
Z
p
q
)
,
Q
p
∈
E
(
Z
p
) and Q
q
∈
E
(
Z
q
); we can get
(6)
φ
(
P
p
q
)
=
[
P
p
,
P
q
]
,
φ
(
Q
p
q
)
=
[
Q
p
,
Q
q
]
,
φ
(
P
p
q
+
Q
p
q
)
=
φ
(
P
p
q
)
+
φ
(
Q
p
q
)
=
[
P
p
,
P
q
]
+
[
Q
p
,
Q
q
]
=
[
P
p
+
Q
p
,
P
q
+
Q
q
]
.Becauseφ is an isomorphism mapping, there is an inverse mapping of it, denoted ψ. Thus,
(7)
ψ
(
φ
(
P
p
q
+
Q
p
q
)
)
=
P
p
q
+
Q
p
q
=
ψ
(
[
P
p
+
Q
p
,
P
q
+
Q
q
]
)
,
which means that the addition law on E
(
Z
p
q
) can be defined as an isomorphism mapping of the addition law in E
(
Z
p
) and E
(
Z
q
), with the convention that the infinity point 𝒪 of E
(
Z
p
q
) can be presented by [
𝒪
p
,
𝒪
q
], where 𝒪
p and 𝒪
q are the points at infinity on E
(
Z
p
) and E
(
Z
q
), respectively. Then, E
(
Z
p
q
) is an Abelian group under this definition of point addition.For more details concerning the addition law on elliptic curves over the ring, see [12, 13, 15]. Besides, there is an important theorem in constructing our CL-PKE over the ring as shown below.Theorem 3.
LetE
n
(
a
,
b
) be an elliptic curve such that gcd
(
4
a
3
+
27
b
2
,
n
)
=
1, n
=
p
q, and let N be lcm
(
♯
E
p
(
a
,
b
)
,
♯
E
q
(
a
,
b
)
). Then, for any P
∈
E
n
(
a
,
b
) and any integer k,
(8)
(
k
·
N
+
1
)
·
P
=
P
o
v
e
r
E
n
(
a
,
b
)
.


## 2.2. Bilinear Pairings

LetG
1 be a cyclic additive group generated by an elliptic curve point P, whose order is N; let G
2 be a multiplicative group of the same order. Assume that bilinear pairing is a map e
:
G
1
×
G
1
→
G
2 with the following properties.(1)
Bilinearity: for all X
,
Y
,
Z
∈
G
1, e
(
X
,
Y
+
Z
)
=
e
(
X
,
Y
)
·
e
(
X
,
Z
) and e
(
X
+
Y
,
Z
)
=
e
(
X
,
Z
)
·
e
(
Y
,
Z
). Consequently, ∀
a
,
b
∈
Z
q, we have e
(
a
X
,
b
Y
)
=
e
(
X
,
Y
)
a
b
=
e
(
a
b
X
,
Y
), and so forth.
(2)
Nondegeneracy: e
(
P
,
P
)
≠
1
G
2, where 1
G
2 denotes the identity element of the group G
2.
(3)
Computability: there exists an efficient algorithm to compute e
(
X
,
Y
) for any X
,
Y
∈
G
1.We also consider the following computational problem in〈
G
1
,
G
2
,
e
〉 as above which will form the basis of security for our CL-PKE scheme.Definition 4.
The Bilinear Diffie-Hellman Problem (BDHP) is given〈
P
,
a
P
,
b
P
,
c
P
〉 with uniformly random choices of a
,
b
,
c
∈
Z
N
*; compute e
(
P
,
P
)
a
b
c
∈
G
2. An algorithm 𝒜 has the advantage ϵ
′ in solving the BDHP in 〈
G
1
,
G
2
,
e
〉 if Pr
[
𝒜
(
〈
P
,
a
P
,
b
P
,
c
P
〉
)
=
e
(
P
,
P
)
a
b
c
]
=
ϵ
′.The BDHP is said to beϵ
′-intractable if there is no algorithm that 𝒜 solves this problem with ϵ
′.


## 2.3. Definition of CL-PKE

According to [2], a CL-PKE scheme consists of seven probabilistic, polynomial time (PPT) algorithms:Setup,Partial-Private-Key-Extract,Set-Secret-Value,Set-Private-Key,Set-Public-Key,Encrypt, andDecrypt.Setup. On input a security parameter 1
k, this algorithm returns the system parametersparam and the master keymsk. The systemparam includes the plaintext space ℳ and the ciphertext space 𝒞. After this algorithm is over, the KGC publishesparam and keeps themsk secret.Partial-Private-Key-Extract. On inputparam,msk, and an identity ID for the entity, KGC executes this algorithm and returns the partial private key D
ID to entity via a confidential and authentic channel.Set-Secret-Value. On inputparam and an identity ID, entity executes this algorithm and returns entity’s secret value x
ID.Set-Private-Key. On inputparam, entity’s partial private key D
ID, and secret value x
ID, this algorithm returns the entity’s full private key SKID. Note that this algorithm is executed by the entity itself.Set-Public-Key. On inputparam and entity’s secret value x
ID, this algorithm returns the public key PKID to the entity. This algorithm is also executed by the entity itself.Encrypt. Running by a sender. On input message M
∈
ℳ, public key PKID, and identity ID of an entity, this algorithm returns a ciphertext C
∈
𝒞.Decrypt. Running this determinate algorithm by a receiver. On inputparam, C
∈
𝒞, and a private key SKID, this algorithm returns a message M
∈
ℳ, which is either a plaintext message or a “Reject” message.


## 2.4. Security Model for CL-PKE

In CL-PKE, there are two types of adversary with different capabilities, Type I and Type II adversaries [2]. A difference between these two attackers is that 𝒜
I does not have access to the master key of KGC, while 𝒜
II does have. Specifically, the adversary 𝒜
I in Type I represents a normal third party attacker against the CL-PKE scheme; that is, 𝒜
I is not allowed to access to the master key but 𝒜
I may request public keys and replace public keys with values of its choice. The adversary 𝒜
II represents a malicious KGC who generates partial private keys of users. The adversary 𝒜
II is allowed to have access to the master key but not replace a public key.Definition 5.
A CL-PKE scheme is IND-CCA secure if neither polynomially bounded adversary𝒜 of Type I nor Type II has a nonnegligible advantage against the challenger in the following game.Setup. The challenger 𝒞
ℋ takes a security parameter 1
k as inputs and runs the Setup algorithm; then it sends the resulting system parametersparam to 𝒜. If 𝒜 is of Type I, 𝒞
ℋ keeps the master secret key m
s
k to itself. Otherwise, it returns m
s
k to 𝒜.Phase 1. 𝒜 is given access to the following oracles.(1)
Partial-Key-Extract-Oracle: upon receiving a partial key query for a user’s identity ID,𝒞
ℋ computes D
ID and returns it to 𝒜. (Note that it is only useful to Type I adversary.)
(2)
Private-Key-Request-Oracle: upon receiving a private key query for a user’s identity ID,𝒞
ℋ computes SKID and returns it to 𝒜. It outputs ⊥ (denotes failure) if the user’s public key has been replaced (in the case of Type I adversary).
(3)
Public-Key-Request-Oracle: upon receiving a public key query for a user’s identity ID,𝒞
ℋ computes PKID and returns it to 𝒜.
(4)
Public-Key-Replace-Oracle: for identity ID and a valid public key,𝒜 replaces the associated user’s public key with the new one of its choice (this is only for Type I adversary). The new value will be recorded and used by 𝒞
ℋ in the coming computations or responses to the adversary’s queries.
(5)
Decryption-Oracle: On input a ciphertext and an identity, it returns the correct decryption of ciphertext, which is encrypted under the private key corresponding to the current value of the public key associated with an identity of the user, even if the corresponding public key for the user ID has been replaced.Challenge Phase. Once 𝒜 decides that Phase 1 is over, it outputs and submits two messages (
M
0
,
M
1
), together with a challenge identity ID
* of the uncorrupted secret key. Note that 𝒜 is not allowed to know the private key of ID
* in anyway. The challenger 𝒞
ℋ picks a random bit β
∈
{
0,1
} and computes C
*, which is the encryption of M
β under the current public key PK
ID
* for ID
*. If the output of the encryption is ⊥, 𝒜 immediately loses the game. Otherwise, C
* is delivered to 𝒜.Phase 2. Now 𝒜 issues a second sequence of queries as inPhase 1. A decryption query on the challenge ciphertext C
* for the combination of ID
* and PK
ID
* is not allowed.Guess. Finally, 𝒜 outputs its guess β
′ for β. The adversary wins the game if β
′
=
β and the advantage of 𝒜 in this game is defined to be Adv
(
𝒜
)
=
|
Pr
(
β
′
=
β
)
-
1
/
2
|. The adversary 𝒜
i
(
i
=
I
,
II
) breaks an IND-CCA secure CL-PKE scheme with (
q
H
,
q
par
,
q
pub
,
q
prv
,
q
D
,
ϵ
) if and only if the guessing advantage of 𝒜
i that makes q
H times the random oracle H
(
·
), q
par times Partial-Key-Extract-Oracle, q
pub times Public-Key-Request-Oracle, q
prv times Private-Key-Request-Oracle, and q
D times Decryption-Oracle queries is greater than ϵ. The scheme is said to be (
q
H
,
q
par
,
q
pub
,
q
prv
,
q
D
,
ϵ
)-IND-CCA secure if there is no attacker 𝒜
i that breaks IND-CCA secure scheme with (
q
H
,
q
par
,
q
pub
,
q
prv
,
q
D
,
ϵ
).


## 3. Our CL-PKE Scheme

In this section, we propose a CL-PKE scheme based on the bilinear pairing over the ring and evaluate its performance.


### 3.1. Construction

The proposed CL-PKE scheme consists of the following seven PPT algorithms.Setup. Let G
1, G
2 be bilinear groups of order N with an arbitrary generator P
∈
G
1, and e
:
G
1
×
G
1
→
G
2 is a bilinear pairing, where G
1 is a elliptic curve E
N
(
a
,
b
). The KGC selects an m
s
k
s
∈
Z
N
* at random and computes X
=
s
P as the master public key. Then, it chooses two collision resistant hash functions H
1
:
{
0,1
}
ω
→
G
1
*, H
2
:
G
2
→
{
0,1
}
*, where ω denotes the bit-length of identity. The system parameters are p
a
r
a
m
=
{
G
1
,
G
2
,
e
,
P
,
X
,
H
1
,
H
2
} and the master secret key is m
s
k
=
s.Partial-Private-Key-Extract. On input an entity’s identity ID
∈
{
0,1
}
ω, this algorithm computes Q
ID
=
H
1
(
ID
)
∈
G
1
* and sends the partial private key D
ID
=
s
·
Q
ID
∈
G
1
* to entity via a secure channel.Set-Secret-Value. On inputparam and an identity ID, entity picks a secret value a
∈
Z
N
*. Return x
ID
=
a.Set-Private-Key. On inputparam, ID and x
ID, entity obtains the private key SKID by computing SK
ID
=
a
·
D
ID
=
a
s
H
1
(
ID
)
∈
G
1
*.Set-Public-Key. On inputparam and ID, this algorithm returns PK
ID
=
x
ID
Q
ID as the public key.Encrypt. To encrypt M
∈
{
0,1
}
*, entity selects a random value r
∈
Z
N
* and σ
∈
{
0,1
}
*, computes C
=
(
c
1
,
c
2
) such that
(9)
c
1
=
r
P
,
c
2
=
(
M
∥
σ
)
⊕
H
2
(
e
(
PK
ID
,
r
X
)
)
,
outputs the ciphertext C
=
(
c
1
,
c
2
).Decrypt. To decrypt ciphertext C
=
(
c
1
,
c
2
) for the entity with identity ID and private key SKID, compute
(10)
M
∥
σ
=
c
2
⊕
H
2
(
e
(
SK
ID
,
c
1
)
)
,
and return M as plaintext.Notice that if(
c
1
,
c
2
) is the encryption of M with public key PKID, we have
(11)
c
2
⊕
H
2
(
e
(
SK
ID
,
c
1
)
)
=
(
M
∥
σ
)
⊕
H
2
(
e
(
PK
ID
,
r
X
)
)
⊕
H
2
(
e
(
a
s
Q
ID
,
r
P
)
)
=
(
M
∥
σ
)
⊕
H
2
(
e
(
Q
ID
,
P
)
a
r
s
)
⊕
H
2
(
e
(
Q
ID
,
P
)
a
r
s
)
=
M
∥
σ
.


### 3.2. Security Analysis

In this section, we will show that the scheme described in the previous is secure in the random oracle model.Theorem 6.
Given thatH
1 and H
2 are two collision resistant hash functions. The proposed CL-PKE scheme based on the ring Z
N is IND-CCA secure in the random oracle model assuming that the BDHP is intractable.In the procession of attacking this system by an adversary𝒜, it chooses two messages M
0, M
1 and is given the challenge ciphertext C
* for one of these two messages M
β by the challenger 𝒞
ℋ firstly. Then, 𝒜 may make decryption queries but not ask for the decryption of C
*. If 𝒜’s guess β
′ is equal to β, it wins the game.In order to prove Theorem6, we prove two lemmas firstly to show that our CL-PKE scheme is secure against Type I and Type II attacker whose behavior is as described in Definition 5.Lemma 7.
The CL-PKE scheme is(
q
H
1
,
q
H
2
,
q
p
a
r
,
q
p
u
b
,
q
p
r
v
,
q
D
,
ϵ
)-IND-CCA secure against Type I attacker 𝒜 in the random oracle assuming that the BDH problem is ϵ
′-intractable, where ϵ
′
>
(
1
/
q
H
2
)
(
2
ϵ
/
e
(
q
p
r
v
+
q
p
a
r
+
1
)
-
q
H
1
/
2
ω
-
q
D
q
H
1
/
2
ω
-
q
D
/
N
).Proof.
In this lemma, Type I models an “outside” adversary, which can replace the public key of arbitrary identities but cannot corrupt the master secret key.
Let𝒜
I be a Type I IND-CCA adversary against our scheme. Suppose that 𝒜
I has the advantage ϵ and makes q
H
i queries to random oracle H
i
(
i
=
1,2
) and q
D decryption queries. We show how to construct an algorithm ℬ to solve the BDH problem with the instance of (
P
,
a
P
,
b
P
,
c
P
) by interacting with 𝒜
I.
At the beginning,ℬ simulates the algorithmSetup for 𝒜
I by supplying it with p
a
r
a
m
=
{
G
1
,
G
2
,
e
,
P
,
X
,
H
1
,
H
2
}, where H
1, H
2 is random oracles that will be controlled by ℬ. ℬ chooses an index I uniformly at random with 1
≤
I
≤
q
H
1.
The adversary𝒜
I may make queries of the random oracles H
i
(
i
=
1,2
) at any time during its attack. ℬ responds as follows.
H
1
Queries. ℬ maintains a list of tuples 〈
ID
i
,
Q
i
,
t
i
〉 in H
1 List L
1. On receiving a query ID
i to H
1, ℬ responds as follows.(1)
IfID
i already appears on the list L
1 in a tuple 〈
ID
i
,
Q
i
,
t
i
〉, ℬ responds Q
i as an answer.
(2)
Otherwise, ifi
≠
I, choose t
i
∈
Z
N
* at random and compute Q
i
=
t
i
P, add 〈
ID
i
,
Q
i
,
t
i
〉 to L
1, and return Q
i as an answer.
(3)
Ifi
=
I, add 〈
ID
i
,
Q
i
=
c
P
,
*
〉 to L
1 and return Q
i
=
c
P as an answer (where * denotes the arbitrary value).
H
2
Queries. ℬ maintains a list of tuples 〈
ID
i
,
e
i
,
R
i
〉 in H
2 List L
2. On receiving a query 〈
ID
i
,
e
i
〉 to H
2, ℬ responds as follows.(1)
IfID
i already appears on the list L
2 in a tuple 〈
ID
i
,
e
i
,
R
i
〉, ℬ responds R
i as an answer.
(2)
Otherwise, pickR
i
∈
{
0,1
}
* at random, add 〈
ID
i
,
e
i
,
R
i
〉 to L
2 and return R
i as an answer.
Phase 1. After receivingparam from ℬ, 𝒜
I issues a sequence of polynomially bounded number of requests, each request being either aPartial-Private-Key-Extraction, aPrivate-Key-Extraction, aRequest-Public-Key, aReplace-Public-Key, orDecryption-Queries for an entity. We assume that 𝒜
I always makes the appropriate H
1 queries on the identity ID before making one of these requests and never makes a decryption query on a ciphertext obtained from the encryption oracle. ℬ replies to these requests as follows.
Partial-Private-Key-Extraction. ℬ maintains a Partial Private Key List of tuples 〈
ID
i
,
D
i
〉. On receiving a query ID
i, ℬ responds as follows.(1)
If〈
ID
i
,
D
i
〉 exist in Partial Private Key List, return D
i as an answer.
(2)
Otherwise, picki at random, so that Pr
[
i
≠
I
]
=
δ. (δ will be determined later.) If i
≠
I, search the L
1 for a tuple 〈
ID
i
,
Q
i
,
t
i
〉, compute D
i
=
t
i
P, add 〈
ID
i
,
D
i
〉 to the Partial Private Key List, and return D
i as an answer.
(3)
Ifi
=
I, return “Abort” and terminate.
Private-Key-Extraction. ℬ maintains a Private Key List of tuples 〈
ID
i
,
x
i
,
D
i
〉. On receiving a query ID
i, ℬ responds as follows.(1)
If〈
ID
i
,
x
i
,
D
i
〉 exist in Private Key List, return 〈
x
i
,
D
i
〉 as answer.
(2)
Otherwise, ifi
≠
I, run the simulation algorithm Request-Public-Key to get a tuple 〈
ID
i
,
x
i
,
PK
i
〉 and the simulation algorithm Private-Key-Extraction to get a tuple 〈
ID
i
,
D
i
〉, add 〈
ID
i
,
x
i
,
D
i
〉 to the Private Key List, and return 〈
x
i
,
D
i
〉 as an answer. (Note that if the corresponding public key has been replaced, such a private key query is not allowed.)
(3)
Ifi
=
I, return “Abort” and terminate.
Request-Public-Key. ℬ maintains a Public Key List of tuples 〈
ID
i
,
x
i
,
PK
i
〉. On receiving a query ID
i, ℬ responds as follows.(1)
If〈
ID
i
,
x
i
,
PK
i
〉 exist in Public Key List, return PK
i as an answer.
(2)
Otherwise, choosex
i
∈
Z
N
*, compute PK
i
=
x
i
H
1
(
ID
i
), add 〈
ID
i
,
x
i
,
PK
i
〉 to the Public Key List, and return PK
i as an answer.
Replace-Public-Key. 𝒜
I may replace any public key with a new value of its choice and ℬ records all the changes.
Decryption-Queries. On receiving a query 〈
ID
i
,
PK
i
,
C
〉, where C
=
(
c
1
,
c
2
) and PK
i
=
x
i
H
1
(
ID
i
). ℬ responds as follows.(1)
Ifi
≠
I and PK
i is the correct public key not a replaced one, ℬ decrypts C by using the corresponding private key.
(2)
Otherwise, searchL
2 for a tuple 〈
ID
i
,
e
i
,
R
i
〉. If such a tuple exists, ℬ retrieves the related R
i to compute M
∥
σ
=
c
2
⊕
R
i and returns M as an answer.
(3)
Otherwise,ℬ picks R
i
∈
{
0,1
}
* at random, computes M
∥
σ
=
c
2
⊕
R
i and returns M as an answer. Add 〈
ID
i
,
e
i
,
R
i
〉 to L
2.
Challenge Phase. 𝒜
I then outputs two messages (
M
0
,
M
1
) and a challenge identity ID
*. On receiving a challenge query 〈
ID
*
,
(
M
0
,
M
1
)
〉:(1)
IfID
*
≠
ID
I, ℬ aborts the game.
(2)
Otherwise,ℬ selects r
*
∈
Z
N
* and σ
∈
{
0,1
}
* randomly, computes c
1
*
=
r
*
P and H
2
(
e
(
SK
ID
*
,
c
1
*
)
)
=
c
2
*
⊕
(
M
β
∥
σ
) (note that ℬ does not know “r
*”), returns C
*
=
(
c
1
*
,
c
2
*
) as a target ciphertext.
Phase 2. 𝒜
I requests in the same ways as inPhase 1. Moreover, no private key extraction on ID
* is allowed and no decryption query can be made on the ciphertext C
* for the combination of identity ID
* and public key PK
ID
* that encrypted plaintext M
β.
Guess. 𝒜
I should make a guess β
′ for β. The adversary wins the game if β
′
=
β.
Analysis. By A
s
k
H
2
* we denote the event that (
ID
*
,
e
i
*
) has been queried to H
2. Also, by A
s
k
H
1
* we denote the event that ID
* has been queried to H
1. If happens, ℬ will be able to solve the BDH problem by choosing a tuple 〈
ID
i
,
e
i
,
R
i
〉 from L
2 and computing H
2
(
e
i
) with the probability at least 1
/
q
H
2. Hence, we have ϵ
′
≥
(
1
/
q
H
2
)
Pr
[
A
s
k
H
2
*
].
It is easy to notice that ifℬ does not abort, the simulations ofPartial-Key-Extract,Private-Key-Request,Public-Key-Request, and the simulated target ciphertext are identically distributed as the real one from the construction.
Now, we evaluate the simulation of the decryption oracle. If a public key PKID has not been replaced nor PKID has been produced by reselecting x
i
∈
Z
N
*, the simulation is perfect as ℬ knowing the private key SKID corresponding to PKID. Otherwise, simulation error may occur while ℬ is running the decryption oracle simulation specified above. Let D
e
c
E
r
r be this event. Suppose that ID, PKID, C, where C
=
(
c
1
,
c
2
) and PK
ID
=
x
ID
P, have been issued as a valid decryption query. Even if C is valid, there is a possibility that C can be produced without querying (
ID
,
e
i
) to H
2. Let V
a
l
i
d be an event that C is valid; let A
s
k
H
2 and A
s
k
H
1 be events that (
ID
,
e
i
) have been queried to H
2 and ID have been queried to H
1, respectively. Since D
e
c
E
r
r is an event that V
a
l
i
d
∣
¬
A
s
k
H
2 happens after the entire simulation and q
D decryption oracle queries being performed, we have Pr
[
D
e
c
E
r
r
]
=
q
D
Pr
[
V
a
l
i
d
∣
¬
A
s
k
H
2
], where,
(12)
Pr
⁡
[
V
a
l
i
d
∣
¬
A
s
k
H
2
]
≤
Pr
⁡
[
V
a
l
i
d
∧
A
s
k
H
1
∣
¬
A
s
k
H
2
]
+
Pr
⁡
[
V
a
l
i
d
∧
¬
A
s
k
H
1
∣
¬
A
s
k
H
2
]
≤
Pr
[
A
s
k
H
1
∣
¬
A
s
k
H
2
]
+
Pr
[
V
a
l
i
d
∣
¬
A
s
k
H
1
∧
¬
A
s
k
H
2
]
≤
q
H
1
2
ω
+
1
N
.
Now, the event(
A
s
k
H
2
*
∨
(
A
s
k
H
1
*
∣
¬
A
s
k
H
2
*
)
∨
D
e
c
E
r
r
)
∣
¬
A
b
o
r
t is denoted by E, where  A
b
o
r
t denotes an event that ℬ aborts during the simulation. The probability ¬
A
b
o
r
t that happens is given by δ
q
prv
+
q
par
(
1
-
δ
) which is maximized at δ
=
1
-
1
/
(
q
prv
+
q
par
+
1
). Hence, we have Pr
[
¬
A
b
o
r
t
]
≤
1
/
e
(
q
prv
+
q
par
+
1
), where e denotes the base of the natural logarithm.
IfE does not happen, it is clear that 𝒜
I does not gain any advantage greater than 1
/
2 to guess β due to the randomness of the output of the random oracle H
2. Namely, we have Pr
[
β
′
=
β
∣
¬
E
]
≤
1
/
2.
By definition ofϵ, we have
(13)
ϵ
<
|
Pr
⁡
[
β
′
=
β
]
-
1
2
|
=
|
1
2
Pr
[
β
′
=
β
∣
¬
E
]
Pr
[
¬
E
]
+
Pr
⁡
[
β
′
=
β
∣
E
]
Pr
⁡
[
E
]
-
1
2
|
≤
|
1
2
Pr
⁡
[
¬
E
]
+
Pr
⁡
[
E
]
-
1
2
|
=
|
1
2
(
1
-
Pr
⁡
[
E
]
)
+
Pr
⁡
[
E
]
-
1
2
|
=
1
2
Pr
⁡
[
E
]
≤
1
2
Pr
⁡
[
¬
A
b
o
r
t
]
×
(
Pr
⁡
[
A
s
k
H
2
*
]
+
Pr
⁡
[
A
s
k
H
1
*
∣
¬
A
s
k
H
2
*
]
+
Pr
⁡
[
D
e
c
E
r
r
]
)
≤
e
(
q
prv
+
q
par
+
1
)
2
(
q
H
2
ϵ
′
+
q
H
1
2
ω
+
q
D
q
H
1
2
ω
+
q
D
N
)
.
Consequently, we obtainϵ
′
>
(
1
/
q
H
2
)
(
2
ϵ
/
e
(
q
prv
+
q
par
+
1
)
-
q
H
1
/
2
ω
-
q
D
q
H
1
/
2
ω
-
q
D
/
N
).Lemma 8.
The CL-PKE scheme is(
q
H
1
,
q
H
2
,
q
p
a
r
,
q
p
u
b
,
q
p
r
v
,
q
D
,
ϵ
)-IND-CCA secure against Type II attacker 𝒜 in the random oracle assuming that the BDH problem is ϵ
′-intractable, where ϵ
′
>
(
1
/
q
H
2
)
(
2
ϵ
/
e
(
q
p
r
v
+
1
)
-
q
H
1
/
2
ω
-
q
D
q
H
1
/
2
ω
-
q
D
/
N
).Proof.
In this lemma, a Type II models an “insider” adversary, who has access tomsk but cannot replace public keys of entities.
Let𝒜
II be a Type II IND-CCA adversary against our scheme. Suppose that 𝒜
II has the advantage ϵ, makes q
H
i queries to random oracle H
i
(
i
=
1,2
), and q
D decryption queries. We show how to construct an algorithm ℬ to solve the BDH problem with the instance of (
P
,
a
P
,
b
P
,
c
P
) by interacting with 𝒜
II.
At the beginning,ℬ simulates the algorithm Setup for 𝒜
II by supplying 𝒜
II with p
a
r
a
m
=
{
G
1
,
G
2
,
e
,
P
,
X
,
H
1
,
H
2
}, where H
1, H
2 are random oracles that will be controlled by ℬ. ℬ chooses an index I uniformly at random with 1
≤
I
≤
q
H
1.
The adversary𝒜
II may make queries of the random oracles H
i
(
i
=
1,2
) at any time during its attack. ℬ responds as follows.
H
1
Queries. ℬ maintains a list of tuples 〈
ID
i
,
Q
i
〉 in H
1 List L
1. On receiving a query ID
i to H
1, ℬ responds as follows.(1)
IfID
i already appears on the list L
1 in a tuple 〈
ID
i
,
Q
i
〉, ℬ responds Q
i as an answer.
(2)
Otherwise, ifi
≠
I, choose Q
i
∈
G
1
* at random and add 〈
ID
i
,
Q
i
〉 to L
1 and return Q
i as an answer.
H
2
Queries. ℬ maintains a list of tuples 〈
ID
i
,
e
i
,
R
i
〉 in H
2 List L
2. On receiving a query 〈
ID
i
,
e
i
〉 to H
2, ℬ responds as follows.(1)
IfID
i already appears on the list L
2 in a tuple 〈
ID
i
,
e
i
,
R
i
〉, ℬ responds R
i as an answer.
(2)
Otherwise, pickR
i
∈
{
0,1
}
* at random, add 〈
ID
i
,
e
i
,
R
i
〉 to L
2, and return R
i as an answer.
Phase 1. After receivingparam from ℬ, 𝒜
II issues a sequence of polynomially bounded number of requests, each request being either aPrivate-Key-Extraction, aRequest-Public-Key, orDecryption-Queries for an entity. We assume that 𝒜
II always makes the appropriate H
1 queries on the identity ID before making one of these requests and never makes a decryption query on a ciphertext obtained from the encryption oracle. ℬ replies to these requests as follows.
Private-Key-Extraction. ℬ maintains a Private Key List of tuples 〈
ID
i
,
x
i
,
D
i
〉. On receiving a query ID
i, ℬ responds as follows.(1)
If〈
ID
i
,
x
i
,
D
i
〉 exist in Private Key List, return 〈
x
i
,
D
i
〉 as an answer.
(2)
Otherwise, picki at random, so that Pr
[
i
≠
I
]
=
δ. (δ is the same as it is in the proof of Lemma 7.) If i
≠
I, run the simulation algorithm Request-Public-Key to get a tuple 〈
ID
i
,
x
i
,
PK
i
〉 and compute D
i
=
s
Q
i, add 〈
ID
i
,
x
i
,
D
i
〉 to the Private Key List, and return 〈
x
i
,
D
i
〉 as an answer.
(3)
Ifi
=
I, return “Abort” and terminate.
Request-Public-Key. ℬ maintains a Public Key List of tuples 〈
ID
i
,
x
i
,
PK
i
〉. On receiving a query ID
i, ℬ responds as follows.(1)
If〈
ID
i
,
x
i
,
PK
i
〉 exist in Public Key List, return PK
i as an answer.
(2)
Otherwise, ifi
≠
I, choose x
i
∈
Z
N
*, compute PK
i
=
x
i
H
1
(
ID
i
), add 〈
ID
i
,
x
i
,
PK
i
〉 to the Public Key List, and return PK
i as an answer.
(3)
Ifi
=
I, set PK
i
=
a
P, add 〈
ID
i
,
*
,
PK
i
=
a
P
〉 to the public key list, and return PK
i
=
a
P as an answer (where * denotes the arbitrary value).
Decryption-Queries. On receiving a query 〈
ID
i
,
PK
i
,
C
〉, where C
=
(
c
1
,
c
2
). ℬ responds as follows.(1)
Ifi
≠
I, ℬ decrypts C by using the private key 〈
x
i
,
D
i
〉.
(2)
Otherwise, searchL
2 for a tuple 〈
ID
i
,
e
i
,
R
i
〉. If such a tuple exists, ℬ retrieves the related R
i to compute M
∥
σ
=
c
2
⊕
R
i and returns M as an answer.
(3)
Otherwise,ℬ picks R
i
∈
{
0,1
}
* at random, computes M
∥
σ
=
c
2
⊕
R
i, and returns M as an answer. Add 〈
ID
i
,
e
i
,
R
i
〉 to L
2.
Challenge Phase. 𝒜
II then outputs two messages (
M
0
,
M
1
) and a challenge identity ID
*. On receiving a challenge query 〈
ID
*
,
(
M
0
,
M
1
)
〉:(1)
IfID
*
≠
ID
I, ℬ aborts the game.
(2)
Otherwise,ℬ selects r
*
∈
Z
N
* and σ
∈
{
0,1
}
* randomly, computes c
1
*
=
r
*
P and H
2
(
e
(
SK
ID
*
,
c
1
*
)
)
=
c
2
*
⊕
(
M
β
∥
σ
), returns C
*
=
(
c
1
*
,
c
2
*
) as a target ciphertext.
Phase 2. 𝒜
II repeats the same methods it used inPhase 1. Moreover, no private key extraction on ID
* is allowed and no decryption query can be made on the ciphertext C
* for the combination of identity ID
* and public key PK
ID
* that encrypted plaintext M
β.
Guess. 𝒜
II should make a guess β
′ for β. The adversary wins the game if β
′
=
β.
Analysis. This part is similar toAnalysis in the proof of Lemma 7.
Consequently, we obtainϵ
′
>
(
1
/
q
H
2
)
(
2
ϵ
/
e
(
q
prv
+
1
)
-
q
H
1
/
2
ω
-
q
D
q
H
1
/
2
ω
-
q
D
/
N
).These two lemmas complete the proof of Theorem6.Furthermore, in our CL-PKE scheme,G
1
=
E
N
(
a
,
b
) is an elliptic curve over the ring Z
N, where N
=
p
q. According to Theorem 6, in order to run the algorithm on E
N
(
a
,
b
), such as addition and scalar multiplication, we should construct two elliptic curves E
p
(
a
,
b
) and E
q
(
a
,
b
) firstly and execute the corresponding operation on them, respectively. Then, we use the results of operation on E
p
(
a
,
b
) and E
q
(
a
,
b
) to present the operation on E
N
(
a
,
b
), which means that we should factoring N into p and q firstly. Therefore, the security of our CL-PKE scheme is also based on the intractability of factoring the large number.


### 3.3. Comparison to Related Schemes

In this section, we compare the proposed scheme with other related CL-PKE schemes on the computation complexity of encryption (Enc) and decryption (Dec), security level (Sec-Lev), and security assumption (Sec-Ass), where RSA in Table1 represents the problem of factoring the large number. Without considering the addition of two points and hash function on the elliptic curves, all the schemes have three major operations, that is, Pairing (P), Scalar Multiplication (S), and Exponentiation (E).Table 1
Comparison of the CL-PKE schemes.
Schemes
Enc
Dec
Sec-Lev
Sec-Ass
[2]
3P + 1S + 1E
1P + 1S
IND-CCA secure
GBDHP
[4]
1P + 2S + 1E
1P + 2S
IND-CCA secure
BDH
[5]
3S + 1E
1P + 3S
IND-CCA secure
K-BDHI
[6]
1P + 3S + 1E
4P
Strong type I/II secure
3-DDH
[7]
2P + 2S + 2E
2P + 1S
IND-CCA secure
BDH
Our scheme
1P + 2S
1P
IND-CCA secure
BDH/RSAThe essential operation of our proposed scheme is to compute a bilinear pairing. According to [16], the computation of a bilinear pairing becomes efficient. From Table 1, compared with the related works, our scheme needs only one pairing and two scalar multiplications in Encrypt and one pairing operation inDecrypt, which will consume less energy while preserving a higher security level. Therefore, the scheme proposed in this paper is more suitable to be applied in IoT with the characteristics of low cost, low power, multifunctional sensor nodes that are small in size and communicate wirelessly with each other node in a short distance.


## 3.1. Construction

The proposed CL-PKE scheme consists of the following seven PPT algorithms.Setup. Let G
1, G
2 be bilinear groups of order N with an arbitrary generator P
∈
G
1, and e
:
G
1
×
G
1
→
G
2 is a bilinear pairing, where G
1 is a elliptic curve E
N
(
a
,
b
). The KGC selects an m
s
k
s
∈
Z
N
* at random and computes X
=
s
P as the master public key. Then, it chooses two collision resistant hash functions H
1
:
{
0,1
}
ω
→
G
1
*, H
2
:
G
2
→
{
0,1
}
*, where ω denotes the bit-length of identity. The system parameters are p
a
r
a
m
=
{
G
1
,
G
2
,
e
,
P
,
X
,
H
1
,
H
2
} and the master secret key is m
s
k
=
s.Partial-Private-Key-Extract. On input an entity’s identity ID
∈
{
0,1
}
ω, this algorithm computes Q
ID
=
H
1
(
ID
)
∈
G
1
* and sends the partial private key D
ID
=
s
·
Q
ID
∈
G
1
* to entity via a secure channel.Set-Secret-Value. On inputparam and an identity ID, entity picks a secret value a
∈
Z
N
*. Return x
ID
=
a.Set-Private-Key. On inputparam, ID and x
ID, entity obtains the private key SKID by computing SK
ID
=
a
·
D
ID
=
a
s
H
1
(
ID
)
∈
G
1
*.Set-Public-Key. On inputparam and ID, this algorithm returns PK
ID
=
x
ID
Q
ID as the public key.Encrypt. To encrypt M
∈
{
0,1
}
*, entity selects a random value r
∈
Z
N
* and σ
∈
{
0,1
}
*, computes C
=
(
c
1
,
c
2
) such that
(9)
c
1
=
r
P
,
c
2
=
(
M
∥
σ
)
⊕
H
2
(
e
(
PK
ID
,
r
X
)
)
,
outputs the ciphertext C
=
(
c
1
,
c
2
).Decrypt. To decrypt ciphertext C
=
(
c
1
,
c
2
) for the entity with identity ID and private key SKID, compute
(10)
M
∥
σ
=
c
2
⊕
H
2
(
e
(
SK
ID
,
c
1
)
)
,
and return M as plaintext.Notice that if(
c
1
,
c
2
) is the encryption of M with public key PKID, we have
(11)
c
2
⊕
H
2
(
e
(
SK
ID
,
c
1
)
)
=
(
M
∥
σ
)
⊕
H
2
(
e
(
PK
ID
,
r
X
)
)
⊕
H
2
(
e
(
a
s
Q
ID
,
r
P
)
)
=
(
M
∥
σ
)
⊕
H
2
(
e
(
Q
ID
,
P
)
a
r
s
)
⊕
H
2
(
e
(
Q
ID
,
P
)
a
r
s
)
=
M
∥
σ
.


## 3.2. Security Analysis

In this section, we will show that the scheme described in the previous is secure in the random oracle model.Theorem 6.
Given thatH
1 and H
2 are two collision resistant hash functions. The proposed CL-PKE scheme based on the ring Z
N is IND-CCA secure in the random oracle model assuming that the BDHP is intractable.In the procession of attacking this system by an adversary𝒜, it chooses two messages M
0, M
1 and is given the challenge ciphertext C
* for one of these two messages M
β by the challenger 𝒞
ℋ firstly. Then, 𝒜 may make decryption queries but not ask for the decryption of C
*. If 𝒜’s guess β
′ is equal to β, it wins the game.In order to prove Theorem6, we prove two lemmas firstly to show that our CL-PKE scheme is secure against Type I and Type II attacker whose behavior is as described in Definition 5.Lemma 7.
The CL-PKE scheme is(
q
H
1
,
q
H
2
,
q
p
a
r
,
q
p
u
b
,
q
p
r
v
,
q
D
,
ϵ
)-IND-CCA secure against Type I attacker 𝒜 in the random oracle assuming that the BDH problem is ϵ
′-intractable, where ϵ
′
>
(
1
/
q
H
2
)
(
2
ϵ
/
e
(
q
p
r
v
+
q
p
a
r
+
1
)
-
q
H
1
/
2
ω
-
q
D
q
H
1
/
2
ω
-
q
D
/
N
).Proof.
In this lemma, Type I models an “outside” adversary, which can replace the public key of arbitrary identities but cannot corrupt the master secret key.
Let𝒜
I be a Type I IND-CCA adversary against our scheme. Suppose that 𝒜
I has the advantage ϵ and makes q
H
i queries to random oracle H
i
(
i
=
1,2
) and q
D decryption queries. We show how to construct an algorithm ℬ to solve the BDH problem with the instance of (
P
,
a
P
,
b
P
,
c
P
) by interacting with 𝒜
I.
At the beginning,ℬ simulates the algorithmSetup for 𝒜
I by supplying it with p
a
r
a
m
=
{
G
1
,
G
2
,
e
,
P
,
X
,
H
1
,
H
2
}, where H
1, H
2 is random oracles that will be controlled by ℬ. ℬ chooses an index I uniformly at random with 1
≤
I
≤
q
H
1.
The adversary𝒜
I may make queries of the random oracles H
i
(
i
=
1,2
) at any time during its attack. ℬ responds as follows.
H
1
Queries. ℬ maintains a list of tuples 〈
ID
i
,
Q
i
,
t
i
〉 in H
1 List L
1. On receiving a query ID
i to H
1, ℬ responds as follows.(1)
IfID
i already appears on the list L
1 in a tuple 〈
ID
i
,
Q
i
,
t
i
〉, ℬ responds Q
i as an answer.
(2)
Otherwise, ifi
≠
I, choose t
i
∈
Z
N
* at random and compute Q
i
=
t
i
P, add 〈
ID
i
,
Q
i
,
t
i
〉 to L
1, and return Q
i as an answer.
(3)
Ifi
=
I, add 〈
ID
i
,
Q
i
=
c
P
,
*
〉 to L
1 and return Q
i
=
c
P as an answer (where * denotes the arbitrary value).
H
2
Queries. ℬ maintains a list of tuples 〈
ID
i
,
e
i
,
R
i
〉 in H
2 List L
2. On receiving a query 〈
ID
i
,
e
i
〉 to H
2, ℬ responds as follows.(1)
IfID
i already appears on the list L
2 in a tuple 〈
ID
i
,
e
i
,
R
i
〉, ℬ responds R
i as an answer.
(2)
Otherwise, pickR
i
∈
{
0,1
}
* at random, add 〈
ID
i
,
e
i
,
R
i
〉 to L
2 and return R
i as an answer.
Phase 1. After receivingparam from ℬ, 𝒜
I issues a sequence of polynomially bounded number of requests, each request being either aPartial-Private-Key-Extraction, aPrivate-Key-Extraction, aRequest-Public-Key, aReplace-Public-Key, orDecryption-Queries for an entity. We assume that 𝒜
I always makes the appropriate H
1 queries on the identity ID before making one of these requests and never makes a decryption query on a ciphertext obtained from the encryption oracle. ℬ replies to these requests as follows.
Partial-Private-Key-Extraction. ℬ maintains a Partial Private Key List of tuples 〈
ID
i
,
D
i
〉. On receiving a query ID
i, ℬ responds as follows.(1)
If〈
ID
i
,
D
i
〉 exist in Partial Private Key List, return D
i as an answer.
(2)
Otherwise, picki at random, so that Pr
[
i
≠
I
]
=
δ. (δ will be determined later.) If i
≠
I, search the L
1 for a tuple 〈
ID
i
,
Q
i
,
t
i
〉, compute D
i
=
t
i
P, add 〈
ID
i
,
D
i
〉 to the Partial Private Key List, and return D
i as an answer.
(3)
Ifi
=
I, return “Abort” and terminate.
Private-Key-Extraction. ℬ maintains a Private Key List of tuples 〈
ID
i
,
x
i
,
D
i
〉. On receiving a query ID
i, ℬ responds as follows.(1)
If〈
ID
i
,
x
i
,
D
i
〉 exist in Private Key List, return 〈
x
i
,
D
i
〉 as answer.
(2)
Otherwise, ifi
≠
I, run the simulation algorithm Request-Public-Key to get a tuple 〈
ID
i
,
x
i
,
PK
i
〉 and the simulation algorithm Private-Key-Extraction to get a tuple 〈
ID
i
,
D
i
〉, add 〈
ID
i
,
x
i
,
D
i
〉 to the Private Key List, and return 〈
x
i
,
D
i
〉 as an answer. (Note that if the corresponding public key has been replaced, such a private key query is not allowed.)
(3)
Ifi
=
I, return “Abort” and terminate.
Request-Public-Key. ℬ maintains a Public Key List of tuples 〈
ID
i
,
x
i
,
PK
i
〉. On receiving a query ID
i, ℬ responds as follows.(1)
If〈
ID
i
,
x
i
,
PK
i
〉 exist in Public Key List, return PK
i as an answer.
(2)
Otherwise, choosex
i
∈
Z
N
*, compute PK
i
=
x
i
H
1
(
ID
i
), add 〈
ID
i
,
x
i
,
PK
i
〉 to the Public Key List, and return PK
i as an answer.
Replace-Public-Key. 𝒜
I may replace any public key with a new value of its choice and ℬ records all the changes.
Decryption-Queries. On receiving a query 〈
ID
i
,
PK
i
,
C
〉, where C
=
(
c
1
,
c
2
) and PK
i
=
x
i
H
1
(
ID
i
). ℬ responds as follows.(1)
Ifi
≠
I and PK
i is the correct public key not a replaced one, ℬ decrypts C by using the corresponding private key.
(2)
Otherwise, searchL
2 for a tuple 〈
ID
i
,
e
i
,
R
i
〉. If such a tuple exists, ℬ retrieves the related R
i to compute M
∥
σ
=
c
2
⊕
R
i and returns M as an answer.
(3)
Otherwise,ℬ picks R
i
∈
{
0,1
}
* at random, computes M
∥
σ
=
c
2
⊕
R
i and returns M as an answer. Add 〈
ID
i
,
e
i
,
R
i
〉 to L
2.
Challenge Phase. 𝒜
I then outputs two messages (
M
0
,
M
1
) and a challenge identity ID
*. On receiving a challenge query 〈
ID
*
,
(
M
0
,
M
1
)
〉:(1)
IfID
*
≠
ID
I, ℬ aborts the game.
(2)
Otherwise,ℬ selects r
*
∈
Z
N
* and σ
∈
{
0,1
}
* randomly, computes c
1
*
=
r
*
P and H
2
(
e
(
SK
ID
*
,
c
1
*
)
)
=
c
2
*
⊕
(
M
β
∥
σ
) (note that ℬ does not know “r
*”), returns C
*
=
(
c
1
*
,
c
2
*
) as a target ciphertext.
Phase 2. 𝒜
I requests in the same ways as inPhase 1. Moreover, no private key extraction on ID
* is allowed and no decryption query can be made on the ciphertext C
* for the combination of identity ID
* and public key PK
ID
* that encrypted plaintext M
β.
Guess. 𝒜
I should make a guess β
′ for β. The adversary wins the game if β
′
=
β.
Analysis. By A
s
k
H
2
* we denote the event that (
ID
*
,
e
i
*
) has been queried to H
2. Also, by A
s
k
H
1
* we denote the event that ID
* has been queried to H
1. If happens, ℬ will be able to solve the BDH problem by choosing a tuple 〈
ID
i
,
e
i
,
R
i
〉 from L
2 and computing H
2
(
e
i
) with the probability at least 1
/
q
H
2. Hence, we have ϵ
′
≥
(
1
/
q
H
2
)
Pr
[
A
s
k
H
2
*
].
It is easy to notice that ifℬ does not abort, the simulations ofPartial-Key-Extract,Private-Key-Request,Public-Key-Request, and the simulated target ciphertext are identically distributed as the real one from the construction.
Now, we evaluate the simulation of the decryption oracle. If a public key PKID has not been replaced nor PKID has been produced by reselecting x
i
∈
Z
N
*, the simulation is perfect as ℬ knowing the private key SKID corresponding to PKID. Otherwise, simulation error may occur while ℬ is running the decryption oracle simulation specified above. Let D
e
c
E
r
r be this event. Suppose that ID, PKID, C, where C
=
(
c
1
,
c
2
) and PK
ID
=
x
ID
P, have been issued as a valid decryption query. Even if C is valid, there is a possibility that C can be produced without querying (
ID
,
e
i
) to H
2. Let V
a
l
i
d be an event that C is valid; let A
s
k
H
2 and A
s
k
H
1 be events that (
ID
,
e
i
) have been queried to H
2 and ID have been queried to H
1, respectively. Since D
e
c
E
r
r is an event that V
a
l
i
d
∣
¬
A
s
k
H
2 happens after the entire simulation and q
D decryption oracle queries being performed, we have Pr
[
D
e
c
E
r
r
]
=
q
D
Pr
[
V
a
l
i
d
∣
¬
A
s
k
H
2
], where,
(12)
Pr
⁡
[
V
a
l
i
d
∣
¬
A
s
k
H
2
]
≤
Pr
⁡
[
V
a
l
i
d
∧
A
s
k
H
1
∣
¬
A
s
k
H
2
]
+
Pr
⁡
[
V
a
l
i
d
∧
¬
A
s
k
H
1
∣
¬
A
s
k
H
2
]
≤
Pr
[
A
s
k
H
1
∣
¬
A
s
k
H
2
]
+
Pr
[
V
a
l
i
d
∣
¬
A
s
k
H
1
∧
¬
A
s
k
H
2
]
≤
q
H
1
2
ω
+
1
N
.
Now, the event(
A
s
k
H
2
*
∨
(
A
s
k
H
1
*
∣
¬
A
s
k
H
2
*
)
∨
D
e
c
E
r
r
)
∣
¬
A
b
o
r
t is denoted by E, where  A
b
o
r
t denotes an event that ℬ aborts during the simulation. The probability ¬
A
b
o
r
t that happens is given by δ
q
prv
+
q
par
(
1
-
δ
) which is maximized at δ
=
1
-
1
/
(
q
prv
+
q
par
+
1
). Hence, we have Pr
[
¬
A
b
o
r
t
]
≤
1
/
e
(
q
prv
+
q
par
+
1
), where e denotes the base of the natural logarithm.
IfE does not happen, it is clear that 𝒜
I does not gain any advantage greater than 1
/
2 to guess β due to the randomness of the output of the random oracle H
2. Namely, we have Pr
[
β
′
=
β
∣
¬
E
]
≤
1
/
2.
By definition ofϵ, we have
(13)
ϵ
<
|
Pr
⁡
[
β
′
=
β
]
-
1
2
|
=
|
1
2
Pr
[
β
′
=
β
∣
¬
E
]
Pr
[
¬
E
]
+
Pr
⁡
[
β
′
=
β
∣
E
]
Pr
⁡
[
E
]
-
1
2
|
≤
|
1
2
Pr
⁡
[
¬
E
]
+
Pr
⁡
[
E
]
-
1
2
|
=
|
1
2
(
1
-
Pr
⁡
[
E
]
)
+
Pr
⁡
[
E
]
-
1
2
|
=
1
2
Pr
⁡
[
E
]
≤
1
2
Pr
⁡
[
¬
A
b
o
r
t
]
×
(
Pr
⁡
[
A
s
k
H
2
*
]
+
Pr
⁡
[
A
s
k
H
1
*
∣
¬
A
s
k
H
2
*
]
+
Pr
⁡
[
D
e
c
E
r
r
]
)
≤
e
(
q
prv
+
q
par
+
1
)
2
(
q
H
2
ϵ
′
+
q
H
1
2
ω
+
q
D
q
H
1
2
ω
+
q
D
N
)
.
Consequently, we obtainϵ
′
>
(
1
/
q
H
2
)
(
2
ϵ
/
e
(
q
prv
+
q
par
+
1
)
-
q
H
1
/
2
ω
-
q
D
q
H
1
/
2
ω
-
q
D
/
N
).Lemma 8.
The CL-PKE scheme is(
q
H
1
,
q
H
2
,
q
p
a
r
,
q
p
u
b
,
q
p
r
v
,
q
D
,
ϵ
)-IND-CCA secure against Type II attacker 𝒜 in the random oracle assuming that the BDH problem is ϵ
′-intractable, where ϵ
′
>
(
1
/
q
H
2
)
(
2
ϵ
/
e
(
q
p
r
v
+
1
)
-
q
H
1
/
2
ω
-
q
D
q
H
1
/
2
ω
-
q
D
/
N
).Proof.
In this lemma, a Type II models an “insider” adversary, who has access tomsk but cannot replace public keys of entities.
Let𝒜
II be a Type II IND-CCA adversary against our scheme. Suppose that 𝒜
II has the advantage ϵ, makes q
H
i queries to random oracle H
i
(
i
=
1,2
), and q
D decryption queries. We show how to construct an algorithm ℬ to solve the BDH problem with the instance of (
P
,
a
P
,
b
P
,
c
P
) by interacting with 𝒜
II.
At the beginning,ℬ simulates the algorithm Setup for 𝒜
II by supplying 𝒜
II with p
a
r
a
m
=
{
G
1
,
G
2
,
e
,
P
,
X
,
H
1
,
H
2
}, where H
1, H
2 are random oracles that will be controlled by ℬ. ℬ chooses an index I uniformly at random with 1
≤
I
≤
q
H
1.
The adversary𝒜
II may make queries of the random oracles H
i
(
i
=
1,2
) at any time during its attack. ℬ responds as follows.
H
1
Queries. ℬ maintains a list of tuples 〈
ID
i
,
Q
i
〉 in H
1 List L
1. On receiving a query ID
i to H
1, ℬ responds as follows.(1)
IfID
i already appears on the list L
1 in a tuple 〈
ID
i
,
Q
i
〉, ℬ responds Q
i as an answer.
(2)
Otherwise, ifi
≠
I, choose Q
i
∈
G
1
* at random and add 〈
ID
i
,
Q
i
〉 to L
1 and return Q
i as an answer.
H
2
Queries. ℬ maintains a list of tuples 〈
ID
i
,
e
i
,
R
i
〉 in H
2 List L
2. On receiving a query 〈
ID
i
,
e
i
〉 to H
2, ℬ responds as follows.(1)
IfID
i already appears on the list L
2 in a tuple 〈
ID
i
,
e
i
,
R
i
〉, ℬ responds R
i as an answer.
(2)
Otherwise, pickR
i
∈
{
0,1
}
* at random, add 〈
ID
i
,
e
i
,
R
i
〉 to L
2, and return R
i as an answer.
Phase 1. After receivingparam from ℬ, 𝒜
II issues a sequence of polynomially bounded number of requests, each request being either aPrivate-Key-Extraction, aRequest-Public-Key, orDecryption-Queries for an entity. We assume that 𝒜
II always makes the appropriate H
1 queries on the identity ID before making one of these requests and never makes a decryption query on a ciphertext obtained from the encryption oracle. ℬ replies to these requests as follows.
Private-Key-Extraction. ℬ maintains a Private Key List of tuples 〈
ID
i
,
x
i
,
D
i
〉. On receiving a query ID
i, ℬ responds as follows.(1)
If〈
ID
i
,
x
i
,
D
i
〉 exist in Private Key List, return 〈
x
i
,
D
i
〉 as an answer.
(2)
Otherwise, picki at random, so that Pr
[
i
≠
I
]
=
δ. (δ is the same as it is in the proof of Lemma 7.) If i
≠
I, run the simulation algorithm Request-Public-Key to get a tuple 〈
ID
i
,
x
i
,
PK
i
〉 and compute D
i
=
s
Q
i, add 〈
ID
i
,
x
i
,
D
i
〉 to the Private Key List, and return 〈
x
i
,
D
i
〉 as an answer.
(3)
Ifi
=
I, return “Abort” and terminate.
Request-Public-Key. ℬ maintains a Public Key List of tuples 〈
ID
i
,
x
i
,
PK
i
〉. On receiving a query ID
i, ℬ responds as follows.(1)
If〈
ID
i
,
x
i
,
PK
i
〉 exist in Public Key List, return PK
i as an answer.
(2)
Otherwise, ifi
≠
I, choose x
i
∈
Z
N
*, compute PK
i
=
x
i
H
1
(
ID
i
), add 〈
ID
i
,
x
i
,
PK
i
〉 to the Public Key List, and return PK
i as an answer.
(3)
Ifi
=
I, set PK
i
=
a
P, add 〈
ID
i
,
*
,
PK
i
=
a
P
〉 to the public key list, and return PK
i
=
a
P as an answer (where * denotes the arbitrary value).
Decryption-Queries. On receiving a query 〈
ID
i
,
PK
i
,
C
〉, where C
=
(
c
1
,
c
2
). ℬ responds as follows.(1)
Ifi
≠
I, ℬ decrypts C by using the private key 〈
x
i
,
D
i
〉.
(2)
Otherwise, searchL
2 for a tuple 〈
ID
i
,
e
i
,
R
i
〉. If such a tuple exists, ℬ retrieves the related R
i to compute M
∥
σ
=
c
2
⊕
R
i and returns M as an answer.
(3)
Otherwise,ℬ picks R
i
∈
{
0,1
}
* at random, computes M
∥
σ
=
c
2
⊕
R
i, and returns M as an answer. Add 〈
ID
i
,
e
i
,
R
i
〉 to L
2.
Challenge Phase. 𝒜
II then outputs two messages (
M
0
,
M
1
) and a challenge identity ID
*. On receiving a challenge query 〈
ID
*
,
(
M
0
,
M
1
)
〉:(1)
IfID
*
≠
ID
I, ℬ aborts the game.
(2)
Otherwise,ℬ selects r
*
∈
Z
N
* and σ
∈
{
0,1
}
* randomly, computes c
1
*
=
r
*
P and H
2
(
e
(
SK
ID
*
,
c
1
*
)
)
=
c
2
*
⊕
(
M
β
∥
σ
), returns C
*
=
(
c
1
*
,
c
2
*
) as a target ciphertext.
Phase 2. 𝒜
II repeats the same methods it used inPhase 1. Moreover, no private key extraction on ID
* is allowed and no decryption query can be made on the ciphertext C
* for the combination of identity ID
* and public key PK
ID
* that encrypted plaintext M
β.
Guess. 𝒜
II should make a guess β
′ for β. The adversary wins the game if β
′
=
β.
Analysis. This part is similar toAnalysis in the proof of Lemma 7.
Consequently, we obtainϵ
′
>
(
1
/
q
H
2
)
(
2
ϵ
/
e
(
q
prv
+
1
)
-
q
H
1
/
2
ω
-
q
D
q
H
1
/
2
ω
-
q
D
/
N
).These two lemmas complete the proof of Theorem6.Furthermore, in our CL-PKE scheme,G
1
=
E
N
(
a
,
b
) is an elliptic curve over the ring Z
N, where N
=
p
q. According to Theorem 6, in order to run the algorithm on E
N
(
a
,
b
), such as addition and scalar multiplication, we should construct two elliptic curves E
p
(
a
,
b
) and E
q
(
a
,
b
) firstly and execute the corresponding operation on them, respectively. Then, we use the results of operation on E
p
(
a
,
b
) and E
q
(
a
,
b
) to present the operation on E
N
(
a
,
b
), which means that we should factoring N into p and q firstly. Therefore, the security of our CL-PKE scheme is also based on the intractability of factoring the large number.


## 3.3. Comparison to Related Schemes

In this section, we compare the proposed scheme with other related CL-PKE schemes on the computation complexity of encryption (Enc) and decryption (Dec), security level (Sec-Lev), and security assumption (Sec-Ass), where RSA in Table1 represents the problem of factoring the large number. Without considering the addition of two points and hash function on the elliptic curves, all the schemes have three major operations, that is, Pairing (P), Scalar Multiplication (S), and Exponentiation (E).Table 1
Comparison of the CL-PKE schemes.
Schemes
Enc
Dec
Sec-Lev
Sec-Ass
[2]
3P + 1S + 1E
1P + 1S
IND-CCA secure
GBDHP
[4]
1P + 2S + 1E
1P + 2S
IND-CCA secure
BDH
[5]
3S + 1E
1P + 3S
IND-CCA secure
K-BDHI
[6]
1P + 3S + 1E
4P
Strong type I/II secure
3-DDH
[7]
2P + 2S + 2E
2P + 1S
IND-CCA secure
BDH
Our scheme
1P + 2S
1P
IND-CCA secure
BDH/RSAThe essential operation of our proposed scheme is to compute a bilinear pairing. According to [16], the computation of a bilinear pairing becomes efficient. From Table 1, compared with the related works, our scheme needs only one pairing and two scalar multiplications in Encrypt and one pairing operation inDecrypt, which will consume less energy while preserving a higher security level. Therefore, the scheme proposed in this paper is more suitable to be applied in IoT with the characteristics of low cost, low power, multifunctional sensor nodes that are small in size and communicate wirelessly with each other node in a short distance.


## 4. Application to Internet of Things

In this section, based on our proposed scheme, we present a protocol to protect the confidentiality and integrity of the transmitting information between the gateway node and the sensor node.In IoT, Smart Car, as illustrated in Figure1, the gateway nodes in the car is responsible for transmitting the information of driving, such as the speed and location that are collected by sensor nodes fixed in the car, to the platform so that it can be monitored in real time. Furthermore, the gateway node will deliver the data and signaling obtained from the platform to sensor nodes for updating and managing equipments. Consequently, the transmitted information between the gateway node and the sensor nodes should be protected in confidentiality and integrity from being eavesdropped and destroyed by an adversary and damaging the normal operation of a Smart Car as a result.Figure 1
Transmitting the data and signaling to the sensor node in a Smart Car.Considering the sensor node with identityID
∈
{
0,1
}
ω in the initial phase, the details of this encryption scheme are as follows.The algorithms ofSetup,Partial-Private-Key-Extract,Set-Secret-Value,Set-Private-Key, andSet-Public-Key are the same as that of the proposed CL-PKE scheme in Section 3.1.Encrypt. To encrypt M
∈
{
0,1
}
*, the gateway node of the Smart Car selects a random value r
∈
Z
N
*, computes C
=
(
c
1
,
c
2
) such that
(14)
c
1
=
r
P
,
c
2
=
(
M
∥
ID
)
⊕
H
2
(
e
(
PK
ID
,
r
X
)
)
sends the ciphertext C
=
(
c
1
,
c
2
) to the sensor node.Decrypt. To decrypt ciphertext C
=
(
c
1
,
c
2
), sensor node fixed in the car uses its private key SKID and computes
(15)
M
′
∥
ID
′
=
c
2
⊕
H
2
(
e
(
SK
ID
,
c
1
)
)
.
The sensor node checks whether the equation ID
′
=
ID holds. If the verification succeeds, return M
′ as the legal data and signaling. Otherwise, return “Reject”.According to the encryption scheme above, this encryption scheme can not only protect the confidentiality of the transmitted data and signaling between gateway node and sensor node in the Smart Car, but also the integrity. This is because the sensor node can determine the transmitted data that was distorted or destroyed by an adversary or the reasons of environment in the public wireless channel, provided thatID
′ is not equal to ID in the phase of Decrypt. Moreover, there is only one pairing operation in Decrypt, which satisfies the characteristics of low-cost, low-power, and low-computation of the sensor node in the Smart Car.


## 5. Conclusion

We have proposed a CL-PKE scheme on the elliptic curve over the ringZ
n and proved that the scheme is IND-CCA secure in the random oracle model, relative to the intractability of the BDHP and factoring the large number problem. A comparison in Table 1 concludes that the proposed scheme is advantageous over the existing related schemes on performance. Due to the appealing properties, based on the proposed one, we also present another CL-PKE scheme for Smart Car in the end, which can provide confidentiality and integrity.



---

*Source: 980274-2014-03-12.xml*