Advanced
Efficient Certificate-Based Proxy Re-encryption Scheme forData Sharing in Public Clouds
Efficient Certificate-Based Proxy Re-encryption Scheme forData Sharing in Public Clouds
KSII Transactions on Internet and Information Systems (TIIS). 2015. Jul, 9(7): 2703-2718
Copyright © 2015, Korean Society For Internet Information
  • Received : February 04, 2015
  • Accepted : June 08, 2015
  • Published : July 31, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Yang Lu

Abstract
Nowadays, public cloud storage is gaining popularity and a growing number of users are beginning to use the public cloud storage for online data storing and sharing. However, how the encrypted data stored in public clouds can be effectively shared becomes a new challenge. Proxy re-encryption is a public-key primitive that can delegate the decryption right from one user to another. In a proxy re-encryption system, a semi-trusted proxy authorized by a data owner is allowed to transform an encrypted data under the data owner’s public key into a re-encrypted data under an authorized recipient’s public key without seeing the underlying plaintext. Hence, the paradigm of proxy re-encryption provides a promising solution to effectively share encrypted data. In this paper, we propose a new certificate-based proxy re-encryption scheme for encrypted data sharing in public clouds. In the random oracle model, we formally prove that the proposed scheme achieves chosen-ciphertext security. The simulation results show that it is more efficient than the previous certificate-based proxy re-encryption schemes.
Keywords
1. Introduction
C loud computing has increasingly become a technology trend due to its key properties, such as cost saving and on-demand provisioning. There is an emerging trend that increasingly more users are beginning to use the public cloud storage for online data storing and sharing. However, many users still hesitate to move their data into a cloud, since they worry about their sensitive information being leaked by a cloud service provider (CSP). To preserve the confidentiality of the data stored at a cloud storage server, one can encrypt the data before sending it to the server. However, traditional encryption paradigm makes it difficult for flexibly sharing encrypted data between different users. For data sharing, there are two ways for a data owner to choose under the traditional encryption paradigm: he encrypts all data with a single symmetric key and gives his friends the symmetric key directly; or he downloads the encrypted data from the cloud storage, decrypts them, re-encrypts them using a new symmetric key and re-uploads the re-encrypted data along with the new symmetric key encrypted under his friend’s public key to cloud. Obviously, the first way violates the least privilege principle since all data are leaked to his friends. For the second way, there are practical concerns on efficiency. Because the data owner has to re-encrypt the data and then re-upload to cloud, it brings heavy computation load and bandwidth cost to the data owner. In addition, the second way also loses the value of cloud storage.
How the encrypted data can be effectively shared in clouds has become a challenge. So far, a variety of methods ( e.g. [1 - 10] ) have been introduced in an attempt to deal with this problem. Among these approaches, proxy re-encryption (PRE) provides a promising solution for encrypted-data sharing in public clouds. The notion of PRE was introduced by Blaze et al. [11] in Eurocrypt’98. Its goal is to securely delegate the decryption right from one user (the delegator ) to another (the delegate ) without relying on trusted third parties. In a PRE scheme, a semi-trusted proxy authorized by the delegator is allowed to transform a ciphertext under the delegator’s public key into a new ciphertext under the delegate’s public key without seeing the underlying plaintext. More concretely, this cryptographic system works as follows: The delegator generates a proxy re-encryption key and sets it in a proxy. On receiving the ciphertexts under the delegator’s public key, the proxy transforms them into the ciphertexts under the delegate’s public key using the re-encryption key. Then, the delegate can decrypt the re-encrypted ciphertexts by using its private key directly. PRE can serve as a fundamental cryptographic building block for constructing secure data sharing applications in cloud systems. With a PRE system, a data owner is able to delegate the access rights of the sharing data to others so that they can access these data from the cloud storage directly. Furthermore, PRE introduces minor overhead on cloud users by eliminating any direct interaction between a data owner and its recipients.
Since its advent, PRE has attracted much attention in the research community and a number of schemes have been proposed. However, most of previous PRE schemes were constructed under either traditional public-key encryption (PKE) ( e.g. [12 - 16] ) or identity-based encryption (IBE) ( e.g. [17 - 20] ). It is well recognized that traditional PKE suffers from the cumbersome certificate management problem and IBE has inherent key escrow and distribution problems. To solve the key escrow problem in identity-based PRE, Xu et al. [3] proposed the notion of certificateless PRE by extending PRE into certificateless public-key cryptography (CL-PKC) that was presented by Al-Riyami and Paterson in Asiacrypt’03 [21] . However, CL-PKC needs a secure communication channel to distribute a partial private key to each user. Therefore, certificateless PRE inevitably suffers from the key distribution problem similar to identity-based PRE. This feature limits the application of certificateless PRE in public clouds.
To address the problems imposed on the previous approaches, Sur et al. [4] introduced the notion of certificate-based PRE (CB-PRE) that follows the idea of certificate-based encryption (CBE) presented by Gentry [22] in Eurocrypt’03. CBE is a public-key encryption primitive that has attracted great interest in the recent years [23 - 30] . This primitive combines traditional PKE with IBE while preserving some of their most attractive features. As in traditional PKE, each user in CBE generates a pair of public key and private key independently and then requests a certificate from a CA. The difference is that a certificate is pushed only to its owner and acts as a partial decryption key. This additional functionality provides an efficient implicit certificate mechanism so that a user needs both his private key and certificate to perform decryption operations, while the other parties need not obtain the fresh information on this user’s certificate status. The feature of implicit certificate makes CBE eliminate third-party queries for the certificate status and simplify the public key revocation problem in traditional PKE. Furthermore, there are no key escrow problem (since CA does not know users’ private keys) and key distribution problem (since the certificates can be sent to their owners publicly) in CBE. To the best of our knowledge, two CB-PRE schemes have been proposed in the literature so far. In [4] , Sur et al. provided a formal security model for CB-PRE schemes and proposed the first CB-PRE scheme that is provably secure in the random oracle model [31] . In [32] , Li et al. proposed another CB-PRE scheme in the random oracle model. However, both of these two CB-PRE schemes are inefficient due to many costly pairing operations. For example, to re-encrypt a ciphertext, Sur et al. ’s scheme [4] requires computing seven pairings while Li et al. ’s scheme [32] requires computing five pairings.
The contribution of this paper is that we develop an efficient CB-PRE scheme with bilinear pairings. The proposed scheme requires computing at most two bilinear pairings in each operation. Compared with the previous CB-PRE schemes, it has obviously advantage in both the computation efficiency and the communication bandwidth. In the random oracle model, we strictly prove that the proposed scheme is chosen-ciphertext secure under the hardness of the bilinear Diffie-Hellman problem.
2. Preliminaries
- 2.1 Bilinear Map and Complexity Assumption
Let k be a security parameter and p be a k -bit prime number. Let G and GT be two cyclic groups of prime order p and P be a generator of the group G .
A bilinear pairing is a map e : G × G GT that takes two elements U and V in the group G as input and outputs an element e ( U , V ) in the group GT . It satisfies the following three properties:
(1) Bilinearity: For all U , V G and all a , b
PPT Slide
Lager Image
, e ( Ua , Vb ) = e ( U , V ) ab ;
(2) Non-degeneracy: e ( P , P ) ≠ 1;
(3) Computability: For all U , V G , e ( U , V ) can be efficiently computed.
The security of our CB-PRE scheme is based on the following complexity assumption.
Definition 1 [33] . The bilinear Diffie-Hellman (BDH) problem in ( G , GT ) is, given a tuple ( P , aP , bP , cP ) ∈ G 4 for unknown a , b , c
PPT Slide
Lager Image
, to compute e ( P , P ) abc GT . The advantage of a probabilistic polynomial time (PPT) algorithm ABDH in solving the BDH problem in ( G , GT ) is defined as
PPT Slide
Lager Image
The BDH assumption is that, for any PPT algorithm ABDH , the advantage Adv ( ABDH ) is negligible.
- 2.2 Certificate-Based Proxy Re-Encryption
In this paper, a CB-PRE scheme is composed of eight algorithms: (1) System setup algorithm Setup , which is performed by a CA to generate a master secret key and a list of public system parameters; (2) User key generation algorithm UserKeyGen , which is performed by the users to generate their private key and public key pairs; (3) Certificate generation 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 delegators to encrypt their data to generate the original ciphertexts; (5) Re-encryption key generation algorithm ReKeyGen , which is performed by the delegators to generate the re-encryption keys; (6) Re-encryption algorithm ReEncrypt , which is performed by a proxy to re-encrypt the original ciphertexts; (7) Normal decryption algorithm Decrypt1 , which is performed by the delegators to decrypt the original ciphertexts; (8) Re-encrypted ciphertext decryption algorithm Decrypt2 , which is performed by the delegates to decrypt the re-encrypted ciphertexts.
A more concrete functional description of a CB-PRE scheme is as follows:
PPT Slide
Lager Image
In the above algorithms UserKeyGen and Certify , a user U may be a delegator A or a delegate B .
For correctness, it is required that, for any message M and any identity idA and idB , the following two equations should hold: Decrypt1 ( params , Encrypt ( params , M , idA , PKA ), SKA , CertA ) = M , Decrypt2 ( params , ReEncrypt ( params , Encrypt ( params , M , idA , PKA ), RK AB ), idB , SKB , CertB , idA , PKA ) = M .
As introduced by Sur et al. in [4] , the security model of CB-PRE schemes is an extension of the model of CBE schemes in which there are two kinds of adversaries, namely Type-I adversary (denoted by AI ) and Type-II adversary (denoted by AII ). The Type-I adversary models an uncertified entity while the Type-II adversary models a malicious CA who knows the master secret key. To formalize the security notions for CB-PRE schemes, we first describe the following six oracles. A Type-I or Type-II adversary can adaptively make requests to some of these oracles. We assume that the challenger keeps a history of “query-answer” when interacting with the adversary.
(1) OUserCreate(idU): On input an identity idU, the challenger responds with the public key PKU associated with the identity idU. If the identity idU has not been created, then the challenger generates a public key PKU and a private key SKU respectively and returns PKU. In this case, the identity idU is said to be created. Note that other oracles defined below only respond to an identity which has been created.
(2) OCorrupt(idU): On input an identity idU, the challenger outputs the private key SKU associated with the identity idU.
(3) OCertificate(idU): On input an identity idU, the challenger responds with a certificate CertU. Note that such an oracle is only queried by the Type-I adversary since the Type-II adversary can generate any user’s certificate by itself.
(4) OReKeyGen ( idA , idB ): On input two identities idA and idB , the challenger responds with a re-encryption key RK AB .
(5) OReEncrypt ( idA , idB , CA ): On input two identities idA , idB and a ciphertext CA under the identity idA and the public key PKA , the challenger responds with a transformed ciphertext CB under the identity idB and the public key PKB .
(6) ODecrypt ( idU , CU ): On input an identity idU and a ciphertext CU , the challenger responds with the decryption of the ciphertext CU .
The chosen-ciphertext security of CB-PRE schemes can be formally defined by the following adversarial game “ IND-CBPRE-CCA2 Game ”, in which a Type-I or Type-II adversary AX ∈ { AI , AII } interacts with a challenger.
Setup. On input a security parameter k , the challenger runs the algorithm Setup ( k ) to generate a master secret key msk and a list of public parameters params . It then sends params to the adversary AX . If AX is a Type-II adversary, the challenger also sends the master secret key msk to it.
Phase 1. In this phase, the adversary AX can adaptively query the oracles OCreateUser , OCorrupt , OCertificate , OReKeyGen , OReEncrypt and ODecrypt if it is a Type-I adversary or the oracles OCreateUser , OPrivateKey , OReKeyGen , OReEncrypt and ODecrypt if it is a Type-II adversary. The challenger responds as described above.
Challenge. Once the adversary AX decides that Phase 1 is over, it outputs an identity idch and two equal-length messages ( M 0 , M 1 ) on which it wants to be challenged. The challenger picks a random bit b ∈{0,1}, computes Cch = Encrypt ( params , Mb , idch , PKch ), and then outputs Cch as the challenge ciphertext to the adversary AX .
Phase 2. In this phase, the adversary AX issues a second sequence of queries as in Phase 1.
Guess. After all queries, the adversary AX outputs a guess b′ ∈{0,1} for the bit b . We say that the adversary AX wins the game if b = b′ and the following restrictions are simultaneously satisfied: (1) ( idch , Cch ) and its derivatives cannot be submitted to the oracle ODecrypt ; (2) idch cannot be submitted to the oracle OCertificate if AX is a Type-I adversary or the oracle OPrivateKey if AX is a Type-II adversary. The advantage of the adversary AX is defined to be
PPT Slide
Lager Image
For our definition to make sense, we consider the notion of derivative of the challenge ciphertext [13] .
Definition 2. Assume that idch is the challenge identity and Cch is the challenge ciphertext in the above games, ( idU , CU ) is said to be a derivative of ( idch , Cch ) if either (1) the adversary AX has queried the oracle OReEncrypt on ( idch , idU , Cch ) to get a new ciphertext CU , or (2) the adversary AX has queried the oracle OReKeyGen ( idch , idU ) to get the re-encryption key RK chU and CU is the result of ReEncrypt ( params , Cch , RK chU ).
It is clear that in the above game we should disallow the queries to ODecrypt not only on the challenge ciphertext ( idch , Cch ) as usual, but also on any derivative of ( idch , Cch ). Otherwise, the adversary AX can easily win the game by making a query to OReEncrypt or OReKeyGen corresponding to ( idch , Cch ).
Definition 3. A CB-PRE scheme is said to be secure against adaptive chosen-ciphertext attacks (or IND-CBPRE-CCA2 secure) if no PPT adversary has non-negligible advantage in the above game.
3. Description of the Proposed CB-PRE Scheme
Motivated by Green and Ateniese’s identity-based PRE scheme [17] , we propose a new CB-PRE scheme. The proposed scheme consists of the following eight algorithms:
(1) Setup ( k ). The CA chooses a k -bit prime number p , generates two cyclic groups G and GT of order p such that there exists a bilinear paring map e : G × G GT . It randomly chooses a generator P G and a master secret key s
PPT Slide
Lager Image
, and sets Ppub = Ps . Additionally, it selects five cryptographic hash functions H 1 : {0,1} * × G G , H 2 : {0,1} n × GT × {0,1} * × G
PPT Slide
Lager Image
, H 3 : {0,1} * × G × G G , H 4 : GT → {0,1} n and H 5 : {0,1} * × {0,1} * × GT × G G , where n is the bit-length of the message to be encrypted. The public system parameters are params = { p , G , GT , e , n , P , Ppub , H 1 , H 2 , H 3 , H 4 , H 5 } and the master secret key is msk = s .
(2) UserKeyGen (params). A user U with identity idU chooses a random value xU
PPT Slide
Lager Image
as his private key SKU and computes his public key PKU = PxU .
(3) Certify ( params , msk, idU , PKU ). The CA computes CertU =
PPT Slide
Lager Image
as a certificate for a user U with identity idU and public key PKU , where QU = H 1 ( idU , PKU ). The user U can check the validness of CertU by verifying whether e ( P , CertU ) = e ( Ppub , QU ).
(4) Encrypt ( params , M , idA , PKA ). To encrypt a message M ∈ {0,1} n , the delegator A randomly chooses σ GT , sets r = H 2 ( M , σ , idA , PKA ), and then computes an original ciphertext CA = ( UA , VA , WA ) = ( Pr , σ e ( Ppub , QA ) -r e ( PKA , RA ) -r , M H 4 ( σ )), where QA = H 1 ( idA , PKA ) and RA = H 3 ( idA , PKA , Ppub ).
The algorithm Encrypt does not require any paring computations once e ( Ppub , QA ) and e ( PKA , RA ) have been pre-computed.
(5) ReKeyGen ( params , idA , SKA , CertA , idB , PKB ). To generate a proxy re-encryption key RK AB , the delegator A computes K 1 = e ( CertA , QB ), K 2 =( PKB ) SKA and K 3 =( RA ) SKA CertA , and then sets RK AB = H 5 ( idA , idB , K 1 , K 2 ) ⋅ K 3 , where QB = H 1 ( idB , PKB ) and RA = H 3 ( idA , PKA , Ppub ).
(6) ReEncrypt ( params , C , RK AB ). To convert an original ciphertext CA = ( UA , VA , WA ) under identity idA and public key PKA into a re-encrypted ciphertext CB under identity idB and public key PKB using the proxy re-encryption key RK AB , the proxy sets UB = UA and WB = WA respectively, computes VB = VA e ( UA , RK AB ) and then sets CB = ( UB , VB , WB ).
(7) Decrypt1 ( params , CA , idA , SKA , CertA ). To decrypt an original ciphertext CA = ( UA , VA , WA ), the delegator A first computes σ′ = VA e ( UA , ( RA ) SKA CertA ) and M′ = WA H 4 ( σ′ ), where RA = H 3 ( idA , PKA , Ppub ). It then checks whether UA = Pr′ where r′ = H 2 ( M′ , σ′ , idA , PKA ). If this check holds, it outputs M′ , otherwise outputs ⊥.
(8) Decrypt2 ( params , CB , idB , SKB , CertB , idA , PKA ). To decrypt a re-encrypted ciphertext CB = ( UB , VB , WB ) from a delegator A with identity idA and public key PKA , the delegate B first computes σ′ = VB e ( UB , H 5 ( idA , idB , e ( QA , CertB ), ( PKA ) SKB ) -1 ) and M′ = WB H 4 ( σ′ ), where QA = H 1 ( idA , PKA ). It then checks whether UB = P r′ where r′ = H 2 ( M′ , σ′ , idA , PKA ). If this check holds, it outputs M′ , otherwise outputs ⊥.
4. Analysis of the Proposed CB-PRE Scheme
- 4.1 Correctness
The correctness of the proposed CB-PRE scheme can be verified as follows:
If CA is an original ciphertext, i.e. , CA = ( UA , VA , WA ), then we have
PPT Slide
Lager Image
If CB is a re-encrypted ciphertext from a delegator A with identity idA and public key PKA , i.e. , CB = ( UB , VB , WB ) = ( UA , VA e ( UA , RK AB ), WA ), then we have
PPT Slide
Lager Image
Hence, the normal decryption and the re-encrypted ciphertext decryption are both correct.
- 4.2 Security Proof
Theorem 1. In the random oracle model, our CB-PRE scheme is IND-CBPRE-CCA2 secure under the BDH assumption.
This theorem can be proved by combining the following Lemma 1 and Lemma 2 .
Lemma 1. Assume that a Type-I adversary AI has an advantage ε against our CB-PRE scheme when asking at most quc queries to the oracle OUserCreate , qcr queries to the oracle OCorrupt , qcer queries to the oracle OCertificate , qrk queries to the oracle OReKeyGen , qren queries to the oracle OReEncrypt , qdec queries to the oracle ODecrypt and qi queries to the random oracles Hi ( i = 1,2,3,4,5) respectively, then there exists an algorithm ABDH to solve the BDH problem with advantage
PPT Slide
Lager Image
Proof. We show how to construct an algorithm ABDH to solve the BDH problem. Assume that the algorithm ABDH is given a random instance ( P , Pa , Pb , Pc ) of the BDH problem in ( G , GT ) and asked to compute e ( P , P ) abc . In order to solve the given problem, ABDH needs to simulate a challenger and all oracles for the adversary AI .
In the setup phase, the algorithm ABDH sets Ppub = Pa and randomly chooses an index θ ∈ {1,2,…, q 1 }. Then, it starts IND-CBPRE-CCA2 Game by supplying the adversary AI with params = { p , G , GT , e , n , P , Ppub , H 1 , H 2 , H 3 , H 4 , H 5 }, where H 1 ~ H 5 are random oracles controlled by ABDH . Note that the master key msk is the value a that is unknown to ABDH .
Now, the algorithm ABDH starts to respond various queries as follows:
H1 queries : We assume that the adversary AI ’s queries to the random oracle H 1 are distinct. The algorithm ABDH maintains a list H 1 List of tuples ( idi , PKi , Qi , Certi ). On receiving such a query on ( idi , PKi ), it does the following: (1) If idi already appears on the list H 1 List in a tuple ( idi , PKi , Qi , Certi ), then it outputs Qi to the adversary AI . (2) Else if the query is on the θ -th distinct identity idθ , it sets h 1i = Pb , inserts a new tuple ( idi , PKi , Qi , ⊥) into the list H 1 List and then returns Qi . (3) Otherwise, it randomly choose si
PPT Slide
Lager Image
, sets Qi = Psi and Certi = ( Pa ) si , inserts a new tuple ( idi , PKi , Qi , Certi ) into the list H 1 List and then returns Qi .
H2 queries : The algorithm ABDH maintains a list H 2 List of tuples ( M , σ , idi , PKi , r ). On receiving such a query on ( M , σ , idi , PKi ), it checks whether ( M , σ , idi , PKi ) already appears on the list H 2 List in a tuple ( M , σ , idi , PKi , r ). If so, it outputs r . Otherwise, it outputs a random value r
PPT Slide
Lager Image
to AI and inserts a new tuple ( M , σ , idi , PKi , r ) into the list H 2 List .
H3 queries : The algorithm ABDH maintains a list H 3 List of tuples ( idi , PKi , ti , Ri ). On receiving such a query on ( idi , PKi , Ppub ), it checks whether ( idi , PKi ) already appears on the list H 3 List in a tuple ( idi , PKi , ti , Ri ). If so, it returns Ri to AI directly. Otherwise, it randomly chooses ti
PPT Slide
Lager Image
, sets Ri = Pti , inserts a new tuple ( idi , PKi , ti , Ri ) into H 3 List and returns Ri to AI .
H4 queries : The algorithm ABDH maintains a list H 4 List of tuples ( σ , h 4 ). On receiving such a query on σ , it checks whether σ already appears on the list H 4 List in a tuple ( σ , h 4 ). If so, it returns h 4 to AI directly. Otherwise, it returns a random value h 4 ∈ {0, 1} n and inserts a new tuple ( σ , h 4 ) into the list H 4 List .
H5 queries : The algorithm ABDH maintains a list H 5 List of tuples ( idi , idj , K 1 , K 2 , h 5ij ). On receiving such a query on ( idi , idj , K 1 , K 2 ), it checks whether ( idi , idj , K 1 , K 2 ) already appears on the list H 5 List in a tuple ( idi , idj , K 1 , K 2 , h 5ij ). If so, it returns h 5ij to AI directly. Otherwise, it returns a random value h 5ij G and inserts a new tuple ( idi , idj , K 1 , K 2 , h 5ij ) into the list H 5 List .
OUserCreate queries : The algorithm ABDH maintains a list KeyList of tuples ( idi , PKi , SKi ). On receiving such a query on id i , it checks whether the identity idi already appears on the list KeyList in a tuple ( idi , PKi , SKi ). If so, it returns PKi to AI directly. Otherwise, it randomly chooses xi
PPT Slide
Lager Image
as SKi , computes PKi = Pxi , inserts a new tuple ( idi , PKi , SKi ) into the list KeyList and then returns PKi .
OCorrupt queries : On receiving such a query on idi , ABDH searches idi in the list KeyList to find a tuple ( idi , PKi , SKi ) and returns SKi to AI .
OCertificate queries : On receiving such a query on idi , ABDH aborts if idi = idθ . Otherwise, it searches idi in the list H 1 List to find a tuple ( idi , PKi , Qi , Certi ) and returns Certi to AI .
OReKeyGen queries : On receiving such a query on ( idi , idj ), ABDH aborts if idi = idθ . Otherwise, it respectively retrieves the private key SKi and certificate Certi associated with the identity idi and the public key PKj associated with the identity idj , then computes ReKeyGen ( params , idi , SKi , Certi , idj , PKj ) and outputs the result to AI .
OReEncrypt queries : On receiving such a query on ( idi , idj , Ci = ( Ui , Vi , Wi )), ABDH does the following: (1) If idi = idθ , it searches in the list H 2 List for a tuple ( M , σ , idi , PKi , r ) such that Ui = Pr , Vi = σ e ( Ppub , H 1 ( idi , PKi )) r e ( PKi , H 3 ( idi , PKi , Ppub )) r and Wi = M H 4 ( σ ). The query is rejected if no such tuple is found. Otherwise, it sets Vj = σ e ( Ui , H 5 ( idi , idj , e ( H 1 ( idi , PKi ), Certj ),( PKi ) SKj )) and returns Cj = ( idi , Ui , Vj , Wi ) as the re-encryption ciphertext to AI . (2) Otherwise, it makes a query OReKeyGen ( idi , idj ) to obtain a re-encryption key RK ij and then returns the result of ReEncrypt ( params , Ci , RK ij ) to AI . Note that a valid ciphertext submitted to this oracle is rejected with probability smaller than qren /2 k across the whole game.
ODecrypt queries : On receiving such a query on ( idi , Ci ), ABDH does the following: (1) If idi = idθ and Ci = ( Ui , Vi , Wi ) is an original ciphertext, it searches in the list H 2 List for a tuple ( M , σ , idi , PKi , r ) such that Ui = rP , Vi = σ e ( Ppub , H 1 ( idi , PKi )) r e ( PKi , H 3 ( idi , PKi , Ppub )) r and Wi = M H 4 ( σ ). If no such tuple is found, it rejects this query. Otherwise, it returns M in this tuple to AI . (2) Else if idi = idθ and Ci = ( idj , Uj , Vi , Wj ) is a transformed ciphertext, it queries the oracle OReKeyGen on ( idj , idi ) to obtain a re-encryption key RK ji and computes Vj = Vi / RK ji . It then searches in the list H 2 List for a tuple ( M , σ , idj , PKj , r ) such that Uj = rP , Vj = σ e ( Ppub , H 1 ( idj , PKj )) r e ( PKj , H 3 ( idj , PKj , Ppub )) r and Wj = M H 4 ( σ ). If no such tuple is found, B rejects this query. Otherwise, it returns M in this tuple to AI . (3) Otherwise, it obtains SKi and Certi associated with the identity idi and then returns the result of Decrypt ( params , Ci , SKi , Certi ). Note that a valid ciphertext submitted to this oracle is rejected with probability smaller than qdec /2 k .
In the challenge phase, AI outputs ( M 0 , M 1 , idch ) on which it wants to be challenged. If idch idθ , then ABDH aborts. Otherwise, it sets Uch = cP , randomly chooses Vch GT , Wch ∈ {0, 1} n , and returns Cch = ( Uch , Vch , Wch ) as the challenge ciphertext to AI .
In the guess phase, AI outputs a bit b′ which is ignored by ABDH . Observe that the decryption of Cch is Wch H 4 ( Vch / e ( Uch , Certch + SKchRch )) where Rch = H 3 ( idch , PKch , Ppub ).
To produce a result, ABDH randomly picks a tuple ( σ , h 4 ) from the list H 4 List , retrieves the value tch from the tuple ( idch , PKch , tch , Rch ) in the list H 3 List and returns
PPT Slide
Lager Image
as the solution to the given BDH problem.
Note that if σ = Vch / e ( Uch , Certch + SKchRch ), then Vch = σ e ( Ppub , Qch ) c e ( PKch , Rch ) c , where Qch = H 1 ( idch , PKch ). Thus, we have
PPT Slide
Lager Image
We now estimate ABDH ’s advantage in solving the BDH problem.
Let Fail denote the event that the above simulation fails and QueryH4 the event that AI makes a query H 4 ( Vch / e ( Uch , Certch + SKchRch ). From the above simulation, the event Fail occurs if any one of the following five events occurs: (1) E1 : In the challenge phase, AI does not choose idθ as the challenge identity; (2) E2 : AI queries the oracle OCertificate on idθ ; (3) E3 : AI queries the oracle OReKeyGen on ( idθ , idj ); (4) E4 : ABDH rejects a valid ciphertext submitted to the oracle OReEncrypt ; (5) E5 : ABDH rejects a valid ciphertext submitted to the oracle ODecrypt .
We clearly have that Pr[¬ E1 ] = 1/ q 1 and ¬ E1 implies ¬ E2 and ¬ E3 . We also already observed that Pr[ E4 ] ≤ qren /2 k and Pr[ E5 ] ≤ qdec /2 k . Thus, the probability that the above simulation does not fail is
PPT Slide
Lager Image
Let Event be the event QueryH4 | ¬ Fail . It is clear that if Event does not happen, then AI does not gain any advantage greater than 1/2 in guessing b . Namely, we have the probability Pr[ b = b ′|¬ Event ] = 1/2. Hence, by splitting the probability Pr[ b = b ′], we obtain Pr[ b = b ′]= Pr[ b = b ′|¬ Event ]⋅Pr[¬ Event ] + Pr[ b = b ′| Event ]⋅Pr[ Event ] ≤ Pr[¬ Event ]/2 + Pr[ Event ] = 1/2 + Pr[ Event ]/2. By the definition of the advantage in IND-CBPRE-CCA2 Game , we have ε ≤ 2|Pr[ b = b ′] - 1/2| ≤ Pr[ Event ] ≤ Pr[ QueryH4 ]/Pr[¬ Fail ]. Hence, we get
PPT Slide
Lager Image
Finally, we get the announced bound on ABDH ’s advantage in solving the BDH problem by noting that ABDH selects the correct tuple from the list H 4 List with probability 1/ q 4 .
Lemma 2. Assume that a Type-II adversary AII has an advantage ε against our CB-PRE scheme when asking at most quc queries to the oracle OUserCreate , qcr queries to the oracle OCorrupt , qrk queries to the oracle OReKeyGen , qren queries to the oracle OReEncrypt , qdec queries to the oracle ODecrypt and qi queries to the random oracles Hi ( i = 1,2,3,4,5) respectively, then there exists an algorithm ABDH to solve the BDH problem with advantage
PPT Slide
Lager Image
Proof. We show how to construct an algorithm ABDH to solve the BDH problem. Assume that ABDH is given a random instance ( P , aP , bP , cP ) of the BDH problem in ( G , GT ) and asked to compute e ( P , P ) abc . In order to solve the given problem, ABDH needs to simulate a challenger and all oracles for the adversary AII .
In the setup phase, ABDH randomly chooses α
PPT Slide
Lager Image
and sets Ppub = αP . Furthermore, it randomly chooses an index θ ∈ {1,2,…, quc }. Then, it starts IND-CBPRE-CCA2 Game by supplying AII with msk = α and params = { p , G , GT , e , n , P , Ppub , H 1 , H 2 , H 3 , H 4 , H 5 }, where H 1 ~ H 5 are random oracles controlled by ABDH .
During the query-answer phase, ABDH responds AII ’s queries to the oracles H 2 , H 4 , H 5 , OReKeyGen , OReEncrypt and ODecrypt as in the proof of Lemma 1 and other queries as follows:
H1 queries : ABDH maintains a list H 1 List of tuples ( idi , PKi , Qi ). On receiving such a query on ( idi , PKi ), ABDH checks whether ( idi , PKi ) already appears on the list H 1 List in a tuple ( idi , PKi , Qi ). If so, then it returns Qi to AII . Otherwise, it returns a random value Qi
PPT Slide
Lager Image
to AII and inserts a new tuple ( idi , PKi , Qi ) into the list H 1 List .
H3 queries : ABDH maintains a list H 3 List of tuples ( idi , PKi , Ri ). On receiving such a query on ( idi , PKi , Ppub ), ABDH does the following: (1) If ( idi , PKi ) already appears on H 3 List in a tuple ( idi , PKi , Ri ), it returns Ri to AII directly. (2) Else if idi = idθ , it returns Ri = bP to AII and inserts a new tuple ( idi , PKi , Ri ) into the list H 3 List . (3) Otherwise, it returns a random element Ri G to AII and inserts a new tuple ( idi , PKi , Ri ) into the list H 3 List .
OUserCreate queries : ABDH maintains a list KeyList of tuples ( idi , PKi , SKi ). On receiving such a query on idi , ABDH does the following: (1) If idi already appears on KeyList in a tuple ( idi , PKi , SKi ), it returns PKi to AII directly. (2) Else if the query is on the θ -th distinct identity idθ , it returns PKθ = bP to AII and inserts ( idθ , PKθ , ⊥) into the list KeyList . Note that the private key corresponding to PKθ is SKθ = b which is unknown to ABDH . (3) Otherwise, it randomly chooses xi
PPT Slide
Lager Image
as SKi , computes PKi = xiP , inserts a new tuple ( idi , PKi , SKi ) into the list KeyList and then returns PKi to AII .
In the challenge phase, AII outputs ( M 0 , M 1 , idch ) on which it wants to be challenged. If idch idθ , then ABDH aborts. Otherwise, it sets Uch = cP , randomly chooses Vch GT , Wch ∈ {0, 1} n , and returns Cch = ( Uch , Vch , Wch ) as the challenge ciphertext to AII .
In the guess phase, AII outputs a bit b′ which is ignored by ABDH . Observe that the decryption of Cch is Wch H 4 ( Vch / e ( Uch , Certch + SKchRch )) where Rch = H 3 ( idch , PKch , Ppub ). To produce a result, ABDH randomly picks a tuple ( σ , h 4 ) from the list H 4 List and returns
PPT Slide
Lager Image
as the solution to the given BDH problem, where Qch = H 1 ( idch , PKch ).
Note that if σ = Vch / e ( Uch , Certch + SKchRch ), then Vch = σ e ( Ppub , Qch ) c e ( PKch , Rch ) c . Thus, we have
PPT Slide
Lager Image
We now estimate ABDH ’s advantage in solving the BDH problem.
Let Fail denote the event that the above simulation fails and QueryH4 the event that AII makes a query H 4 ( Vch / e ( Uch , Certch + SKchRch ). From the above simulation, the event Fail occurs if any one of the following events occurs: (1) E1 : In the challenge phase, AII does not choose idθ as the challenge identity; (2) E2 : AII queries the oracle OCorrupt on idθ ; (3) E3 : AII queries the oracle OReKeyGen on ( idθ , idj ); (4) E4 : ABDH rejects a valid ciphertext submitted to the oracle OReEncrypt ; (5) E5 : ABDH rejects a valid ciphertext submitted to the oracle ODecrypt .
We clearly have that Pr[¬ E1 ] = 1/ quc and ¬ E1 implies ¬ E2 and ¬ E3 . As in the proof of Lemma 1, we have Pr[ E4 ] ≤ qren /2 k and Pr[ E5 ] ≤ qdec /2 k . Thus, the probability that the above simulation does not fail is
PPT Slide
Lager Image
Let Event be the event QueryH4 | ¬ Fail . It is clear that if Event does not happen, then AII does not gain any advantage greater than 1/2 in guessing b . Namely, we have the probability Pr[ b = b ′|¬ Event ] = 1/2. Hence, by splitting the probability Pr[ b = b ′], we obtain Pr[ b = b ′]= Pr[ b = b ′|¬ Event ]⋅Pr[¬ Event ] + Pr[ b = b ′| Event ]⋅Pr[ Event ] ≤ Pr[¬ Event ]/2 + Pr[ Event ] = 1/2 + Pr[ Event ]/2. By the definition of the advantage in IND-CBPRE-CCA2 Game , we have ε ≤ 2|Pr[ b = b ′] - 1/2| ≤ Pr[ Event ] ≤ Pr[ QueryH4 ]/Pr[¬ Fail ]. Hence, we get
PPT Slide
Lager Image
Finally, we get the announced bound on ABDH ’s advantage in solving the BDH problem by noting that ABDH selects the correct tuple from the list H 4 List with probability 1/ q 4 .
- 4.3 Performance Comparison
To evaluate the performance of the proposed scheme, we provide a comparison of it and the previous two CB-PRE schemes [4 , 32] . Without considering pre-computation, the details of the compared schemes are listed in Table 1 . We denote pairing, exponentiation in GT , exponentiation in G , map-to-point hash and general hash by P , ET , E , HM and H respectively, the bit length of an element in G , an element in GT and a message by | G |, | GT | and n respectively. In Sur et al. ’s scheme [4] , k 0 denotes the bit-length of the random values used to encrypt the data, which should be at least 160 in order to obtain a reasonable security.
Performance of the CB-PRE schemes
PPT Slide
Lager Image
Performance of the CB-PRE schemes
To give a more intuitive comparison, we implement these CB-PRE schemes using the standard cryptographic library MIRACAL [34] . Our experimental platform is a PIV 3-GHZ processor with 512-MB memory and a Windows XP operation system. To achieve the 1024-bit (2048-bit) RSA level security, the Tate pairing defined over the super-singular elliptic curve E / Fp : y 2 = x 3 + x with embedding degree 2 is used, where p is a 512-bit (1024-bit) prime. The simulation results are given in Table 2 and Table 3 .
Simulation results of the CB-PRE schemes (1024-bit security level)
PPT Slide
Lager Image
Simulation results of the CB-PRE schemes (1024-bit security level)
Simulation results of the CB-PRE schemes (2048-bit security level)
PPT Slide
Lager Image
Simulation results of the CB-PRE schemes (2048-bit security level)
The above comparison shows that our scheme is more efficient than the previous two CB-PRE schemes in both the computation cost and the communication cost. Actually, the computation performance of our scheme can be further optimized. If the pairings e ( Ppub , QA ) and e ( PKA , RA ) are pre-computed, then the algorithm Encrypt of our scheme requires computing only two exponentiations in GT , one exponentiation in G and two general hashes to encrypt a message.
5. Conclusion
In this paper, we develop an efficient CB-PRE scheme from pairings and prove it to achieve chosen-ciphertext security in the random oracle model. Compared with the previous CB-PRE schemes, the proposed scheme enjoys obvious advantage in both the computation efficiency and the communication bandwidth. However, as pairing operation is extremely disliked by the power-constrained devices, it would be interesting to construct CB-PRE schemes that do not depend on parings. In addition, the security of our scheme can only be achieved in the random oracle model. So, another interesting problem is to construct secure CB-PRE schemes in the standard model.
BIO
Yang Lu received the Ph.D. degree from PLA University of Science and Technology in 2009. He has been working in HoHai University from 2003. Currently, he is an Assistant Professor in College of Computer and Information Engineering. His major research interests include information security and cryptography, network security and cloud security, etc. He has published more than 30 scientific papers in international conferences and journals.
References
Do J.M. , Song Y.J. , Park N. “Attribute based proxy re-encryption for data confidentiality in cloud computing environments,” in Proc. of 2011 First ACIS/JNU International Conference on Computers, Networks, Systems and Industrial Engineering 2011 248 - 251
Wang G. , Liu Q. , Wu J. 2011 “Achieving fine-grained access control for secure data sharing on cloud servers,” Concurrency and Computation: Practice and Experience 23 (12) 1443 - 1464    DOI : 10.1002/cpe.1698
Xu L. , Wu X. , Zhang X. “CL-PKE: a certificateless proxy re-encryption scheme for secure data sharing with public cloud,” in Proc. of the 7th ACM Symposium on Information, Computer and Communications Security 2012 87 - 88
Sur C. , Park Y. , Shin S.U. , Rhee K.H. , Seo C. “Certificate-based proxy re-encryption for public cloud storage,” in Proc. of the 7th International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing 2013 159 - 166
Lee S.H. , Lee I.Y. 2013 “A secure index management scheme for providing data sharing in cloud storage,” Journal of Information Processing Systems 9 (2) 287 - 300    DOI : 10.3745/JIPS.2013.9.2.287
Seo S.H. , Nabeel M. , Ding X. , Bertino E. 2013 “An efficient certificateless encryption for secure data sharing in public clouds,” IEEE Transactions on Knowledge and Data Engineering 26 (9) 2107 - 2119    DOI : 10.1109/TKDE.2013.138
Liang K. , Au M.H. , Liu J.K. , Susilo W. , Wong D.S. , Yang G. , Phuong T.V.X. , Xie Q. 2014 “A DFA-based functional proxy re-encryption scheme for secure public cloud data sharing,” IEEE Transactions on Information Forensics and Security 9 (10) 1667 - 1680    DOI : 10.1109/TIFS.2014.2346023
Liu Q. , Wang G. , Wu J. 2014 “Time-based proxy re-encryption scheme for secure data sharing in a cloud environment,” Information Sciences 258 355 - 370    DOI : 10.1016/j.ins.2012.09.034
Han N.D. , Han L. , Tuan D.M. , In H.P. , Jo M. 2014 “A scheme for data confidentiality in cloud-assisted wireless body area networks,” Information Sciences 284 157 - 166    DOI : 10.1016/j.ins.2014.03.126
Li J.W. , Li J. , Liu Z. , Jia C. 2014 “Enabling efficient and secure data sharing in cloud computing,” Concurrency and Computation: Practice and Experience 26 (5) 1052 - 1066    DOI : 10.1002/cpe.3067
Blaze M. , Bleumer G. , Strauss M. “Divertible protocols and atomic proxy cryptography,” in Proc. of Advances in Cryptology - Eurocrypt 1998 1998 127 - 144
Ateniese G. , Fu K. , Green M. , Hohenberger S. 2006 “Improved proxy re-encryption schemes with applications to secure distributed storage,” ACM Transactions on Information and System Security 9 (1) 1 - 30    DOI : 10.1145/1127345.1127346
Canetti R. , Hohenberger S. “Chosen-ciphertext secure proxy re-encryption,” in Proc. of the 14th ACM conference on Computer and Communications Security 2007 185 - 194
Deng R.H. , Weng J. , Liu S. , Chen K. “Chosen-ciphertext secure proxy re-encryption without pairings,” in Proc. of CANS 2008 2008 1 - 17
Libert B. , Vergnaud D. “Unidirectional chosen-ciphertext secure proxy re-encryption,” in Proc. of Public Key Cryptography - PKC 2008 2008 360 - 379
Shao J. , Cao Z. “CCA-secure proxy re-encryption without pairings,” in Proc. of Public Key Cryptography - PKC 2009 2009 357 - 376
Green M. , Ateniese G. “Identity-based proxy re-encryption,” in Proc. of ACNS 2007 2007 288 - 306
Chu C.K. , Tzeng W.G. “Identity-based proxy re-encryption without random oracles,” in Proc. of Information Security 2007 2007 189 - 202
Matsuo T. “Proxy re-encryption systems for identity-based encryption,” in Proc. of Pairing-Based Cryptography - Pairing 2007 2007 247 - 267
Luo S. , Shen Q. , Chen Z. “Fully secure unidirectional identity-based proxy re-encryption,” in Proc. of Information Security and Cryptology - ICISC 2011 2012 109 - 126
Al-Riyami S.S. , Paterson K.G. “Certificateless public key cryptography,” in Proc. of Advances in Cryptology - Asiacrypt 2003 2003 452 - 473
Gentry C. “Certificate-based encryption and the certificate revocation problem,” in Proc. of Advances in Cryptology - Eurocrypt 2003 2003 272 - 293
Sur C. , Jung C. D. , Rhee K. H. “Multi-receiver certificate-based encryption and application to public key broadcast encryption,” in Proc. of 2007 ECSIS Symposium on Bio-inspired, Learning, and Intelligent Systems for Security 2007 35 - 40
Galindo D. , Morillo P. , Ràfols C. 2008 “Improved certificate-based encryption in the standard model,” Journal of Systems and Software 81 (7) 1218 - 1226    DOI : 10.1016/j.jss.2007.09.009
Liu J. K. , Zhou J. “Efficient certificate-based encryption in the standard model,” in Proc. of 6th Int. Conf. on Security and Cryptography for Networks 2008 144 - 155
Lu Y. , Li J. , Xiao J. 2009 “Constructing efficient certificate-based encryption with paring,” Journal of Computers 4 (1) 19 - 26    DOI : 10.4304/jcp.4.1.19-26
Shao Z. 2011 “Enhanced certificate-based encryption from pairings,” Computers and Electrical Engineering 37 (2) 136 - 146    DOI : 10.1016/j.compeleceng.2011.01.007
Yao J. , Li J. , Zhang Y. 2013 “Certificate-based encryption scheme without pairing,” KSII Transactions on Internet and Information Systems 7 (6) 1480 - 1491    DOI : 10.3837/tiis.2013.06.008
Hyla T. , Maćków W. , Pejaś J. “Implicit and explicit certificates-based encryption scheme,” in Proc. of the 13th IFIP TC8 International Conference on Computer Information Systems and Industrial Management 2014 651 - 666
Lu Y. , Li J. 2014 “Efficient construction of certificate-based encryption secure against public key replacement attacks in the standard model,” Journal of Information Science and Engineering 30 (5) 1553 - 1568
Bellare M. , Rogaway P. “Random oracles are practical: a paradigm for designing efficient protocols,” in Proc. of 1st ACM Conf. on Communications and Computer Security 1993 62 - 73
Li J. , Zhao X. , Zhang Y. “Certificate-based conditional proxy re-encryption,” in Proc. of the 8th International Conference on Network and System Security 2014 299 - 310
Boneh D. , Franklin M. “Identity-based encryption from the Weil pairing,” in Proc. of Advances in Cryptology - Crypto 2001 2001 213 - 229
MIRACL, Multiprecision integer and rational arithmetic cryptographic library http://certivox.org/display/EXT/MIRACL