1. Introduction

Public key cryptography (PKC) is an important technique to realize network and information security. In PKC, each user has a pair of keys, namely a public key and a private key. The public key is usually published to the public while the corresponding private key is only known to its owner. However, in traditional PKC, each user’s public key is generated randomly and does not contain any information associated with its owner. Therefore, it is infeasible to prove that a user is indeed the owner of a given public key. This problem can be solved by employing a trusted certification authority (CA) to generate public key certificates. A public key certificate is a digital signature issued by CA that binds a public key to the identity of its owner. By verifying a certificate, anyone can confirm whether a public key belongs to a user. This kind of certificate systems is referred to as public key infrastructure (PKI). However, the traditional PKI technology is faced with many practical challenges, especially the cumbersome certificate management problem. To eliminate the management of the certificates, Shamir [1] introduced the concept of identity-based cryptography (IBC) in 1984. In IBC, a user’s public key is his unique identity information such as an e-mail address or a telephone number, and his private key is generated by a trusted third party called private key generator (PKG). Because the identity is a natural link to a user, the ability to use identities as public keys eliminates the need for public key certificates. However, IBC inevitably suffers from the key escrow problem as all users’ private keys are known to the PKG.

In order to fill the gap between traditional PKC and IBC, Al-Riyami and Paterson [2] put forward the notion of certificateless public key cryptography (CL-PKC) in Asiacrypt 2003. In CL-PKC, a trusted third party called key generation center (KGC) is employed for generating a partial private key for each user. Each user generates a secret key and a public key, and then combines his secret key with the partial private key from the KGC to generate his full private key. Since KGC does not know any user’s private key, CL-PKC overcomes the key escrow problem inherent in IBC. However, as partial private keys should be sent to users via secure channels, CL-PKC suffers from the key distribution problem. This drawback limits the application of CL-PKC in the public networks.

In Eurocrypt 2003, Gentry [3] proposed another new paradigm called certificate-based cryptography (CBC), which represents an interesting balance between IBC and traditional PKC. As in traditional PKC, each user in CBC first generates a private key and a public key, and then requests a certificate from a CA. The certificate in CBC acts not only as a public key certificate (as in traditional PKC) but also as a partial decryption/signing key, namely that each user should combine his private key with his certificate to generate his decryption/signing key. This additional functionality provides an effective implicit certificate mechanism so that a user needs both his private key and certificate to perform some cryptographic operations (such as decryption and signing), while the other communication parties need not obtain the fresh information on this user’s certificate status. As a result, CBC eliminates the third-party query for the certificate status and simplifies the complicated certificate revocation problem in traditional PKC. As introduced by Gentry in [3], CBC can be used to construct efficient PKIs requiring fewer infrastructures than traditional ones. Furthermore, because the CA does not know the users’ private keys and the certificates can be sent to the users publicly, CBC overcomes both the key escrow and key distribution problems. Following Gentry’s pioneering work, numerous cryptographic schemes in the CBC setting (including many certificate-based encryption (CBE) schemes [4-11] and certificate-based signature (CBS) schemes [12-18]) have been proposed in the literature so far.

1.1 Motivation and contribution

The motivation of this paper is to develop a secure CBE scheme that does not depend on the costly bilinear pairings. As we know, compared with other common cryptographic operations such as scalar multiplications in the elliptic curve groups, the bilinear pairings may be the most expensive operations. Our experiment results show that the computation cost of the fastest Tate pairing is about 9 times as much as a scalar multiplication in the elliptic curve group under the 1024-bit RSA security level. As the computationally-heavy pairing operations will greatly aggravate the computation load of a device, they are extremely disliked by the computation-limited or power-constrained devices, such as smart phone, PDA. Therefore, as far as the efficiency, the cryptographic schemes without bilinear pairings would be more attractive. In 2013, Yao et al. [19] proposed a CBE scheme that does not use the bilinear pairings. They claimed that their scheme satisfies the chosen-ciphertext security in the random oracle model. Unfortunately, this is not ture. Cryptanalysis shows that Yao et al.’s CBE scheme fails in achieving the chosen-ciphertext security, even the weaker chosen-plaintext security. The insecurity of Yao et al.’s scheme lies in the fact that an adversary can easily break the ciphertext indistinguishability of their scheme without making any oracle queries.

In this paper, we first give a concrete attack to show that Yao et al.’s CBE scheme [19] does not achieve their security claim. Based on the Schnorr signature scheme [20,21] and the enhanced ElGamal public key encryption scheme proposed by Fujisaki and Okamoto [22], we newly develop a CBE scheme without depending on the bilinear pairings. Under the classic complexity assumption - computational Diffie-Hellman assumption, we formally prove that the proposed scheme satisfies the indistinguishable security under adaptive chosen-ciphertext attacks (i.e., the chosen-ciphertext security) in the random oracle model [23,24]. Compared with the previous pairing-based CBE schemes, the proposed scheme is more efficient in the computation efficiency. Due to avoiding the costly pairing operations, it is particularly suitable for the computation-limited or power-constrained devices.

1.2 Paper organization

The rest of this paper is organized as follows. In Section 2, we briefly review some related background definitions. In Section 3, we describe the attack against Yao et al.’s CBE scheme. The proposed CBE scheme is described and analyzed in Section 4. Finally, we draw our conclusion in Section

 

2. Preliminaries

2.1 Elliptic curve group and complexity assumption

Let p be a prime number and Fp be a prime finite field. Let a and b be two elements such that Δ = 4a3 + 27b2 ≠ 0 in Fp. An elliptic curve over Fp (denoted by E(Fp)) defined by the parameters a and b is the set of all solutions (x, y) ∈ Fp × Fp to the equation y2 = x3 + ax + b, together with an extra point O at infinity. The set of points on E(Fp) forms an abelian elliptic curve group

The point addition “+” in the elliptic curve group G is defined as follows: Let P, Q ∈ G, l1 be the line connecting P and Q (l1 be the tangent line to E(Fp) if P = Q), and R be the third point of intersection of the line l1 with E(Fp). Let l2 be the line connecting R and O. Then P + Q is the third point of intersection of the line l2 with E(Fp), namely P + Q and R are x-axial symmetry points. The scalar multiplication in the group G can be computed as follows:

The security of the CBE scheme proposed in this paper relies on the computational Diffie-Hellman (CDH) assumption in the group G.

Definition 1. Given a tuple (P, aP, bP) ∈ G3 for unknown a,b ∈ , the CDH problem in the group G is to compute abP ∈ G. The advantage of a probabilistic polynomial-time (PPT) algorithm ACDH in solving the CDH problem is defined as

The CDH assumption is that, for any PPT algorithm ACDH, the advantage Adv(ACDH) is negligible.

2.2 Formal model of certificate-based encryption

Usually, a CBE scheme is composed of five algorithms: (1) System setup algorithm Setup, which is performed by a CA to generate a master secret key msk and a set of public parameters params; (2) Key-pair generation algorithm KeyPairGen, which is performed by the user to generate a pair of private key and public key; (3) Certification algorithm Certify, which is performed by a CA to generate a certificate for each user in the system; (4) Encryption algorithm Encrypt, which is performed by the senders to encrypt the messages; (5) Decryption algorithm Decrypt, which is performed by the receivers to decrypt the received ciphertexts.

Fig. 1 gives the functional description of a CBE scheme.

Fig. 1.Functional description of a CBE scheme

Definition 2. A CBE scheme (Setup, KeyPairGen, Certify, Encrypt, Decrypt) is said to be correct if for any message M, C = Encrypt(params, M, IDU, PKU, CertU), then M = Decrypt(params, C, IDU, SKU, CertU), where the public parameters params, the private/publickey pair (SKU, PKU) and the certificate CertU are respectively generated according to the specification of the algorithms Setup, KeyPairGen and Certify.

As introduced in [3,6], the security model of CBE consists of two different types of adversaries, namely Type-I adversary (denoted by AI) and Type-II adversary (denoted by AII). The Type-I adversary AI simulates an uncertified user who knows the target user’s private key and can replace any user’s public key, but cannot access the target user’s certificate and the CA’s master secret key, while the Type-II adversary AII simulates a malicious CA in possession of the master secret key who can produce certificates for any users, but cannot access the target user’s private key and replace any user’s public key. It is clear that if a Type-II adversary AII is allowed to replace public keys, by producing the certificates on the false public keys, then it can easily break any user’s confidentiality.

In the security model of CBE, an adversary can make requests to some of the following five oracles adaptively. We assume that the challenger (or the simulator) keeps a history of “query-answer” when interacting with the adversaries. The oracles are described as follows:

(1) OCreateUser: On input an identity IDU, the challenger returns a public key PKU. If the identity IDU has not been created, then the challenger generates a set of private key SKU, public key PKU and certificate CertU for the identity IDU, and then returns PKU as the output. In this case, IDU is said to be created. Because the Type-II adversary AII simulates a malicious CA who will generate a certificate for any user by itself, it is possible that the challenger is not aware of the secret(s) used by the adversary AII to generate a certificate. Therefore, when creating a new user, the Type-II adversary AII should submit the secret(s) to the challenger to generate a certificate for that user. For simplicity, we assume that other oracles defined below only respond to an identity which has been created.

(2) OReplacePublicKey: On input an identity IDU and a public key , the challenger replaces the current public key PKU associated with the identity ID with . This oracle is only queried by the Type-I adversary AI, since the Type-II adversary AII is disallowed to replace public keys.

(3) OPrivateKey: On input an identity IDU, the challenger responds with a private key SKU associated with the identity IDU. Here, the Type-I adversary AI is disallowed to query this oracle on any identity for which the public key has been replaced. This restriction is imposed due to the fact that it is unreasonable to expect the challenger to be able to provide a private key of a user for which it does not know the private key.

(4) OCertificate: On input an identity IDU, the challenger responds with a certificate CertU associated with the identity IDU. This oracle is only queried by the Type-I adversary AI as the Type-II adversary AII can generate any user’s certificate by itself. Here, the Type-I adversary AI is disallowed to query this oracle on any identity for which the public key has been replaced. This restriction is imposed due to the fact that it is unreasonable to expect the challenger to be able to provide a certificate on a false public key.

(5) ODecrypt: On input an identity IDU and a ciphertext C, the challenger responds with the decryption of the ciphertext C.

The indistinguishable security under adaptive chosen-ciphertext attacks (i.e., the IND-CCA2 security) for CBE schemes is defined by two adversarial games IND-CCA2-I and IND-CCA2-II (see Fig. 2), in which a challenger interacts with the Type-I adversary AI and the Type-II adversary AII respectively.

Fig. 2.Adversarial games IND-CCA2-I and IND-CCA2-II

The game IND-CCA2-I is played between the challenger and the Type-I adversary AI, in which state represents some state information, Oracles-I means that the adversary AI can adaptively query the oracles OCreateUser, OReplacePublicKey, OPrivateKey, OCertificate and ODecrypt with the following constraints: (1) The target identity IDch cannot be submitted to the oracle OCertificate; (2) The target identity and the challenge ciphertext (IDch, Cch) cannot be submitted to the oracle ODecrypt. The game IND-CCA2-II is played between the challenger and the Type-II adversary AII, in which state represents some state information, Oracles-II means that the adversary AII can adaptively query the oracles OCreateUser, OPrivateKey and ODecrypt with the following constraints: (1) The target identity IDch cannot be submitted to the oracle OPrivateKey; (2) The target identity and the challenge ciphertext (IDch, Cch) cannot be submitted to the oracle ODecrypt.

In both the games IND-CCA2-I and IND-CCA2-II, we say that an adversary wins the game if β = β' . The adversary’s advantage in winning the game is defined to be

where X is eitherI or II.

Definition 3. A CBE scheme satisfies the IND-CCA2 security if no PPT adversary has non-negligible advantage in the games IND-CCA2-I and IND-CCA2-II.

In the above definition, if the adversary is disallowed to make any queries to the oracle ODecrypt, then we obtain the weaker chosen-plaintext security (i.e., the IND-CPA security) for the CBE schemes.

 

3. Cryptanalysis of Yao et al.’s CBE Scheme

In this section, we show that the CBE scheme without pairings proposed by Yao et al. [19] can not achieve either the IND-CCA2 security or the IND-CPA security.

3.1 Review of Yao et al.’s CBE scheme

Yao et al.’s CBE scheme [19] consists of the following five algorithms:

(1) Setup: Input a security parameter k. Generate two primes p and q such that p =2q + 1. Pick a generator g of . Pick x ∈ uniformly at random as master secret key msk = x, and compute master public key mpk = gx mod p. Choose hash functions: . The public parameters are params = {p, q, g, mpk, H1, H2}.

(2) KeyPairGen: Input the public parameters params. Pick s ∈ at random as the user U’s private key SKU and compute PKU = gs mod p as the user U’s public key. Return the private key and public key pair (SKU, PKU) = (s, gs).

(3) Certify: Input (params, msk, IDU, PKU). Pick y ∈ at random, compute cert1 = gy, cert2 = y + xH1(IDU, PKU) and cert3 = y + x(y + xH1(IDU, PKU)). Then it returns CertU = (cert1, cert2, cert3) as the certificate for the user U.

(4) Encrypt: Input (params, M, IDU, PKU, CertU), check whether gcert3 · (mpk)-cert2 = cert1. Then randomly choose r ∈ , compute C1 = gr, C2 = M · (PKU)r · (mpk)rH1(IDU,PKU) · (cert1)r and C3 = H2(gr, M). Output the ciphertext C = (C1, C2, C3).

(5) Decrypt: Input (params, C, IDU, SKU, CertU), compute . If H2(C1,M') = C3, returnM'. Otherwise return ⊥ indicating a decryption failure.

3.2 Cryptanalysis

In [19], Yao et al. claimed that their scheme achieves the IND-CCA2 security against both the Type-I adversary AI and the Type-II adversary AII. However, this is not true. The adversary AI (or AII) can easily break the ciphertext indistinguishability of Yao et al.’s scheme in the following way:

Since both the Type-I adversary AI and the Type-II adversary AII can carry out the above attack without making any oracle queries, Yao et al.’s scheme does not satisfy either the IND-CCA2 security or the weaker IND-CPA security against both AI and AII.

 

4. The Proposed CBE Scheme

In this section, we propose a new CBE scheme without bilinear pairing and prove it to achieve the IND-CCA2 security under the CDH assumption in the random oracle model.

4.1 Description of the scheme

Our CBE scheme is constructed by incorporating the Schnorr signature scheme [20,21] into the enhanced ElGamal public key encryption scheme proposed by Fujisaki and Okamoto [22]. A formal description of the proposed scheme is as follows:

(1) Setup: The CA does the following: generate an additive cyclic group G over elliptic curve E(Fp) as described in Section 2 and determine a generator P of the group G; choose a random value α ∈ and compute Ppub = αP; choose three cryptographic hash functions H1: {0,1}* × G × G → , H2: {0,1}n+l × {0,1}* × G × G → and H3: G → {0,1}n+l, where n and l denote the bit-length of a plaintext and a random bit string respectively; output the public parameters params = {E(Fp), G, q, P, Ppub, n, l, H1, H2, H3} and the master secret key msk = α .

(2) KeyPairGen: A user U chooses a random value xU ∈ as his private key SKU and computes his public key PKU = xUP.

(3) Certify: To generate a certificate for a user U with identity IDU and public key PKU, the CA chooses a random value yU ∈ and computes , where .

(4) Encrypt: To send a message M ∈ {0,1}n to a user U with identity IDU, the sender does the following: choose a random bit δ ∈ {0,1}l and compute r = H2(M, δ, IDU, PKU); compute X = rP and Y = (M║δ)⊕H3(rQU), where ; set C = (X, Y) as the ciphertext.

(5) Decrypt: To decrypt a received ciphertext C, a user U does the following: parse the ciphertext C as (X, Y) and compute ; check whether X = rP holds where r = H2(M, δ, IDU, PKU); accept M if it holds or reject the decryption otherwise.

4.2 Correctness

Theorem 1. The proposed CBE scheme is correct.

Proof. This theorem can be easily proved by the following equations:

4.3 Security

Theorem 2. In the random oracle model, the proposed CBE scheme achieves the IND-CCA2 security under the CDH assumption.

This theorem can be proved by combining the following two lemmas.

Lemma 1. Suppose that H1 ~ H3 are random oracles and AI is a Type-I adversary against the IND-CCA2 security of our CBE scheme with advantage ε when running in time τ, making at most qcu queries to the oracle OCreateUser, qrpk queries to the oracle OReplacePublicKey, qpk queries to the oracle OPrivateKey, qcer queries to the oracle OCertificate, qdec queries to the oracle ODecrypt and qi queries to the random oracles Hi (1 ≤ i ≤ 3). Then there exists an algorithm ACDH to solve the CDH problem in G with advantage

and running time τ' ≤ τ + (q1 + q2 + q3 + qrpk + qcer + qpk)O(1) + qcu(3 τm + O(1)) + qdec(4 τm + O(1)), where e is the Euler number and τm denotes the time for computing a scalar multiplication in G.

Proof. We show how to construct an algorithm ACDH to solve the CDH problem from the Type-I adversary AI. Assume that the algorithm ACDH is given a random CDH problem instance (G, p, P, aP, bP). Its goal is to compute abP by interacting with the adversary AI as follows:

In the setup phase of the game, the algorithm ACDH first sets Ppub = aP. It then starts the game IND-CCA2-I by supplying the adversary AI with the public parameters params = {E(Fp), G, q, P, Ppub, n, l, H1, H2, H3}, where H1 ~ H3 are random oracles controlled by the algorithm ACDH. Note that the master secret key msk is the value a which is unknown to the algorithm ACDH.

During the query-answer phase, the adversary AI can adaptively make queries to the oracles H1, H2, H3, OCreateUser, OReplacePublicKey, OPrivateKey, OCertificate and ODecrypt. The algorithm ACDH responds the adversary AI’s various queries as follows:

H1 queries: The algorithm ACDH maintains a list H1List of tuples . On receiving such a query on , the algorithm ACDH checks whether the list H1List contains a tuple . If it does, the algorithm ACDH outputs h1 to the adversary AI directly. Otherwise, it outputs a random value h1 ∈ to the adversary AI and inserts a new tuple into the list H1List.

H2 queries: The algorithm ACDH maintains a list H2List of tuples (M, δ, IDi, PKi, h2). On receiving such a query on (M, δ, IDi, PKi), the algorithm ACDH checks whether the list H2List contains a tuple (M, δ, IDi, PKi, h2). If it does, the algorithm ACDH outputs h2 to the adversary AI directly. Otherwise, it outputs a random value h2 ∈ to the adversary AI and inserts a new tuple (M, δ, IDi, PKi, h2) into the list H2List.

H3 queries: The algorithm ACDH maintains a list H3List of tuples (R, h3). On receiving such a query on R, the algorithm ACDH checks whether the list H3List contains a tuple (R, h3). If it does, the algorithm ACDH outputs h3 to the adversary AI directly. Otherwise, it outputs a random value h3 ∈ {0,1}n+l to the adversary AI and inserts a new tuple (R, h3) into the list H3List.

OCreateUser queries: The algorithm ACDH maintains a list UserList of tuples (IDi, PKi, SKi, yi, Certi, ci). On receiving such a query on IDi, the algorithm ACDH outputs PKi to the adversary AI directly if the list UserList contains a tuple (IDi, PKi, SKi, yi, Certi, ci). Otherwise, ACDH picks a random coin ci ∈ {0, 1} so that Pr{ci = 1} = γ for some value γ that will be determined later and performs as follows:

OReplacePublicKey queries: On receiving an identity IDi and a false public key , the algorithm ACDH retrieves a tuple of the form (IDi, PKi, SKi, yi, Certi, ci) from the list UserList. If ci = 1, it aborts. Otherwise, it replaces the tuple with

OPrivateKey queries: On receiving such a query on IDi, the algorithm ACDH retrieves a tuple of the form (IDi, PKi, SKi, yi, Certi, ci) from the list UserList and returns SKi to the adversary AI.

OCertificate queries: On receiving such a query on IDi, the algorithm ACDH retrieves a tuple of the form (IDi, PKi, SKi, yi, Certi, ci) from the list UserList. If ci = 1, ACDH aborts. Otherwise, it returns Certi to AI.

ODecrypt queries: On receiving such a query on (IDi, C = (X, Y)), the algorithm ACDH performs as follows:

At the challenge phase, the adversary AI outputs an identity IDch and two messages M0, M1 of equal length. The algorithm ACDH retrieves a tuple of the form (IDch, PKch, SKch, ych, Certch, cch) from the list UserList. If cch = 0, ACDH aborts. Otherwise, it randomly chooses β ∈ {0,1} and Ych ∈ {0,1}n+l, sets Xch = bP, and returns Cch = (Xch, Ych) as the challenge ciphertext to the adversary AI. Observe that the decryption of the challenge ciphertext Cch is and H2(Mβ, δ*, IDch, PKch) = b, where and δ* ∈ {0,1}l.

At the guess phase, the adversary AI outputs a bit β' which is ignored by the algorithm ACDH. To produce a result, the algorithm ACDH retrieves the secret values SKch = xch and ych associated with the target identity IDch from the list UserList, randomly chooses a tuple from the list H3List and computes

as the solution to the given CDH problem. It is easy to deduce that T = abP if

This completes the simulation. We now estimate the advantage of the algorithm ACDH in solving the given CDH problem. From the above construction, the simulation fails if any of the following events occurs:

Let E = (DecErr ∨ AskH2* ∨ AskH3*)|¬Abort. It is clear that if the event E does not happen, then the adversary AI does not gain any advantage greater than 1/2 in the above simulation. Therefore, we get Pr{β' = β|¬E} ≤ 1/2. By splitting Pr{β' = β}, we have

Hence, we get 2|Pr{β' = β} – 1/2} ≤ Pr{E}. By the definition of the adversary AI’s advantage in the game IND-CCA2-I, we have

We clearly have that Pr{¬Abort} = γ(1-γ)q , Pr{DecErr} ≤ qdec/2l and Pr{AskH2*} ≤ q2/2l, where q = qrpk + qcer is the total number of AI’s queries to the oracles OReplacePublicKey and OCertificate. The value of γ(1-γ)q is maximized at γmax = 1/(q + 1) . Thus, the probability that ACDH dose not abort is at least1/(e(q + 1)) . Therefore, we obtain

Since once the event AskH3* happens, the algorithm ACDH can solve the CDH problem by picking the correct tuple from the list H3List. Therefore, we obtain the advantage of the algorithm ACDH in solving the given CDH problem

From the simulation above, the running time of the algorithm ACDH is bound by τ' ≤ τ + (q1 + q2 + q3 + qrpk + qcer + qpk)O(1) + qcu(3 τm + O(1)) + qdec(4 τm + O(1)).

This completes the proof of Lemma 1. #

Lemma 2. Suppose that H1 ~ H3 are random oracles and AII is a Type-II adversary against the IND-CCA2 security of our CBE scheme with advantage ε when running in time τ, making at most qcu queries to the oracle OCreateUser, qpk queries to the oracle OPrivateKey, qdec queries to the oracle ODecrypt and qi queries to the random oracles Hi (1 ≤ i ≤ 3). Then there exists an algorithm ACDH to solve the CDH problem in G with advantage

and running time τ' ≤ τ + (q1 + q2 + q3 + qpk)O(1) + qcu(3 τm + O(1)) + qdec(4 τm + O(1)), where e is the Euler number and τm denotes the time for computing a scalar multiplication in G.

Proof. We show how to construct an algorithm ACDH to solve the CDH problem from the Type-II adversary AII. Assume that the algorithm ACDH is given a random CDH problem instance (G, p, P, aP, bP). Its goal is to compute abP by interacting with the adversary AII as follows:

In the setup phase of the game, the algorithm ACDH first randomly chooses a value α ∈ . It then computes Ppub = αP and starts the game IND-CCA2-II by supplying the adversary AII with the master key msk = α and the public parameters params = {E(Fp), G, q, P, Ppub, n, l, H1, H2, H3}, where H1 ~ H3 are random oracles controlled by the algorithm ACDH.

During the query-answer phase, the adversary AII can adaptively make queries to the oracles H1, H2, H3, OCreateUser, OPrivateKey and ODecrypt. The algorithm ACDH answers the adversary AII’s queries to the oracles H1, H2, H3 and ODecrypt in the same way as the proof of Lemma 1 and handles other oracle queries as follows:

OCreateUser queries: The algorithm ACDH maintains a list UserList of tuples (IDi, PKi, SKi, yi, Certi, ci). On receiving such a query on IDi, it outputs PKi to the adversary AII directly if the list UserList contains a tuple (IDi, PKi, SKi, yi, Certi, ci). Otherwise, after receiving a value yi ∈ from the adversary AII, it picks a random coin ci ∈ {0, 1} so that Pr{ci = 1} = γ for some value γ and performs as follows:

OPrivateKey queries: On receiving such a query on IDi, the algorithm ACDH aborts if ci = 1. Otherwise, it retrieves a tuple of the form (IDi, PKi, SKi, yi, Certi, ci) from the list UserList and returns SKi to the adversary AII.

At the challenge phase, the adversary AII outputs two messages M0 and M1 of equal length and an identity IDch. The algorithm ACDH retrieves a tuple of the form (IDch, PKch, SKch, ych, Certch, cch) from the list UserList. If cch = 0, ACDH aborts. Otherwise, it randomly chooses β ∈ {0, 1} and Ych ∈ {0, 1}n+l, sets Xch = bP, and returns Cch = (Xch, Ych) as the challenge ciphertext to the adversary AII. Observe that the decryption of the challenge ciphertext Cch is and H2(Mβ, δ*, IDch, PKch) = b, where δ* ∈ {0, 1}l.

At the guess phase, the adversary AII outputs a bit β' which is ignored by the algorithm ACDH. To produce a result, the algorithm ACDH retrieves the secret value ych associated with the identity IDch from the list UserList, randomly chooses a tuple (R, h3) from the list H3List and computes

as the solution to the given CDH problem. It is easy to deduce that T = abP if

As in the proof of Lemma 1, we can derive that the advantage of the algorithm ACDH in solving the given CDH problem is bounded by

where q = qpk is the total number of AII’s queries to the oracle OPrivateKey.

From the simulation above, the running time of the algorithm ACDH is bound by τ' ≤ τ + (q1 + q2 + q3 + qpk)O(1) + qcu(3 τm + O(1)) + qdec(3 τm + O(1)).

This completes the proof of Lemma 2. #

4.3 Efficiency comparison

Below, we make an efficiency comparison of our scheme and some previous CBE schemes [3,6-9,11] in terms of the encryption cost and the decryption cost.

We mainly consider six cryptographic operations: pairing, exponentiation in the bilinear target group G2, scalar multiplication in the bilinear group G1, scalar multiplication in the elliptic curve group G, map-to-point hash and general hash. Here (G1, G2) are the bilinear groups in the setting of bilinear pairing, i.e., the bilinear pairing is e: G1 × G1 → G2. For simplicity, we denote these operations by P, E, M1, M, HM and H respectively. Note that if G1 is a multiplicative group, the scalar multiplication in G1 is then called exponentiation correspondingly. The details of the compared CBE schemes are listed in Table 1. Note that we do not list all known CBE schemes in the literature but some secure and representative ones.

Table 1.Computation efficiency of the compared CBE schemes

To give a more intuitive comparison, we simulate these CBE schemes using the standard cryptographic library MIRACAL [25] under the 1024-bit RSA security level. The experimental platform is a PIV 3-GHZ processor with 512-MB memory and a Windows XP operation system. For the pairing-based CBE schemes [3,6-9,11], to achieve the 1024-bit RSA security level, we use the fastest Tate pairing defined over the supersingular elliptic curve E(Fp): y2 = x3 + x with embedding degree 2, where p is a 512-bit Solinas prime. For our scheme, to achieve the same security level, we use the security parameter secp160r1 recommended by the Standards for Efficient Cryptography Group (SECG) [26], where p = 2160 - 231 -1, a = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF 7FFFFFFC and b = 1C97BEFC 54BD7A8B 65ACF89F 81D4D4AD C565FA45. The simulation results are given in Table 2.

Table 2.Running time of the compared CBE schemes

As shown in Table 2, the running time of the encryption algorithm of our scheme is 6.63ms which is about 10.5% of [3], 11.4% of [6], 28.4% of [7], 16.11% of [8], 17.8% of [9] and 21.5% of [11], while the running time of the decryption algorithm of our scheme is 4.42ms which is about 16.7% of [3], 7.7% of [6], 13.9% of [7], 7.2% of [8], 3.7% of [9] and 7.5% of [11]. Therefore, it is more efficient than the previous pairing-based CBE schemes.

 

5. Conclusion

In this paper, we show that the CBE scheme without bilinear pairings proposed by Yao et al. [19] fails in achieving either the IND-CCA2 security or the weaker IND-CPA security. We propose an enhanced CBE scheme without relying on the bilinear pairings and formally prove that it satisfies the IND-CCA2 security under the CDH assumption in the random oracle model. Compared with the previous CBE schemes, our scheme enjoys obvious advantage in the computation efficiency. Due to avoiding the computationally-heavy pairing operations, it is suitable for the computation-limited or power-constrained devices.