An Efficient and Provably-Secure Certificateless Public Key Encryption Scheme for Telecare Medicine Information Systems

Abstract

Telecare Medicine Information Systems (TMIS) promote the traditional medical and healthcare services by information and communication technology. Since the physician and caregiver can monitor the patient’s physiological condition remotely in TMIS, the confidentiality of this sensitive data should be protected, which is the key issue in the Health Insurance Portability and Accountability Act. In this paper, we propose an efficient certificateless public key encryption scheme without bilinear pairing for TMIS. Our proposal is proved to be secure in the random oracle model under the hardness assumption of computational Diffie-Hellman problem. Moreover, after modifying the original model of the certificateless encryption, this scheme achieves Girault’s trust level 3. Compared with the related protocols, the perform evaluations show that our scheme is more efficient and appropriate to collocate with low power mobile devices for TMIS.

Introduction

Telecare Medicine Information Systems (TMIS), a typical telemedicine technology based on the wireless mobile telecommunication, consist of the lightweight devices with limited memory, small bandwidth and low power [1]. In TMIS, as shown in Fig. 1, the patient’s physiological condition (e.g., blood pressure, pulse oximeter and temperature) can be monitored in time by a physician and caregiver remotely, which is possible to bring the advantages of telemedicine directly into the patient’s home. These electronic medical records (EMR) transmitted in public channel should be protected for ensuring patient’s privacy.

Fig. 1

Telecare medicine information system architecture

The Health Insurance Portability and Accountability Act [2], enacted by the United States Congress in 1996, provided the guidelines for privacy and security regulations that the confidentiality of the information between patient and physician should be assured. The privacy and security issues vest the patient’s rights to understand and control the use of his/her sensitive information, such as name, telephone number, medical record number [3, 4]. Thus, a secure encryption scheme is essential to safeguard the confidentiality of the data related to personal health in TMIS.

According to the above descriptions, the requirements of the encryption scheme for TMIS should own the following properties.

• 1. Efficiency: In TMIS, low power consumption, limited memory space and small bandwidth are the most important issues for medical mobile device designing. The patient wishes he/she can be served anywhere for a long period. Thus, an efficient protocol is significant for extending the executing time of this mobile device.

• 2. Confidentiality: The data transmitted in the public channel between patient and doctor is all sensitive to the patient, which refers to his/her privacy. The patient does not want anyone (include the medical server) to access his/her privacy except physician. A secure protocol designed for TMIS should be provided to protect the confidentiality of the patient’s sensitive information.

In the traditional public key encryption primitive, to encrypt a message, a public key infrastructure (PKI) is used to provide an assurance through the certificates issued by a certification authority (CA). However, a PKI is responsible for managing the certificate, including distribution, storage, revocation and verification of certificates, which places a computational burden on the entity. In addition, the computational ability and memory space of mobile devices in TMIS are limited. Therefore, the PKI-based encryption scheme is not suitable for TMIS. To avoid the management of digital certificate, Shamir [5] proposed the notion of identity based public key cryptography (ID-PKC) by deriving the user’s public key directly from its identity information, such as e-mail address and IP address. Moreover, Boneh and Franklin presented a practical identity based encryption (IBE) scheme firstly in [6]. Nevertheless, the inherent key escrow problem in ID-PKC is a great drawback [7] since that the malicious medical server (MS) enables to eavesdrop all the sensitive messages about the patient. Hence, these two cryptographic primitive are not suitable for protecting the entity’s privacy in lightweight mobile devices, such as in TMIS.

To solve these problems above, certificateless public key cryptography (CL-PKC) was introduced by Al-Riyami and Paterson [8]. In the certificateless encryption (CLE) protocol, the user combines a secret value picked by itself with the partial private key obtained from the key generation center (KGC) to generate the private key, rather than generating it completely by private key generator (PKG) in IBE. Consequently, KGC cannot access the user’s private key to decrypt his/her ciphertext any more.

Several CLE schemes have been proposed in the last few years [9–14]. Libert and Quisquater [9] gave a method to achieve generic CLE constructions which were provably chosen ciphertext attacks (CCA) secure in the random oracle model. In 2007, Huang and Wong [10] proposed a generic construction of certificateless encryption which could be proven secure against the malicious-but-passive KGC attack in the standard model, and their scheme was the first one to be proven secure in the standard model. In order to resist the strong adversaries in the standard model, Dent et al. [11] presented the first strongly secure CLE scheme. In 2010, Sun and Li [12] constructed a short-ciphertext CLE scheme in the standard model with achieving adaptive chosen ciphertext security (CCA2-secure). Due to the property of CL-PKC, the above CLE constructions made use of IBE as a building block, which resulted in pairing based schemes. Being aware of the computation cost in the pairing based CLE schemes, Baek et al. [13] proposed a CLE scheme without pairing firstly in the random oracle model. In 2011, Lai et al. [14] modified Baek et al’s scheme to enjoy the Girault’s trust level 3 [15], the same trust level reached by a traditional PKI.

In this paper, we modify the original CLE model in [8] to achieve the Girault’s trust level 3. This revised model limits the power of MS to generate false public key for the patient. Moreover, based on this model, we propose an efficient CLE scheme without pairing for TMIS, and prove that it is secure in the random oracle model against the chosen ciphertext attacks. The new proposal needs only one scalar multiplication in decryption phase, which reduces the computational cost of patient considerably. Finally, after comparing the computation and communication cost between this scheme and others, we find that our protocol offers a better performance in efficiency.

In the next section, we briefly review the notions of computational assumptions, the Girault’s trust level, and the model of CLE and its security. In Section A new CLE scheme, we propose a new CLE protocol for TMIS and analyze the security of it. In Section Comparisons, we compare the efficiency with related schemes and conclude the paper in Section Conclusions.

Preliminaries

Computational assumptions

The following computational hardness assumptions will be used in the rest of the paper.

• Definition 1 Discrete Logarithm (DL) problem: Let G be an additive cyclic group with prime order p, and P be a generator of G. Given (P, Q ∈ G), find an integer x ∈ Z _p ^* satisfying Q = xP.

  The DL assumption is that there is no polynomial time algorithm that can solve the DL problem with non-negligible probability.

• Definition 2 Computational Diffie-Hellman (CDH) problem: Let G be an additive cyclic group with prime order p, and P be a generator of G. Given (Q = xP, R = yP) ∈ G ² for any x, y ∈ Z _p ^*, compute xyP.

  The CDH assumption is that there is no polynomial time algorithm that can solve the CDH problem with non-negligible probability.

Let algorithm $\mathcal{A}$ be a CDH adversary who has the advantage Adv $(\mathcal{A})$ = |Pr[$\mathcal{A}$(P,xP,yP) = xyP]| in solving the CDH problem. This probability is measured over random choices of x, y ∈ Z _p ^* and the point P. Adversary $\mathcal{A}$ solves the CDH problem with (t, ε) if and only if the advantage of $\mathcal{A}$ is greater than ε in running time t. The CDH problem is said to be (t, ε)-intractable if there is no algorithm $\mathcal{A}$ that solves this problem with (t, ε).

Girault’s trust level

The Girault’s trust level [15] provides the trust hierarchy for public key cryptography, which can be used to evaluate the credibility of the authority.

• Level 1. The authority (e.g., the CA in a PKI, the KGC in an identity based or certificateless cryptography) knows (or can easily compute) users’ secret keys. Therefore, the authority can impersonate any user at any time without being detected.

• Level 2. The authority does not know (or cannot easily compute) users’ secret keys. Nevertheless, it can still impersonate users by generating false guarantees (e.g., false certificates in a PKI, false public keys in a certificateless cryptography).

• Level 3. The authority cannot compute users’ secret keys, and it can be proven that it generates false guarantees of users if it does so.

According to these definitions, we can easily find that the original certificateless cryptography falls into Level 2, and the traditional PKI achieves Level 3.

Certificateless public key encryption

In this subsection, we revise the original model of CLE in [8], and the improved one promotes the trust level of MS to Level 3.

A CLE scheme for TMIS consists of seven probabilistic polynomial time (PPT) algorithms: Setup, Patient-Key-Generation, Partial-Key-Extract, Set-Private-Key, Set-Public-Key, Encrypt and Decrypt. These algorithms are defined as follows:

Setup:

On input a security parameter 1^k, MS returns the system parameters params, master public key mpk and the master secret key msk. After this algorithm is over, the MS publishes params and mpk, and keeps the msk secretly.

Patient-Key-Generation:

On input the system parameters params, the patient returns a secret key sk and a public key pk.

Partial-Key-Extract:

On input params, msk, the patient’s identity ID _P and his/her public key pk, MS executes this algorithm and returns a partial private key D _P to the patient via a confidential and authentic channel, and a partial public key P _P .

Set-Private-Key:

On input params, the patient’s partial private key D _P and secret key sk, this algorithm returns the patient’s private key SK _P .

Set-Public-Key:

On input params, the patient’s partial public key P _P and public key pk, this algorithm returns the public key PK _P to the patient.

Encrypt:

Running by the doctor. On input params, message M, the patient’s identity ID _P , and his/her public key PK _P , this algorithm returns a ciphertext C.

Decrypt:

Running this deterministic algorithm by the patient. On input params, the ciphertext C, and his/her private key SK _P , this algorithm returns a plaintext message M or a “Reject” message.

The Patient-Key-Generation algorithm in this model must be operated prior to the Partial-Key-Extract algorithm. In this way, the patient chooses his/her secret key sk and public key pk firstly. Then the MS binds the patient’s public key with his/her identity ID _P to generate the patient’s partial key D _P . Specifically, in this model of CLE, although MS can replace the patient’s public key pk, there will exist two working public keys for one patient, such as pk and pk′. Moreover, two working different public keys PK _P and PK _P ^′ binding one patient can result from two partial private keys, and only the MS has ability to generate these two working partial private keys. Therefore, the MS’s forgery is easily tracked, which indicates that our proposal achieves the Girault’s trust level 3.

Security model

In CLE scheme, as defined in [8], there are two types of adversaries $\mathcal{A}$ _I and $\mathcal{A}$ _II . A Type-I adversary $\mathcal{A}$ _I acts as a dishonest user who does not have the MS’s master secret key but it is able to replace the public keys of arbitrary patient with its own choices value. By contrast, a Type-II adversary $\mathcal{A}$ _II acts as an honest-but-curious MS who controls the master secret key msk (hence it can compute the patient’s partial secret key). Besides, Type-II adversary $\mathcal{A}$ _II is allowed to receive private keys for arbitrary identities but cannot replace any patient’s public key.

• Definition 3 A CLE scheme Π is said to be secure against adaptive chosen ciphertext attack (IND-CCA secure) if neither polynomial bounded adversary $\mathcal{A}$ of Type-I nor Type-II has a non-negligible advantage against the challenger in the following game:

  Setup:

  The challenger C takes a security parameter 1^k as input, and operates the Setup algorithm in Section Certificateless public key encryption. Then it gives the resulting public parameters params and mpk to $\mathcal{A}$. If $\mathcal{A}$ is of Type-I, it keeps the master secret key msk to itself. Otherwise (i.e., if $\mathcal{A}$ is of Type-II), returns msk to $\mathcal{A}$.

  Phase 1:

  A can query the following oracles:

  • (1) Public-Key-Request-Oracle: Upon receiving a public key query for a user’s identity ID, C computes (sk, pk) and the related (P _ID , D _ID ), then it generates PK _ID and sends it to $\mathcal{A}$.

  • (2) Partial-Key-Extract-Oracle: (For Type-I adversary only.) Upon receiving a partial key query for a user’s identity ID and pk, C computes (P _ID , D _ID ) and sends them to $\mathcal{A}$.

  • (3) Private-Key-Request-Oracle: Upon receiving a private key query for a user’s identity ID, C computes (sk, pk) and (P _ID , D _ID ), then generates SK _ID and sends it to $\mathcal{A}\kern-4pt$. It outputs ⊥ (denotes failure) if the user’s public key has been replaced in the case of Type-I adversary.

  • (4) Public-Key-Replace-Oracle: (For Type-I adversary only.) For identity ID and its valid public key, $\mathcal{A}$ replaces this public key with a new one of its choice. This new value will be recorded and used by C in the coming computations or responses to the adversary’s queries.

  • (5) Decryption-Oracle: On input a ciphertext and an identity ID, C returns the corresponding plaintext by using of the private key of the user, even if the public key for ID has been replaced.

  Challenge Phase:

  Once $\mathcal{A}$ decides that Phase 1 is over, it outputs and submits two messages (M ₀, M ₁), together with a challenger’s identity ID^*. Note that $\mathcal{A}$ is not allowed to know the private key of ID^* in any way. The challenger C picks a random bit β ∈ {0, 1} and computes C ^*, which is the encryption of M _β under the current public key PK _ID*. If the output of Encrypt is ⊥, adversary $\mathcal{A}$ loses the game. Otherwise, C ^* is delivered to $\mathcal{A}$.

  Phase 2:

  $\mathcal{A}$ issues a new sequence of queries as in Phase 1. However, a decryption query on the challenge ciphertext C ^* for the combination of $\left({\mathrm{ID}}^{\ast },P{K}_{I{D}^{\ast }}\right)$ is not allowed.

  Guess:

  $\mathcal{A}$ outputs its guess β′ for β. It wins the game if β′ = β.

The guessing advantage of $\mathcal{A}$ in this game is defined to be $Adv\left(\mathcal{A}\right)=\left| \Pr \left(\beta \prime =\beta \right)-\frac{1}{2}\right|$. $\mathcal{A}$ breaks an IND-CCA secure CLE scheme Π with (t, q _H , q _par , q _pub , q _prv , q _D , ε) if and only if the advantage of $\mathcal{A}$ that makes q _H times to a 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 ε within running time t. The scheme Π is said to be (t, q _H , q _par , q _pub , q _prv , q _D , ε)-IND-CCA secure if there is no adversary $\mathcal{A}$ that breaks IND-CCA secure scheme Π with (t, q _H , q _par , q _pub , q _prv , q _D , ε).

A new CLE scheme

In this section, we propose a new CLE scheme without bilinear pairing to protect the confidentiality of data between the patient and the doctor. The notations used throughout this paper are listed in Table 1.

Table 1 Notation defined in this scheme

Construction

The proposed CLE scheme as shown in Fig. 2 consists of the following seven PPT algorithms.

Setup:

Let G be a cyclic group of prime order p with an arbitrary generator P ∈ G. The MS selects x ∈ Z _p ^∗ randomly and computes X = xP as the master public key. Then, it chooses two collision resistant hash functions ${H}_1:{\left\{0,1\right\}}^{l_0}\times {G}^{*}\times {G}^{*}\to {Z}_p^{\ast }$ and H ₂ : G* → {0,1}^l. The system parameters are params = {p, G, P, X, H ₁ , H ₂ }, and the master secret key is msk = x.

Patient-Key-Generation:

The patient picks y ∈ Z _p ^∗ uniformly at random and computes Y = yP, and he/she returns (sk, pk) = (y, Y).

Partial-Key-Extract:

The MS picks α ∈ Z _p ^∗ at random and computes r _P  = αP and z _P  = α + xH ₁(ID _P ‖r _P ‖pk), where ID _P is the patient’s identity. After that, MS returns (P _P , D _P ) = (r _P , z _P ) as the patient’s partial key.

Set-Private-Key:

Set SK _P  = (sk,D _p ) = (y,z _P ), it returns SK _P as the patient’s private key.

Set-Public-Key:

Let PK _P  = (pk,P _p ) = (Y,r _P ), it returns PK _P as the patient’s public key.

Encrypt:

Let the bit-length of M be l ₁, where l = l ₀ + l ₁ ∈ N (N denotes the set of positive integer). The doctor picks u ∈ Z _p ^∗ randomly and computes the ciphertext:

$$ {c}_1= uP, $$

c ₂ = H ₂(u(Y + r _P  + H ₁(ID _P ‖r _P ‖pk)X)) ⊕ (M||ID _P ). Note that the bit-length of M||ID _P is equal to l. Then, the doctor delivers the ciphertext C = (c ₁, c ₂) to the patient.

Decrypt:

To decrypt C, the patient computes

$$ M\prime \left|\right|{\mathrm{ID}}_P^{\prime }={H}_2\left(\left({z}_P+y\right)\cdot {c}_1\right)\oplus {c}_2. $$

Fig. 2

Our CLE scheme for TMIS

Check whether ID _P ^′ = ID _P . If not, output “Reject”. Else, the patient returns M′ as the plaintext of C.

The above decryption algorithm is consistent if C is a valid ciphertext, then it can derive that:

$$ \begin{array}{l}{H}_2\left(\left({z}_P+y\right)\cdot {c}_1\right)\oplus {c}_2={H}_2\left(\left(\alpha +x{H}_1\left({\operatorname{ID}}_P\Vert {r}_P\Vert pk\right)+y\right)\cdot uP\right)\oplus {c}_2={H}_2\left(\left({r}_P+X{H}_1\left({\operatorname{ID}}_P\Vert {r}_P\Vert pk\right)+Y\right)\cdot u\right)\oplus {c}_2={H}_2\left(\left({r}_P+X{H}_1\left({\operatorname{ID}}_P\Vert {r}_P\Vert pk\right)+Y\right)\cdot u\right)\oplus {H}_2\left(u\left(Y+{r}_P+{H}_1\left({\mathrm{ID}}_P\Vert {r}_P\Vert pk\right)X\right)\right)\oplus \left(M\Vert {\operatorname{ID}}_P\right)=M\Vert {\operatorname{ID}}_P.\hfill \end{array} $$

Security analysis

In this subsection, we prove that the proposed CLE scheme constructed in the previous section is secure in the random oracle model.

Theorem 1. Given H ₁ and H ₂ are two collision resistant hash functions. This CLE scheme is IND-CCA secure in the random oracle model assuming that there is no polynomial time algorithm that can solve the CDH problem with non-negligible probability.

This theorem following from two lemmas will show that our CLE scheme is secure against the Type-I and Type-II adversaries whose behaviors are described in Definition 3.

Lemma 1. This CLE scheme is $\left(t,{q}_{H_1},{q}_{H_2},{q}_{par},{q}_{pub},{q}_{prv},{q}_D,\epsilon \right)$ -IND-CCA secure against the Type-I adversary $\mathcal{A}$ in the random oracle assuming the CDH problem is (t′, ε′)-intractable, where

$$ \begin{array}{c}\hfill \epsilon \prime >\frac{1}{q_{H_2}}\left(\frac{2\epsilon }{e\left({q}_{prv}+1\right)}-\frac{q_D{q}_{H_1}}{2^{l_0}{p}^2}-\frac{q_D}{p}\right),\hfill \\ {}\hfill t\prime >t+2\left({q}_{par}+{q}_{pub}+{q}_{prv}\right){t}_{sm}+{q}_D{q}_{H_2}{t}_{sm}+2{t}_{sm},\hfill \end{array} $$

and t _sm is the time for computing scalar multiplication of the additive cyclic group G.

Proof Assuming there exists a Type-I adversary $\mathcal{A}$ _I simulating an “outside” adversary, who replaces the public key of arbitrary identities but cannot corrupt the master secret key.

Suppose that there is another PPT algorithm $\mathcal{B}$ can solve the CDH problem in the instance of (p, P, aP, xP) with probability at least ε′ and the time at most t′ by interacting with $\mathcal{A}$ _I . To solve this problem, $\mathcal{B}$ needs to simulate a challenger to perform each algorithm of IND-CCA game for $\mathcal{A}$ _I as follows:

Setup:

Algorithm $\mathcal{B}$ sets X = xP, where x ∈ Z _p ^∗ is the master secret key that is unknown to $\mathcal{B}$. Then, $\mathcal{B}$ gives $\mathcal{A}$ _I the params = {p, G. P, X, H ₁, H ₂} as CLE system parameters, where H ₁ and H ₂ are random oracles. Adversary $\mathcal{A}$ _I may make queries of these two random oracles at any time during its attack. $\mathcal{B}$ responds as follows:

H ₁ queries :

$\mathcal{B}$ maintains a list of tuples 〈(ID,r _ID ,Y),v〉 in H ₁-List L ₁. On receiving a query (ID, r _ID , Y) to H ₁:

• (1) If 〈(ID,r _ID ,Y),v〉 already appears on the list L ₁, $\mathcal{B}$ responds v as an answer.

• (2) Otherwise, pick v ∈ Z _p ^∗ randomly, add 〈(ID,r _ID ,Y),v〉 to L ₁ and return v as an answer.

H ₂ queries :

$\mathcal{B}$ maintains a list of tuples 〈(ID,T),R〉 in H ₂-List L ₂. On receiving a query (ID, T) to H ₂:

• (1) If 〈(ID,T),R〉 exists in the list L ₂, $\mathcal{B}$ responds R as an answer.

• (2) Otherwise, choose R ∈ {0, 1}^l uniformly at random, add 〈(ID,T),R〉 to L ₂ and return R as an answer.

Phase 1:

$\mathcal{A}$ _I can issue a number of the following oracle queries.

Partial-Key-Extract-Oracle :

$\mathcal{B}$ maintains a PartialKeyList of tuples 〈ID,(r _ID ,z _ID )〉. On receiving a query ID, $\mathcal{B}$ responds as follows:

• (1) If 〈ID,(r _ID ,z _ID )〉 exists in PartialKeyList, return (r _ID , z _ID ) as an answer.

• (2) Otherwise, pick z _ID , v ∈ Z _p ^∗ at random, and compute r _ID  = z _ID P − vX. Add (ID, r _ID , v) to L ₁ and 〈ID,(r _ID ,z _ID )〉 to PartialKeyList, return (r _ID , z _ID ) as an answer.

Public-Key-Request-Oracle :

$\mathcal{B}$ maintains a PublicKeyList of tuples 〈ID,(r _ID ,Y),coin〉. On receiving a query ID, $\mathcal{B}$ responds as follows:

• (1) If 〈ID,(r _ID ,Y),coin〉 exists in PublicKeyList, return PK _ID  = (r _ID ,Y) as an answer.

• (2) Otherwise, choose coin ∈ {0, 1} at random so that Pr[coin = 0] = δ. (δ will be defined later.)

• (3) If coin = 0, do the following:

  • (a) If 〈ID,(r _ID ,z _ID )〉 exists in PartialKeyList, pick y ∈ Z _p ^∗ at random and compute Y = yP. Then, add 〈ID,(y,z _ID )〉 to PrivateKeyList (which will be defined later) and 〈ID,(r _ID ,Y),coin〉 to PublicKeyList respectively, return PK _ID  = (r _ID ,Y) as an answer.

  • (b) Otherwise, run the Partial-Key-Extract-Oracle to get partial keys (r _ID , z _ID ) about ID. Pick y ∈ Z _p ^∗ at random and compute Y = yP. Then, add 〈ID,(r _ID ,z _ID )〉 to PrivateKeyList and 〈ID,(r _ID ,Y),coin〉 to PublicKeyList respectively, return PK _ID  = (r _ID , Y) as an answer.

  • (4) Otherwise (if coin = 1), pick α, y ∈ Z _p ^∗ at random and compute r _ID  = αP, Y = yP, add 〈ID,(y,∗),α〉 to PrivateKeyList (where “*” denotes the arbitrary value), and 〈ID,(r _ID ,Y),coin〉 to PublicKeyList, return PK _ID  = (r _ID , Y) as an answer.

Private-Key-Request-Oracle :

$\mathcal{B}$ maintains a PrivateKeyList of tuples 〈ID,(y,z _ID ),α〉. On receiving a query ID, β responds as follows:

• (1) Run Public-Key-Request-Oracle on ID to get a tuple 〈ID,(r _ID ,Y),coin〉 from PublicKeyList.

• (2) If coin = 0, search a tuple 〈ID,(y,z _ID ),α〉 in PrivateKeyList and return SK _ID  = (y, z _ID ) as answer.

• (3) Otherwise, return “Abort” and terminate.

Public-Key-Replace-Oracle :

$\mathcal{A}$ _I may replace any public key with a new value of its choice and $\mathcal{B}$ records all the changes.

Decryption-Oracle :

On receiving a query 〈ID, PK _ID , C〉, where C = (c ₁, c ₂) and PK _ID  = (r _ID , Y). $\mathcal{B}$ responds as follows:

• (1) Search a tuple 〈ID,(r _ID ,Y),coin〉 in PublicKeyList.

• (2) If such a tuple exists and coin = 0.

  • (a) Search PrivateKeyList for a tuple 〈ID,(y,z _ID )〉.

  • (b) Compute M ′ ‖ID ′ = H ₂((z _ID  + y) ⋅ c ₁) ⊕ c ₂.

  • (c) If ID′ = ID, return M′as plaintext and “Reject” otherwise.

• (3) Else, if such a tuple exists and coin = 1.

  • (a) Perform H ₁ queries to get a tuple 〈(ID,r _ID ,Y),v〉.

  • (b) If there exists 〈(ID,T),R〉 ∈ L ₂ such that c ₂ = R ⊕ (M‖ID), return M as plaintext and “Reject” otherwise.

• (4) Else, if such a tuple does not exist (which means that the public key of a target user is replaced by A _I ), perform the same algorithm in (3)

Challenge Phase:

Once $\mathcal{A}$ _I decides that Phase 1 is over, it outputs two messages (M ₀, M ₁) and a challenge identity ID^*. On receiving a challenge query 〈ID^∗,(M ₀,M ₁)〉, $\mathcal{B}$ responds as follows:

• (1) Run Public-Key-Request-Oracle on ID^* to get a tuple $\langle {\mathrm{ID}}^{*},\left({r}_{I{D}^{*}},{Y}^{*}\right), coin\rangle \in$ PublicKeyList.

• (2) If coin = 0, return “Abort” and terminate.

• (3) Otherwise, do the following:

  • (a) Search a tuple 〈ID^∗,(y ^∗,∗),α ^∗〉 in PrivateKeyList. (In this case, we know that ${r}_{I{D}^{*}}={\alpha}^{*}P,{Y}^{*}={y}^{*}P$.)

  • (b) Pick c ₂ ^∗ ∈ {0,1}^l and β ∈ {0, 1} at random.

  • (c) Set ${c}_1^{*}= aP,\varGamma =a{r}_{I{D}^{*}}$ and ${v}^{*}={H}_1\left({\mathrm{ID}}^{*}\Vert {r}_{I{D}^{*}}\Vert {Y}^{*}\right)$.

  • (d) Define

    ${H}_2\left(a\left({Y}^{*}+{r}_{I{D}^{*}}+{H}_1\left({\mathrm{ID}}^{*}\Vert {r}_{I{D}^{*}}\Vert {Y}^{*}\right)X\right)\right)={c}_2^{*}\oplus \left({M}_{\beta}\Vert {\mathrm{ID}}^{*}\right).$ Note that $\mathcal{B}$ does not know “a”.

• (4) Return C ^∗ = (c ₁ ^∗,c ₂ ^∗) as the target ciphertext.

Phase 2:

$\mathcal{A}$ _I makes the same queries as it did in Phase 1. However, there is no Partial-Key-Extract-Oracle or Private-Key-Request-Oracle query on ID^* is allowed. Also, no Decryption-Oracle query should be made on the ciphertext C ^∗ = (c ₁ ^∗,c ₂ ^∗) for the combination of ID^* and $P{K}_{I{D}^{\ast }}$ that encrypted plaintext M _β .

Guess:

$\mathcal{A}$ _I outputs a guess β′ for β, and wins the game if β′ = β. Then, $\mathcal{B}$ will be able to solve the CDH problem by computing $\left({c}_1^{*}\cdot {z}_{I{D}^{*}}-\varGamma \right)/{v}^{\ast }$.

Analysis

We denote the event that ID^* has been queried to H ₁ as Ask H ₁ ^∗. Also, by Ask H ₂ ^∗, we denote the event that 〈(ID^∗,T ^∗),R ^∗〉 has been queried to H ₂. Provided that the event Ask H ₂ ^∗ happens, $\mathcal{B}$ will enable to solve the CDH problem by picking a tuple 〈(ID^∗,T ^∗),R ^∗〉 in L ₂ and compute $\left({c}_1^{*}\cdot {z}_{I{D}^{*}}-\varGamma \right)/{v}^{*}$ with probability at least $1/{q}_{H_2}$. Hence, we have $\epsilon \prime \ge \left(1/{q}_{H_2}\right) \Pr \left[\mathrm{Ask}{H}_2^{\ast}\right]$.

If $\mathcal{B}$ does not abort during the game, the simulations of Partial-Key-Extract-Oracle, Public-Key-Request-Oracle, Private-Key-Request-Oracle and the target ciphertext is identically distributed as the real attack in our construction. Because $\mathcal{B}$’s responses to all hash queries are uniformly and independently distributed as in the real attack, and all responses to $\mathcal{A}$ _I can pass the validity test unless $\mathcal{B}$ aborts in the game.

Thus, we find that when a public key PK _ID has not been replaced or produced under coin = 1, the simulation is perfect as $\mathcal{B}$ knowing the corresponding private key SK _ID . Otherwise, a simulation error may occur in Decryption-Oracle, and let DecErr denote this event. Suppose that ID, PK _ID  = (r _ID ,Y) and C = (c ₁, c ₂) have been issued as a valid decryption query. Even if C is a valid ciphertext, there is a possibility that C can be produced without querying 〈(ID,T),R〉 to H ₂. Let Valid be an event that C is a valid ciphertext, Ask H ₁ and Ask H ₂ be events that (ID, r _ID , Y) has been queried to H ₁ and (ID,T) to H ₂ respectively. Since DecErr is an event that Valid|¬Ask H ₂ happens during the entire simulation and q _D Decryption-Oracle queries are operated, we have Pr[DecErr] = q _D Pr[Valid|¬Ask H ₂]. However,

$$ \begin{array}{c}\hfill \Pr \left[\left.\mathbf{Valid}\right|\neg \mathbf{Ask}{H}_2\right]\le \Pr \left[\left.\mathbf{Valid}\wedge \mathbf{Ask}{H}_1\right|\neg \mathbf{Ask}{H}_2\right]\hfill \\ {}\hfill + \Pr \left[\left.\mathbf{Valid}\wedge \neg \mathbf{Ask}{H}_1\right|\neg \mathbf{Ask}{H}_2\right]\hfill \\ {}\hfill \le \Pr \left[\left.\mathbf{Ask}{H}_1\right|\neg \mathbf{Ask}{H}_2\right]\hfill \\ {}\hfill + \Pr \left[\left.\mathbf{Valid}\right|\neg \mathbf{Ask}{H}_1\wedge \neg \mathbf{Ask}{H}_2\right]\hfill \\ {}\hfill \le \left({q}_{H_1}/\left({2}^{l_0}{p}^2\right)\right)+\left(1/p\right).\hfill \end{array} $$

Let the event (Ask H ₂ ^* ∨ DecErr)|¬ Abort be denoted by E, where Abort is an event that $\mathcal{B}$ aborts during the simulation. The probability that ¬Abort happens is given by ${\delta}^{q_{prv}}\left(1-\delta \right)$ which is maximized at δ = 1 − 1/(q _prv  + 1). Hence, we have Pr[¬ Abort] ≤ 1/(e(q _prv  + 1)), where e denotes the base of the natural logarithm.

If E does not happen, it is clear that $\mathcal{A}$ _I does not gain any advantage greater than 1/2 to guess β due to the randomness of the output of the random oracle H ₂. Namely, we have Pr[β ′ = β|¬ E] ≤ 1/2.

By definition of ε, we have

$$ \begin{array}{l}\epsilon <\left| \Pr \left[\beta \prime =\beta \right]-\left(1/2\right)\right|=\left| \Pr \left[\beta \prime =\beta |\neg \mathbf{E}\right] \Pr \left[\neg \mathbf{E}\right]+ \Pr \left[\beta \prime =\beta |\mathbf{E}\right] \Pr \left[\mathbf{E}\right]-\left(1/2\right)\right|\le \left|\left(1/2\right) \Pr \left[\neg \mathbf{E}\right]+ \Pr \left[\mathbf{E}\right]-\left(1/2\right)\right|=\left|\left(1/2\right)\left(1- \Pr \left[\mathbf{E}\right]\right)+ \Pr \left[\mathbf{E}\right]-\left(1/2\right)\right|=\left(1/2\right) \Pr \left[\mathbf{E}\right]\le \left( \Pr \left[\mathbf{Ask}{H}_2^{*}\right]+ \Pr \left[\mathbf{DecErr}\right]\right)/\left(2 \Pr \left[\neg \mathbf{Abort}\right]\right)\le \left(e\left({q}_{prv}+1\right)/2\right)\left({q}_{H_2}\epsilon \prime +\left({q}_D{q}_{H_1}/\left({2}^{l_0}{p}^2\right)\right)+\left({q}_D/p\right)\right).\hfill \end{array} $$

Consequently, we obtain

$$ \epsilon \prime >\frac{1}{q_{H_2}}\left(\frac{2\epsilon }{e\left({q}_{prv}+1\right)}-\frac{q_D{q}_{H_1}}{2^{l_0}{p}^2}-\frac{q_D}{p}\right). $$

The running time of adversary $\mathcal{B}$ is

$$ t\prime >t+2\left({q}_{par}+{q}_{pub}+{q}_{prv}\right){t}_{sm}+{q}_D{q}_{H_2}{t}_{sm}+2{t}_{sm}, $$

Where t _sm denotes the time for computing scalar multiplication of the additive cyclic group G.

The following lemma shows that our CLE scheme is secure against the Type-II adversary.

Lemma 2. This CLE scheme is $\left(t,{q}_{H_1},{q}_{H_2},{q}_{par},{q}_{pub},{q}_{prv},{q}_D,\upepsilon \right)$ -IND-CCA secure against the Type-II adversary $\mathcal{A}$ in the random oracle assuming the CDH problem is (t′, ε′)-intractable, where

$$ \epsilon \prime >\frac{1}{q_{H_2}}\left(\frac{2\epsilon }{e\left({q}_{prv}+1\right)}-\frac{q_D{q}_{H_1}}{2^{l_0}{p}^2}-\frac{q_D}{p}\right), $$

$$ t\prime >t+2\left({q}_{pub}+{q}_{prv}\right){t}_{sm}+{q}_D{q}_{H_2}{t}_{sm}+2{t}_{sm}, $$

and t _sm is the time for computing scalar multiplication of the additive cyclic group G.

Proof Assuming there exists an algorithm $\mathcal{A}$ _II who models an “insider” adversary. Suppose that another PPT algorithm $\mathcal{B}$ enables to solve the CDH problem though $\mathcal{A}$ _II with probability at least ε′ and the time at most t′.

$\mathcal{B}$ is given (p, P, aP, bP) as an instance of the CDH problem. In order to solve this problem, $\mathcal{B}$ needs to simulate a challenger to execute each phase of IND-CCA game for $\mathcal{A}$ _II as follows:

Setup:

Algorithm B picks the master secret key x ∈ Z _p ^∗ randomly and computes X = xP. Then, $\mathcal{B}$ gives the system parameters params = {p,G,P,X,H ₁,H ₂} to ${\mathcal{A}}_{II}$, where H ₁ and H ₂ are random oracles. Adversary ${\mathcal{A}}_{II}$ queries these two random oracles at any time during its attack. $\mathcal{B}$ responds as follows:

H ₁ queries :

$\mathcal{B}$ maintains a list of tuples 〈(ID,r _ID ,Y),v〉 in H ₁ -List L ₁. On receiving a query (ID,r _ID ,Y) to H ₁:

• (1) If 〈(ID,r _ID ,Y),v〉 already appears on the list L ₁, return v as an answer.

• (2) Otherwise, pick v ∈ Z _p ^∗ at random, add 〈(ID,r _ID ,Y),v〉 to L ₁ and return v as an answer.

H ₂ queries :

$\mathcal{B}$ maintains a list of tuples 〈(ID,T),R〉 in H ₂-List L ₂. On receiving a query (ID,T) to H ₂:

• (1) If 〈(ID,T),R〉 exists in the list L ₂, return R as an answer.

• (2) Otherwise, choose R ∈ {0,1}^l uniformly at random, add 〈(ID,T),R〉 to L ₂ and return R as an answer.

Phase 1:

${\mathcal{A}}_{II}$ issues the following oracle queries.

Public-Key-Request-Oracle :

$\mathcal{B}$ maintains a PublicKeyList of tuples 〈ID,(r _ID ,Y),coin〉. On receiving a query ID, $\mathcal{B}$ responds as follows:

• (1) If 〈ID,(r _ID ,Y),coin〉 exists in PublicKeyList, return PK _ID  = (r _ID ,Y) as an answer.

• (2) Otherwise, pick coin ∈ {0,1} at random so that Pr[coin = 0] = δ. (δ is the same as it in the proof of Lemma 1.)

• (3) If coin = 0, choose y, α ∈ Z _p ^∗ at random and compute Y = yP, r _ID  = αP and z _ID  = α + xH ₁(ID||r _ID ||Y). Then, add 〈ID,(y,z _ID ),α〉 to PrivateKeyList and add 〈ID,(r _ID ,Y),coin〉 to PublicKeyList respectively, return PK _ID  = (r _ID ,Y) as an answer.

• (4) Otherwise (if coin = 1), pick α, y ∈ Z _p ^∗ at random and compute r _ID  = αaP, Y = yP and z _ID  = α + bxH ₁(ID||r _ID ||Y). Then, add 〈ID,(y,∗),α〉 to PrivateKeyList (where “*” denotes the arbitrary value), and 〈ID,(r _ID ,Y),coin〉 to PublicKeyList,return PK _ID  = (r _ID ,Y) as an answer.

Private-Key-Request-Oracle :

$\mathcal{B}$ maintains a PrivateKeyList of tuples 〈ID,(y,z _ID ),α〉. On receiving a query ID, $\mathcal{B}$ responds as follows:

• (1) Perform Public-Key-Request-Oracle on ID to get a tuple 〈ID,(r _ID ,Y),coin〉 from PublicKeyList.

• (2) If coin = 0, search PrivateKeyList for a tuple 〈ID,(y,z _ID ),α〉 and return SK _ID  = (y,z _ID ) as an answer.

• (3) Otherwise, return “Abort” and terminate.

Decryption-Oracle :

On receiving a query < ID, PK _ID , C >, where C = (c ₁,c ₂) and PK _ID  = (r _ID ,Y). $\mathcal{B}$ responds as follows:

• (1) Search a tuple 〈ID,(r _ID ,Y),coin〉 in PublicKeyList. If such a tuple exists and coin = 0, search PrivateKeyList for a tuple 〈ID,(y,z _ID )〉 (Note that 〈ID,(r _ID ,Y),coin〉 must exist in PublicKeyList. While coin = 0, the tuple 〈ID,(y,z _ID ),α〉 exists in PrivateKeyList). Then, set SK _ID  = (y,z _ID ) and operate Decrypt. Finally, return the results of Decrypt algorithm.

• (2) Otherwise (if coin = 1), run H ₁ queries to access a tuple 〈(ID,r _ID ,Y),v〉. If there exists 〈(ID,T),R〉 in L ₂ such that c ₂ = R ⊕ (M||ID), return M as plaintext and “Reject” otherwise.

Challenge Phase:

When Phase 1 is over, ${\mathcal{A}}_{II}$ output two messages (M ₀,M ₁) and a challenge identity ID*. On receiving a challenge query < ID^∗, (M ₀,M ₁) >:

• (1) Taking ID* as input, $\mathcal{B}$ runs Public-Key-Request-Oracle and gets a tuple $\langle {\mathrm{ID}}^{*},\left({r}_{I{D}^{*}},{Y}^{*}\right), coin\rangle$ from PublicKeyList.

• (2) If coin = 0, return “Abort” and terminate.

• (3) Otherwise, do the following:

  • (a) Search for a tuple $\langle {\mathrm{ID}}^{*},\left({y}^{*},{z}_{I{D}^{*}}\right),{\alpha}^{*}\rangle$ from PrivateKeyList. (In this case, we know that Y ^∗ = y ^∗ P, ${r}_{I{D}^{*}}={\alpha}^{*} aP$.)

  • (b) Choose c ₂ ^∗ ∈ {0,1}^l and β ∈ {0,1} randomly.

  • (c) Set c ₁ ^∗ = aP and ${v}^{*}={H}_1\left({\mathrm{ID}}^{*}\left|\right|{r}_{I{D}^{*}}\left|\right|{Y}^{*}\right)$.

  • (d) Define

    ${H}_2\left(a\left({Y}^{*}+{r}_{I{D}^{*}}+{H}_1\left({\mathrm{ID}}^{*}\left|\right|{r}_{I{D}^{*}}\left|\right|{Y}^{*}\right)X\right)\right)={c}_2^{*}\oplus \left({M}_{\beta}\left|\right|{\mathrm{ID}}^{*}\right).$ Note that $\mathcal{B}$ does not know “a”.

• (4) Return C ^∗ = (c ₁ ^∗,c ₂ ^∗) as the target ciphertext.

Phase 2:

${\mathcal{A}}_{II}$ repeats the same methods as in Phase 1. Moreover, no private key extraction on ID* is allowed and no decryption query can be made on the ciphertext C* that encrypted plaintext M _β .

Guess:

${\mathcal{A}}_{II}$ outputs a guess β′ for β, and wins the game if β′ = β. Then, $\mathcal{B}$ will be able to solve the CDH problem by computing $\left({c}_1^{\ast}\cdot {z}_{I{D}^{\ast }}-{r}_{I{D}^{\ast }}\right)/\left(x\cdot {v}^{\ast}\right)$.

Analysis:

Similar to Analysis in the proof of Lemma 1.

Consequently, we obtain

$$ \epsilon \hbox{'}>\frac{1}{q_{H_2}}\left(\frac{2\epsilon }{e\left({q}_{prv}+1\right)}-\frac{q_D{q}_{H_1}}{2^{l_0}{p}^2}-\frac{q_D}{p}\right). $$

The running time of adversary $\mathcal{B}$ is

$$ {t}^{\prime }>t+2\left({q}_{pub}+{q}_{prv}\right){t}_{sm}+{q}_D{q}_{H_2}{t}_{sm}+2{t}_{sm}, $$

Where t _sm denotes the time for computing scalar multiplication of the additive cyclic group G.

To sum up, we complete the proof of Theorem 1.

Comparisons

In this section, we compare our CLE scheme with previous protocols on the computation complexity of encryption (Enc) and decryption (Dec), the bandwidth of the ciphertext (Bandwidth) and the running time (Time) of each scheme. Without considering the addition of two points, the hash function and exclusive-OR operations, we denote the cost of a bilinear pairing by P, the cost of an exponentiation by E, and the cost of a scalar multiplication in the additive cyclic group by S.

We simulate the cryptographic operations by using of MIRACL (version 5.6.1, [16]). The experiments are performed on a laptop using the Intel Core i5-2400 at a frequency of 3.10 GHz with 3GB memory and Windows XP operation system. Then the average running time of each operation in 100 times is obtained and demonstrated in Table 2. For pairing-based schemes, in order to implement in practice efficiently, we use the Fast-Tate-Pairing in MIRACL, which is defined over the MNT curve E/F _q [17] with characteristic a 160-bit prime and embedding degree 4. For ECC-based protocols, we employ the parameters secp160r1 [18], where p = 2¹⁶⁰ − 2³¹ − 1. Furthermore, we denote the length of an element in a multiplicative group to be 1024-bit. Based on the above parameter settings, the total running time to finish one round of Encrypt-Decrypt in different schemes are illustrated in Table 3. In addition, we simulate the whole procedure of our CLE scheme and the operation time is only 3.76 ms.

Table 2 Cryptographic operation time

Table 3 Comparison of the related schemes

To the energy consumption, it is calculated as W = P × t based on the power (P) and execution time (t). Suppose that the max power of central processing unit (CPU) is 95 W. Then the energy consumption of CPU in different schemes is demonstrated in Fig. 3, which indicates that when the CPU is at full capacity, our scheme consumes less energy than others in the process of encryption and decryption.

Fig. 3

Energy consumption of CPU

For the communication cost, we analyze it in terms of the bandwidth of the transmitted ciphertext. Suppose that the output of one way hash function is 160-bit, and the symmetric cipher is 128-bit (e.g., AES). In our protocol and [9], each ciphertext contains one point and one hash value, thus the bandwidths of our protocol and [9] are (160 + 160)/8 = 40 bytes respectively. In [13] and [14], each ciphertext contains one exponentiation and one hash value, thus the bandwidths of [13] and [14] are (1024 + 160)/8 = 148 bytes respectively. In Dent et al.’s scheme [11], the ciphertext contains four exponentiations, the bandwidth of it is (1024 × 4)/8 = 512 bytes. At last, in the scheme of [12], the ciphertext contains one point and one symmetric cipher, and therefore the bandwidth of it is (160 + 128)/8 = 36 bytes. The detailed comparison results are also listed in Table 3, and the bandwidth of our scheme is a smaller one.

Notably, the cost of computation and communication and the power consumption at the patient side of this scheme is far less than others. These analyses show that our scheme enables to provide an efficient method to protect the confidential information between patient and doctor in TMIS.

Conclusions

We have proposed an efficient certificateless encryption paradigm for TMIS to protect the privacy of patients. In point of security, it shows that our scheme is IND-CCA secure in the random oracle model under the hardness of CDH problem. Moreover, our protocol limits the power of the medical server to replace the patient’s public key. A thorough performance evaluation and experiments indicate that our proposal is advantageous over the related schemes in efficiency. These attributes render our scheme a promising approach in the privacy protection of TMIS with lightweight devices.