Next Article in Journal
ESPADE: An Efficient and Semantically Secure Shortest Path Discovery for Outsourced Location-Based Services
Previous Article in Journal
Side-Channel Evaluation Methodology on Software
Open AccessArticle

Privacy-Preserving and Efficient Public Key Encryption with Keyword Search Based on CP-ABE in Cloud

State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China
*
Author to whom correspondence should be addressed.
Received: 16 August 2020 / Revised: 2 October 2020 / Accepted: 8 October 2020 / Published: 13 October 2020

Abstract

In the area of searchable encryption, public key encryption with keyword search (PEKS) has been a critically important and promising technique which provides secure search over encrypted data in cloud computing. PEKS can protect user data privacy without affecting the usage of the data stored in the untrusted cloud server environment. However, most of the existing PEKS schemes concentrate on data users’ rich search functionalities, regardless of their search permission. Attribute-based encryption technology is a good method to solve the security issues, which provides fine-grained access control to the encrypted data. In this paper, we propose a privacy-preserving and efficient public key encryption with keyword search scheme by using the ciphertext-policy attribute-based encryption (CP-ABE) technique to support both fine-grained access control and keyword search over encrypted data simultaneously. We formalize the security definition, and prove that our scheme achieves selective indistinguishability security against an adaptive chosen keyword attack. Finally, we present the performance analysis in terms of theoretical analysis and experimental analysis, and demonstrate the efficiency of our scheme.
Keywords: cloud computing; public key encryption with keyword search; data privacy; access control; ciphertext-policy attribute-based encryption cloud computing; public key encryption with keyword search; data privacy; access control; ciphertext-policy attribute-based encryption

1. Introduction

With the rise and popularity of cloud computing technology, more and more data users are motivated to outsource their data to cloud for storage, and start to enjoy the various advantages brought by cloud computing, such as large storage capacity, flexible accessibility and vast computationality. By outsourcing data to the cloud, data users are relieved from the heavy burden of local storage and management costs. However, as the cloud server is not fully trusted and the outsourced data may contain sensitive information, sensitive data privacy and security in the cloud naturally become a primary concern for users. In order to address this issue, sensitive data should be encrypted before outsourcing to the cloud. Typical practical applications include cloud-based storage systems, such as electronic medical record systems where electronic health record data-sharing can help doctors to effectively assess patients’ conditions and make correct treatments. To prevent the leakage of patient information, we store the encrypted medical data on the cloud. Although encryption can ensure the confidentiality of data, it brings the inconvenience of data access and processing. For example, when doctors want to query the required medical data, the cloud server needs to perform search functions without knowing the content of the data. However, the conventional information retrieval methods based on plaintext can not directly be used on ciphertext. Therefore, how to search over encrypted data is of importance and becomes a new challenge.
Homomorphic encryption [1,2] can operate on encrypted data, it can be used to search the keyword over encrypted data theoretically. However, constructions based on homomorphic encryption needs large key sizes and brings huge communication costs. To better solve the keyword search problem over encrypted data, searchable encryption (SE) was proposed as an efficient solution. SE not only enables users to search queries over encrypted data stored on an untrusted server but also protects data privacy and search privacy. Compared with homomorphic encryption, SE is designed for keyword search, which is more efficient.
Song et al. [3] seminally proposed the notion of searchable encryption, which was the first concrete symmetric searchable encryption (SSE) construction. Subsequently, a number of efficient SSE schemes [4,5,6,7,8,9,10] have been proposed. However, data users have to securely share key for encryption in SSE schemes due to the property of symmetric cryptography. Therefore, most SSE schemes inevitably suffer from secret key distribution and management problems. Later, at Eurocrypt’04, Boneh et al. [11] first introduced the concept of public key searchable encryption based on the public key encryption algorithm, namely public key encryption with keyword search (PEKS). PEKS solved the secret key management and distribution yield by SSE, so PEKS has aroused great attention in research and has a broader application prospect.
PEKS is a critically important and promising technique, and this paper concentrates on PEKS. At present, various PEKS schemes have been proposed in the literature [12,13,14,15,16,17,18,19,20], and PEKS has been rapidly developed [21]. Most existing PEKS schemes focus on data users’ rich search functionalities, such as conjunctive keyword search [14] and multi-keyword search [20]. In the above schemes, all search users can be regarded as authorized users, who can have unrestricted access to the system. However, it is not suitable for practical requirements. For example, only the mail receiver is allowed to search on the encrypted emails in the cloud-based email system, while other users have no such permissions. To solve this problem, CP-ABE technology is widely adopted as a viable tool to achieve flexible data access control over encrypted data, which can gain one-to-many encryption instead of one-to-one.
Zheng et al. [22] constructed an attribute-based keyword search scheme on the basis of CP-ABE, however, computation and storage costs grow linearly with the number of system attributes. Yin et al. [23] improved the work of Zheng, but encryption and key generation operations also lead to much higher computational overheads. Thus, in this paper, we propose a new privacy-preserving and efficient public key encryption with keyword search scheme based on ciphertext-policy attribute-based encryption (PEKS-CPABE) to support both fine-grained access control and keyword search over encrypted data simultaneously. Specifically, the main contributions of this paper can be summarized as follows.
  • We propose an efficient and privacy-preserving PEKS-CPABE scheme, which enables the data owner to control the search and use of its outsourced encrypted data in the cloud according to its access control policy. Our scheme can achieve keyword search queries over encrypted data with fine-grained access control;
  • We formalize the security definition, and prove that our scheme achieves selective indistinguishability security against an adaptive chosen keyword attack and can also ensure keyword privacy;
  • We present the performance analysis in terms of theoretical analysis and experimental analysis, and demonstrate the efficiency of our scheme. Finally, the experimental results show that our PEKS-CPABE scheme performs better than the CP-ABKS scheme proposed in [22] and CP-ABSE scheme proposed in [23].
The remainder of this paper is organized as follows: Section 2 presents an overview of related work. Section 3 reviews some necessary and basic preliminary notions used in this paper. Section 4 defines the system model, algorithm description and security model of our proposed scheme. Section 5 introduces the concrete construction of our proposed scheme. Section 6 provides detailed security proof of our proposed scheme. Section 7 shows the performance analysis of our proposed scheme in terms of theoretical analysis and experimental analysis. Finally, Section 8 summarizes this paper.

2. Related Work

In 2004, Boneh et al. [11] devised the first public key searchable encryption scheme based on a standard public key encryption algorithm. In this scheme, multiple users are allowed to encrypt data using the public key, but only the private key holder can search the keyword over encrypted data. Inspired by Boneh et al. pioneering work, more and more researchers have been working on the public key searchable encryption to achieve various functionalities. Park et al. [13] first proposed a PEKS scheme to support conjunctive keyword search on encrypted data. Subsequently, Boneh and Waters [14] extended PEKS to support conjunctive, subset, and range queries on encrypted data. Later on, Lv et al. [18] proposed an expressive and secure PEKS scheme based on composite-order groups to support conjunctive, disjunctive and negation search operations that can be extended to support a range search. Huang and Li [19] proposed a public key authenticated encryption with keyword search scheme that can resist the inside keyword guessing attack, in which the data user can use the secret key to authenticate the data. Recently, Zhang et al. [20] constructed a novel PEKS scheme supporting semantic multi-keyword search by leveraging an efficient inner product encryption technology. These schemes guarantee that data users are able to efficiently perform search queries and prevent the untrusted cloud server from infringing data confidentiality and search privacy.
Attribute-based encryption (ABE), as a useful data encryption tool to address the problem of fine-grained data sharing and decentralized access control, was first proposed by Sahai and Waters [24]. This kind of new cryptographic technology enables users to achieve access control over encrypted data by using an access control policy associated with the private key or ciphertext. There are two types of attribute-based encryption, depending on whether the private key or ciphertext is associated with the access control policy, namely key-policy attribute-based encryption (KP-ABE) and ciphertext-policy attribute-based encryption (CP-ABE). Goyal et al. [25] proposed the first KP-ABE scheme, where the private key is associated with an access control policy and the ciphertext is associated with attributes. A user can decrypt a ciphertext only if the attributes that are used for encryption satisfy the access policy on the user private key. Bethencourt et al. [26] proposed the first CP-ABE scheme, where the ciphertext is associated with an access control policy and the key is associated with attributes. A user can decrypt a ciphertext only if the attributes on the user private key satisfy the access policy associated with the ciphertext. Compared with KP-ABE, CP-ABE is a preferred choice for designing an access control mechanism, because it is conceptually closer to traditional role-based access control.
Based on the special features of ABE, Zheng et al. [22] proposed a ciphertext-policy attribute-based keyword search (CP-ABKS) scheme, in which keywords are encrypted with an access control policy so that only data users with a legitimate credential can generate the trapdoor used to search over encrypted data. Dong et al. [27] introduced an enhanced attribute-based keyword search scheme via an online/offline approach. Their schemes mainly consider resource-constrained mobile devices, and allow data owners and data users to perform related operations online and offline. However, two encryption and decryption operations incur huge computational costs. Li et al. [28] proposed an attribute-based keyword search scheme with outsourcing key-issuing and outsourcing decryption, which is shown to be secure against chosen-plaintext attack, but it introduces three cloud storage providers and needs a number of expenses. Sun et al. [29] designed an authorized keyword search scheme with user revocation by utilizing CP-ABE technology, however, the computational costs in the trapdoor generation grow linearly with the number of system attributes. Qiu et al. [30] proposed a hidden policy attribute-based keyword search scheme to protect the privacy of the access control policy, which incurs abundant computational costs at the same time. Recently, Yin et al. [23] proposed a ciphertext-policy attribute-based searchable encryption scheme, and improved the scheme of Zheng et al. Inspired by both the work of Zheng and Yin, in this paper, we propose a new privacy-preserving and efficient public key encryption with a keyword search scheme based on ciphertext-policy attribute-based encryption (PEKS-CPABE) to support both fine-grained access control and keyword search over encrypted data simultaneously.

3. Preliminaries

In this section, we review some necessary and basic preliminary notions used in this paper.

3.1. Bilinear Map

Let G and G T be two multiplicative cyclic groups with the same prime order, p. g is a generator of G . Let e ^ : G × G G T be a computable bilinear map. The map e ^ has the following properties:
  • Bilinearity: Given a , b Z p and for all g G , there exists e ^ ( g a , g b ) = e ^ ( g , g ) a b ;
  • Non-degeneracy: e ^ ( g , g ) 1 ;
  • Computability: Given a , b Z p and for all g G , there is an efficient algorithm to compute e ^ ( g a , g b ) G T .

3.2. Decisional Bilinear Diffie-Hellman Assumption

Decisional Bilinear Diffie–Hellman (DBDH) Assumption is given as follows: Let G be a cyclic group with prime order p. g is a generator of G . e ^ : G × G G T is a bilinear map. We define the advantage as ϵ of a PPT adversary A to solve the DBDH problem as A d v A D B D H ( λ ) = | P r [ A ( g ,   g a ,   g b ,   g c ,   e ^ ( g , g ) a b c ) = 1 ] P r [ A ( g ,   g a ,   g b ,   g c ,   e ( g , g ) z ) = 1 ] | < ϵ , where a , b , c , z Z p . We say that the DBDH assumption holds if the PPT adversary has a negligible advantage ϵ in solving the DBDH problem.

3.3. Access Structure

Access structure is defined by the concepts of an authorized access subset and unauthorized access subset. Let P = { P 1 , P 2 , , P n } be a set of parties. A collection A 2 P is monotone if B , C : if B A and B C , then C A . A monotone access structure is a monotone collection A which is a non-empty subset for { P 1 , P 2 , , P n } , i.e., A 2 P { } . The set in A is called an authorized set, and the set not in A is called an unauthorized set.

3.4. Access Tree

An access tree is usually used to represent an access control policy. Let T be an access tree, and each non-leaf represents a threshold gate described by a threshold value and the number of its children nodes. Let n u m x represent the number of children of node x, and the children be labeled from the left to the right as { 1 , , n u m x } . Let k x represent the threshold value of x with 1 k x n u m x . If k x = 1 , the logic gate of node x is an “OR” gate. If k x = n u m x , the logic gate of node x is an “AND” gate. In an access tree T, a leaf is associated with an attribute, so each leaf node of T is described by an attribute and a threshold value k x = 1 .
Let p a r e n t ( x ) denote the parent of node x, a t t ( x ) denote the attribute associated with leaf node x, and l v s ( T ) denote the set of leaves of the access tree T. Let i n d e x ( x ) denote the label of the node x, and T x represent the subtree of T rooted at node x (thus, T r o o t = T ). If an attribute set γ meets the access tree T x , we denotes it as T x ( γ ) = 1 . Otherwise, T x ( γ ) = 0 . When x is a leaf node, if and only if a t t ( x ) γ , then T x ( γ ) = 1 . When x is a non-leaf node, we can compute T x ( γ ) for each child node x of node x. If at least k x children of the node x return 1, then T x ( γ ) = 1 .

4. System Model

In this section, we present the system model, the algorithm description of our proposed scheme and the security model.

4.1. System Model

The system model for our proposed scheme is shown as Figure 1, which involves four types of entities, namely Trusted Authority (TA), Data Owner (DO), Data User (DU) and Cloud Service Provider (CSP). First, the DO extracts the keywords from each data file and builds a secure-searchable keyword index with an attribute-based access policy before outsourcing them into the CSP. The CSP is responsible for many services, such as data storage, computation and search. When a DU wants to issue a search query over encrypted data, he will generate a search trapdoor according to his interested keyword by using his private key and submit it to the CSP. Having received the trapdoor, the CSP attempts to check whether the specified search keyword matches with the index, without knowing the content of the encrypted data and the search keyword. Finally, the CSP returns the corresponding search results to the DU if and only if the attributes of the data user on the trapdoor satisfy the access policies of secure-searchable indexes, and the search trapdoor matches the keyword index. In addition, a TA is in charge of generating and distributing public keys and master keys.

4.2. Algorithm Description of PEKS-CPABE Scheme

In this section, we present an overview of our proposed scheme, which is a tuple of five algorithms.
  • Setup ( 1 λ ) : The setup algorithm is invoked by the TA, which takes as input the security parameter λ , and outputs the public parameter p p and the master private key m s k ;
  • KeyGen ( p p , m s k , S U ) : The key generation algorithm is invoked by the TA, which takes as input the public parameter p p , the master private key m s k and the data user’s attribute set S U , and outputs the private key of the data user S K U ;
  • Encryption ( p p , T , w ) : The encryption algorithm is invoked by the DO, which takes as input the public parameter p p , the access tree T and the index keyword w, and outputs the encrypted index I w ;
  • TrapGen ( p p , S K U , w ) : The trapdoor generation algorithm is called the DU, which takes as input the public parameter p p , the private key of the data user S K U and the search query for keyword w , and outputs the trapdoor for query keyword T w ;
  • Search ( p p , I w , T w , S U ) : The search query algorithm is called the CSP, which takes as input the public parameter p p , the encrypted index I w , the trapdoor for query keyword T w and the data user’s attribute set S U . If the attributes of the data user on the trapdoor satisfy the access policies of secure searchable indexes, and the search trapdoor matches the keyword index, the algorithm returns 1. Otherwise, it returns 0.

4.3. Security Model

To demonstrate the security of our scheme, we design a security game: indistinguishability security against an adaptive chosen keyword attack (IND-CKA) game.
The IND-CKA security game between an adversary A and a challenger C is defined as follows.
  • Init: The adversary A chooses a challenging access tree T , which is sent to the challenger C ;
  • Setup: The challenger C runs the Setup ( 1 λ ) algorithms to generate public parameters p p and master key m s k . It gives p p to adversary A and keeps master key m s k ;
  • Phase 1: A can adaptively ask the simulator B for the trapdoors T w i of a series of keywords w i , and issue private key query and trapdoor query as follows:
    Private key query: The adversary A can adaptively ask the challenger C for a group of private keys S K U of some attributes. The challenger C runs the KeyGen ( p p , m s k , S U ) to generate a set of private keys S K U , and sends to the adversary A . The only restriction is that the responding private key does not satisfy T , and the C maintains a list L S K U of private keys;
    Trapdoor query: The adversary A can adaptively ask the challenger C for the trapdoors T w of a series of keywords w . The challenger C runs the Trapdoor ( p p , S K U , w ) to generate the trapdoor, and sends to the adversary A ;
  • Challenge: The adversary A sends the challenger C two keywords w 0 , w 1 on which it wishes to be challenged. The challenger C randomly selects a bit b { 0 , 1 } to encrypt and sends the encrypted keyword to the adversary A ;
  • Phase 2: The adversary A can repeat the query in Phase 1 and continue to ask for any keyword of his choice, except for the w 0 , w 1 ;
  • Guess: The adversary A outputs its guess of b and wins the game if b = b .
The advantage of an adversary A in winning the IND-CKA game is
A d v A I N D C K A ( λ ) = | P r [ b = b ] 1 2 |
Definition 1.
Our scheme is said to be IND-CKA secure if a probabilistic polynomial-time adversary wins the IND-CKA game with negligible advantage.

5. PEKS-CPABE Construction

In this section, we give a concrete construction of the proposed PEKS-CPABE scheme.
  • Setup ( 1 λ ) : The setup algorithm is called by the TA, which takes as input the security parameter λ , and outputs the public parameter p p and the master private key m s k , which is processed as follows:
    The TA first chooses two cyclic groups G and G T of order p, which is a λ bit prime, g is the generator of G , and selects a bilinear map e ^ : G × G G T ;
    Let H 1 : { 0 , 1 } Z p and H 2 : { 0 , 1 } G be two secure hash functions;
    Then, the TA selects a random element α , β Z p and sets
    p p = ( G , G T , p , e ^ , g , g α , g β , H 1 , H 2 ) ,   m s k = ( α , β ) ;
  • KeyGen ( p p , m s k , S U ) : The key generation algorithm is invoked by the TA, which takes as input the public parameter p p , the master private key m s k and the data user’s attribute set S U , and outputs the private key of the data user S K U , which is processed as follows:
    The TA randomly selects r Z p and computes K = g α + r β , K = g r ;
    For each attribute a t j S U , compute K a t j = K g H 1 ( a t j ) ;
    Set the private key of the data user as
    S K U = ( K , { ( K a t j ) | a t j S U } )
  • Encryption ( p p , T , w ) : The encryption algorithm is invoked by the DO, which takes as input the public parameter p p , the access tree T and the index keyword w, and outputs the encrypted index I w , which is processed as follows:
    The DO first computes I 1 = e ^ ( g , g ) α s e ^ ( g s β , H 2 ( w ) ) , I 2 = g s β ;
    For each node x in the access tree T, the DO chooses a d x degree polynomial q x in a top-down manner, where d x = k x 1 , where k x is the threshold value of node x;
    For the root node r o o t of access tree T, the DO randomly picks up a secret key s Z p and sets q r o o t ( 0 ) = s . Then, the DO randomly chooses d r o o t other points of to define the polynomial q r o o t completely;
    For other non-root node x, the DO sets q x ( 0 ) = q p a r e n t ( x ) ( i n d e x ( x ) ) , and randomly chooses d x other points to define the polynomial q x completely;
    Finally, for each node x l v s ( T ) , compute A x = g q x ( 0 ) and B x = g H 1 ( a t t ( x ) ) q x ( 0 ) . The encrypted index is given as
    I w = ( T , I 1 , I 2 , { ( A x , B x ) | x l v s ( T ) } )
  • TrapGen ( p p , S K U , w ) : The trapdoor generation algorithm is called the DU, which takes as input the public parameter p p , the private key of the data user S K U and the search query for keyword w , and outputs the trapdoor T w , which is processed as follows:
    The DU computes T 0 = K 1 H 2 ( w ) = g α + r β H 2 ( w ) ;
    For each a t j S U , compute T a t j = K a t j . The trapdoor is given as
    T w = ( T 0 , { ( T a t j ) | a t j S U } )
  • Search ( p p , I w , T w , S U ) : The search query algorithm is called by the CSP, which takes as input the public parameter p p , the encrypted index I w , the trapdoor for query keyword T w and the data user’s attribute set S U . The CSP selects a data user’s attribute set S U that satisfies the access tree T contained the encrypted index. If S U does not exist, the algorithm returns 0. Otherwise, it computes as follows:
    If the node x is a leaf node in the T, for each attribute a t j S U , then
    E x = e ^ ( T a t j , A x ) e ^ ( g , B x ) = e ^ ( g r g H 1 ( a t j ) , g q x ( 0 ) ) e ^ ( g , g H 1 ( a t t ( x ) ) q x ( 0 ) ) = e ^ ( g , g ) r q x ( 0 ) , a t t ( x ) = a t j , x l v s ( T ) .
    If the node x is a non-leaf node in the T, we get the E x by computing E x in a recursive manner, where x is the children nodes of x. Let S x represent an arbitrary k x set of children nodes x, if no such set exists, E x   =   ; otherwise, compute as follows
    E x = x S x E x Δ i , S x ( 0 ) = x S x ( e ^ ( g , g ) r q x ( 0 ) ) Δ i , S x ( 0 ) = x S x ( e ^ ( g , g ) r q p a r e n t ( x ) ( i n d e x ( x ) ) ) Δ i , S x ( 0 ) = x S x ( e ^ ( g , g ) r q x ( i ) ) Δ i , S x ( 0 ) = e ^ ( g , g ) r q x ( 0 )
    where i = i n d e x ( x ) , S x = { i n d e x ( x ) : x S x } ;
    If x is a root node in T, E r o o t = e ^ ( g , g ) r q r o o t ( 0 ) = e ^ ( g , g ) r s . Finally, if e ^ ( I 2 , T 0 ) = E r o o t I 1 , the search algorithm returns 1; otherwise, it returns 0.
    Correctness. I 1 and I 2 are generated by the encryption algorithm, and T 0 is generated in the trapdoor generation algorithm. The proposed PEKS-CPABE scheme is correct when the following equation holds.
    I 1 = e ^ ( I 2 , T 0 ) E r o o t = e ^ ( g s β , g α + r β H 2 ( w ) ) e ^ ( g , g ) r s = e ^ ( g , g ) s ( α + r ) e ^ ( g s β , H 2 ( w ) ) e ^ ( g , g ) r s = e ^ ( g , g ) α s e ^ ( g s β , H 2 ( w ) ) .
    If the query keyword w matches the encrypted keyword index, namely w = w , then we have the equation e ^ ( I 2 , T 0 ) E r o o t = I 1 hold.

6. Security Proof

In this section, we give the security proof of the proposed PEKS-CPABE scheme. Based on the aforementioned security model, we provide a detailed security proof that our scheme achieves selective indistinguishability security against an adaptive chosen keyword attack.
Theorem 1.
PEKS-CPABE scheme achieves IND-CKA security on the condition that DBDH problem is intractable.
Proof. 
Assume that A is an adversary that can break our proposed scheme, then we can construct a simulator B , and the goal is to distinguish between the DBDH tuple ( g a ,   g b ,   g c ,   Z = e ^ ( g ,   g ) a b c ) and a random tuple ( g a ,   g b ,   g c ,   Z = e ^ ( g , g ) z ) where a ,   b ,   c ,   z Z p . The IND-CKA security game between the adversary A and the simulator B is conducted as follows.
  • Init: The adversary A first chooses an access tree T to be challenged, which is sent to the simulator B ;
  • Setup: The simulator B randomly chooses α , β Z p , and computes g α , g β , e ^ ( g , g ) α . Then, B returns the public parameter p p = ( G , G T , p , e ^ , g , g α , g β , H 1 , H 2 ) which is sent to adversary A . H 2 ( w i ) is simulated as follows. If the w i has not been queried before, the simulator B randomly chooses ρ i Z p , adds ( w i , ρ i ) to the list O H 2 and outputs g ρ i ; otherwise, the simulator B returns g ρ i by searching ρ i from O H 2 ;
  • Phase 1: A can adaptively ask the simulator B for the trapdoors T w i of a series of keywords w i , and issue the O K e y G e n and O T r a p d o o r oracles as follows.
    O K e y G e n : The adversary A can adaptively ask the simulator B for a group of private keys S K U 1 , , S K U n of some attributes S U 1 , , S U n . The attribute sets embedded into corresponding private keys do not satisfy T . The simulator B randomly selects r Z p and computes K = g α + r β . For each attribute a t j S U , compute K a t j = g r g H 1 ( a t j ) . The simulator B sends the private key S K U = ( K , K a t j ) to A , and maintains a list L S K U of private keys.
    O T r a p d o o r : The simulator B first searches the O K e y G e n oracle to obtain the secret key as
    ( K , { ( K a t j , K a t j ) | a t j S U } ) . Then, B computes T 0 = K H 2 ( w i ) = g α + r β g ρ i . For each a t j S U , compute T a t j = K a t j . Finally, B generates the trapdoor as T w i = ( T 0 , { ( T a t j ) | a t j S U } ) , and B sends T w i to the adversary A ;
  • Challenge: The adversary A sends the simulator B two keywords w 0 , w 1 on which it wishes to be challenged. The simulator B randomly selects a bit b { 0 , 1 } to encrypt and generates the encrypted keyword index as follows: I 1 = Z e ^ ( g a β , H 2 ( w b ) ) , I 2 = g a β , A x = g q x ( 0 ) , B x = g H 1 ( a t t ( x ) ) q x ( 0 ) , x l v s ( T ) . Namely, I w b = ( T , I 1 , I 2 , { ( A x , B x ) | x l v s ( T ) } ) where a Z p . Then, B sends I w b to the adversary A ;
  • Phase 2: The adversary A can repeat query in Phase 1 and continue to ask for any keyword of his choice, except for the w 0 , w 1 ;
  • Guess: The adversary A outputs its guess b of b. If b = b , B outputs 1; otherwise B randomly outputs 0 or 1.
There are two conditions, as follows:
  • If Z = e ^ ( g , g ) a b c , a valid ciphertext I w b is given to the adversary A , and the adversary A has an advantage ϵ to win this game.
    The ciphertexts I w b is valid. I 1 = Z e ^ ( g a β , H 2 ( w b ) ) = e ^ ( g , g ) a b c e ^ ( g a β , H 2 ( w b ) ) , I 2 = g a β . Since α , s are randomly selected, a , b , c , Z p , let a = s ,   b c = α , I 1 ,   I 2 can be denoted as I 1 = e ^ ( g , g ) s α e ^ ( g s β , H 2 ( w b ) ) , I 2 = g s β . This means I w b is the valid ciphertext. Through ϵ is the advantage that the adversary A outputs a correct guess, therefore we have that P r [ B ( g ,   g a ,   g b ,   g c ,   Z = e ^ ( g ,   g ) a b c ) = 1 ] = 1 2 + ϵ ;
  • If Z e ^ ( g , g ) a b c , I w b is a random ciphertext. A has nothing to do with the guess, so the adversary A cannot acquire any advantage in this IND-CKA security game but a random guess. Therefore, we have P r [ B ( g ,   g a ,   g b ,   g c ,   Z = e ^ ( g ,   g ) z ) = 1 ] = 1 2 .
Finally, the overall advantage that B can solve the DBDH problem in the IND-CKA security is as follows: A d v B I N D C K A ( λ ) = 1 2 ( 1 2 + ϵ ) + 1 2 · 1 2 1 2 = ϵ 2
Thus, we have a conclusion that if the probabilistic polynomial time adversary A has a non-negligible advantage ϵ in breaking IND-CKA security, then we can construct a simulator B to solve the DBDH problem with the non-negligible advantage ϵ 2 . From the above analysis, we know that our proposed PEKS-CPABE scheme is IND-CKA secure on the condition that the DBDH problem is intractable. This completes the proof. □

7. Performance Analysis

In this section, we show the performance analysis of our proposed PEKS-CPABE scheme in terms of theoretical analysis and experimental analysis, and further compare our proposed scheme with the state-of-the-art CP-ABKS [22] scheme and CP-ABSE [23] scheme. Table 1 shows the notations of the performance analysis. For the theoretical analysis, we mainly focus on the computation cost and storage cost. For convenience of comparison, we mainly consider several time-consuming operations, as follows: the bilinear pairing operation P a i r mapping two elements in group G to group G T , the hash function operation H mapping the arbitrary string to an element in group G , a modular exponentiation operation E G in G and a modular exponentiation operation E G T in G T . We ignore the multiplication operations and hash operations mapping the arbitrary string to an element in group Z p because of the increased efficiency.

7.1. Theoretical Analysis

In Table 2, we evaluate the computation cost of KeyGen algorithm, Encryption algorithm, TrapGen algorithm and Search algorithm under the same access control policy tree, respectively. We observe that our scheme is much more efficient than the CP-ABKS [22] scheme and CP-ABSE [23] scheme in the KeyGen algorithm and Encryption algorithm. Although we notice that our scheme has a higher computational overhead than the CP-ABSE [23] scheme in the TrapGen algorithm, the hash function operation time is minimal. In the Search algorithm, our scheme performs similarly to that of CP-ABSE [23] scheme, and the PEKS-CPABE scheme has a better performance than the CP-ABKS [22] scheme.
In Table 3, we show the storage cost comparison. We observe that the storage cost of our scheme outperforms the CP-ABKS [22] scheme and CP-ABSE [23] scheme in the KeyGen algorithm. In the execution Encryption algorithm and TrapGen algorithm, the storage cost of our scheme is the same as that of the CP-ABSE [23] scheme, but much less than that of the CP-ABKS [22] scheme. Although the CP-ABSE scheme has better search performance than the CP-ABKS scheme, the cost of KeyGen algorithm and Encryption algorithm bring in a much higher overhead. Our scheme solves this problem at the same time, with greater efficiency, therefore, with respect to theoretical analysis, our scheme is acceptable in the cloud.

7.2. Experimental Analysis

To evaluate the actual performance of our scheme, we implement CP-ABKS [22], CP-ABSE [23] and our scheme using Java language based on the Java Pairing Based Cryptography Library (JPBC) [31]. Our experimental platform is based on a Windows 10 server with Intel(R) Core(TM) i7-8565U CPU @ 1.80 GHz and 8.00GB RAM. The running environment of our experiment is Java Runtime Environment 1.8 (JRE1.8). In our experiment, we instantiated the bilinear map with Type A: y 2 = x 3 + x . For comparison convenience, we set the access policy tree as “AND” access tree “ a t 1 AND a t 2 AND, ⋯, AND a t N ”, and the number of a data user’s attributes S is equal to the number of attributes that are involved in the access policy, from 1 to 50 with step length 10, namely, N = S [ 1 , 50 ] . We conduct each experiment many times to obtain the average execution time under the same access control policy. Figure 2 shows the performance comparison of various schemes.
As shown in Figure 2a, we can find that the time of key generation in our scheme is more efficient than the CP-ABKS scheme and CP-ABSE scheme. For example, when setting N = 50 , our scheme needs 1061 ms to generate keys, however, both CP-ABKS scheme and CP-ABSE scheme need 4333 and 4314 ms, respectively. As illustrated in Figure 2b, in our scheme, the time cost to generate ciphertexts is the lowest out of the three schemes. For example, when setting N = 50 , our scheme needs 3074 ms to generate ciphertexts, however, both the CP-ABKS scheme and CP-ABSE scheme need 4375 and 4277 ms, respectively. From Figure 2c,d, we can show that our scheme has the better search performance. In the execution of trapdoor generation and search, our scheme and the CP-ABSE scheme outperform the CP-ABKS scheme. Therefore, our scheme is acceptable in practice and suitable for the cloud.

8. Conclusions

In this paper, we propose a privacy-preserving and efficient public key encryption with a keyword search scheme based on CP-ABE to support both fine-grained access control and keyword search over encrypted data simultaneously. Then, we show that our scheme achieves selective indistinguishability security against an adaptive chosen keyword attack on the condition that the DBDH problem is intractable. Meanwhile, we also analyzed the performance of our proposed scheme from the aspects of theoretical analysis and experimental analysis. At last, the experimental results further demonstrate that our scheme performs better than the CP-ABKS scheme proposed in [22] and CP-ABSE scheme proposed in [23]. Besides, our work only considers single keyword search. For the part of the future work, we try to enhance the search functionality and further explore an attribute-based multi-keyword search.

Author Contributions

Conceptualization, Y.Z.; methodology, Y.Z.; software, Y.Z.; validation, S.Z. and L.W.; formal analysis, S.Z. and L.W.; investigation, Y.Z.; writing—original draft preparation, Y.Z.; writing—review and editing, S.Z. and L.W; project administration, L.W.; funding acquisition, L.W. All authors have read and agreed to the published version of the manuscript.

Funding

This work was supported by the National Key R&D Program of China (2017YFB0803001) and the National Natural Science Foundation of China (NSFC) (No. 61972050).

Acknowledgments

In addition, we gratefully acknowledge Jing Li and Jie Cheng from the State Grid Information & Telecommunication Branch for their constructive criticism and suggestions in the revision of this manuscript.

Conflicts of Interest

The authors declare no conflict of interest.

Abbreviations

The following abbreviations are used in this manuscript:
PEKSPublic Key Encryption with Keyword Search
ABEAttribute-based Encryption
CP-ABECiphertext-policy Attribute-based Encryption
KP-ABEKey-policy Attribute-based Encryption
SESearchable Encryption
SSESymmetric Searchable Encryption
TATrusted Authority
DOData Owner
DUData User
CSPCloud Service Provider

References

  1. Paillier, P. Public-key cryptosystems based on composite degree residuosity classes. In International Conference on the Theory and Applications of Cryptographic Techniques; Springer: Berlin/Heidelberg, Germany, 1999; pp. 223–238. [Google Scholar]
  2. Gentry, C. Fully homomorphic encryption using ideal lattices. In Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing, Bethesda, MD, USA, 31 May–2 June 2009; pp. 169–178. [Google Scholar]
  3. Song, D.X.; Wagner, D.; Perrig, A. Practical techniques for searches on encrypted data. In Proceedings of the 2000 IEEE Symposium on Security and Privacy. S&P 2000, Berkeley, CA, USA, 14–17 May 2000; pp. 44–55. [Google Scholar]
  4. Curtmola, R.; Garay, J.; Kamara, S.; Ostrovsky, R. Searchable symmetric encryption: Improved definitions and efficient constructions. J. Comput. Secur. 2011, 19, 895–934. [Google Scholar] [CrossRef]
  5. Kamara, S.; Papamanthou, C.; Roeder, T. Dynamic searchable symmetric encryption. In Proceedings of the 2012 ACM Conference on Computer and Communications Security, Raleigh, NC, USA, 16–18 October 2012; pp. 965–976. [Google Scholar]
  6. Kamara, S.; Papamanthou, C. Parallel and dynamic searchable symmetric encryption. In International Conference on Financial Cryptography and Data Security; Springer: Berlin/Heidelberg, Germany, 2013; pp. 258–274. [Google Scholar]
  7. Li, H.; Yang, Y.; Dai, Y.; Bai, J.; Yu, S.; Xiang, Y. Achieving secure and efficient dynamic searchable symmetric encryption over medical cloud data. IEEE Trans. Cloud Comput. 2017. [Google Scholar] [CrossRef]
  8. Ghareh Chamani, J.; Papadopoulos, D.; Papamanthou, C.; Jalili, R. New constructions for forward and backward private symmetric searchable encryption. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, Toronto, ON, Canada, 15–19 October 2018; pp. 1038–1055. [Google Scholar]
  9. Sun, S.F.; Yuan, X.; Liu, J.K.; Steinfeld, R.; Sakzad, A.; Vo, V.; Nepal, S. Practical backward-secure searchable encryption from symmetric puncturable encryption. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, Toronto, ON, Canada, 15–19 October 2018; pp. 763–780. [Google Scholar]
  10. Wang, K.; Dong, X.; Shen, J.; Cao, Z. An Effective Verifiable Symmetric Searchable Encryption Scheme in Cloud Computing. In Proceedings of the 2019 7th International Conference on Information Technology: IoT and Smart City, Kuala, Malaysia, 18 April 2019; pp. 98–102. [Google Scholar]
  11. Boneh, D.; Di Crescenzo, G.; Ostrovsky, R.; Persiano, G. Public key encryption with keyword search. In International Conference on the Theory and Applications of Cryptographic Techniques; Springer: Berlin/Heidelberg, Germany, 2004; pp. 506–522. [Google Scholar]
  12. Abdalla, M.; Bellare, M.; Catalano, D.; Kiltz, E.; Kohno, T.; Lange, T.; Malone-Lee, J.; Neven, G.; Paillier, P.; Shi, H. Searchable encryption revisited: Consistency properties, relation to anonymous IBE, and extensions. In Annual International Cryptology Conference; Springer: Berlin/Heidelberg, Germany, 2005; pp. 205–222. [Google Scholar]
  13. Park, D.J.; Kim, K.; Lee, P.J. Public key encryption with conjunctive field keyword search. In International Workshop on Information Security Applications; Springer: Berlin/Heidelberg, Germany, 2004; pp. 73–86. [Google Scholar]
  14. Boneh, D.; Waters, B. Conjunctive, subset, and range queries on encrypted data. In Theory of Cryptography Conference; Springer: Berlin/Heidelberg, Germany, 2007; pp. 535–554. [Google Scholar]
  15. Baek, J.; Safavi-Naini, R.; Susilo, W. Public key encryption with keyword search revisited. In International Conference on Computational Science and Its Applications; Springer: Berlin/Heidelberg, Germany, 2008; pp. 1249–1259. [Google Scholar]
  16. Tang, Q.; Chen, L. Public-key encryption with registered keyword search. In European Public Key Infrastructure Workshop; Springer: Berlin/Heidelberg, Germany, 2009; pp. 163–178. [Google Scholar]
  17. Fang, L.; Susilo, W.; Ge, C.; Wang, J. Public key encryption with keyword search secure against keyword guessing attacks without random oracle. Inf. Sci. 2013, 238, 221–241. [Google Scholar] [CrossRef]
  18. Lv, Z.; Hong, C.; Zhang, M.; Feng, D. Expressive and secure searchable encryption in the public key setting. In International Conference on Information Security; Springer: Berlin/Heidelberg, Germany, 2014; pp. 364–376. [Google Scholar]
  19. Huang, Q.; Li, H. An efficient public-key searchable encryption scheme secure against inside keyword guessing attacks. Inf. Sci. 2017, 403, 1–14. [Google Scholar] [CrossRef]
  20. Zhang, Y.; Wang, Y.; Li, Y. Searchable Public Key Encryption Supporting Semantic Multi-Keywords Search. IEEE Access 2019, 7, 122078–122090. [Google Scholar] [CrossRef]
  21. Zhou, Y.; Li, N.; Tian, Y.; An, D.; Wang, L. Public Key Encryption with Keyword Search in Cloud: A Survey. Entropy 2020, 22, 421. [Google Scholar] [CrossRef]
  22. Zheng, Q.; Xu, S.; Ateniese, G. VABKS: Verifiable attribute-based keyword search over outsourced encrypted data. In Proceedings of the IEEE INFOCOM 2014-IEEE Conference on Computer Communications, Toronto, ON, Canada, 27 April–2 May 2014; pp. 522–530. [Google Scholar]
  23. Yin, H.; Zhang, J.; Xiong, Y.; Ou, L.; Li, F.; Liao, S.; Li, K. CP-ABSE: A ciphertext-policy attribute-based searchable encryption scheme. IEEE Access 2019, 7, 5682–5694. [Google Scholar] [CrossRef]
  24. Sahai, A.; Waters, B. Fuzzy identity-based encryption. In Annual International Conference on the Theory and Applications of Cryptographic Techniques; Springer: Berlin/Heidelberg, Germany, 2005; pp. 457–473. [Google Scholar]
  25. Goyal, V.; Pandey, O.; Sahai, A.; Waters, B. Attribute-based encryption for fine-grained access control of encrypted data. In Proceedings of the 13th ACM Conference on Computer and Communications Security, Alexandria, VA, USA, 30 October–3 November 2006; pp. 89–98. [Google Scholar]
  26. Bethencourt, J.; Sahai, A.; Waters, B. Ciphertext-policy attribute-based encryption. In Proceedings of the 2007 IEEE Symposium on Security and Privacy (SP’07), Berkeley, CA, USA, 20–23 May 2007; pp. 321–334. [Google Scholar]
  27. Dong, Q.; Guan, Z.; Chen, Z. Attribute-based keyword search efficiency enhancement via an online/offline approach. In Proceedings of the 2015 IEEE 21st International Conference on Parallel and Distributed Systems (ICPADS), Melbourne, Australia, 14–17 December 2015; pp. 298–305. [Google Scholar]
  28. Li, J.; Lin, X.; Zhang, Y.; Han, J. KSF-OABE: Outsourced attribute-based encryption with keyword search function for cloud storage. IEEE Trans. Serv. Comput. 2016, 10, 715–725. [Google Scholar] [CrossRef]
  29. Sun, W.; Yu, S.; Lou, W.; Hou, Y.T.; Li, H. Protecting Your Right: Verifiable Attribute-Based Keyword Search with Fine-Grained Owner-Enforced Search Authorization in the Cloud. IEEE Trans. Parallel Distrib. Syst. 2016, 27, 1187–1198. [Google Scholar] [CrossRef]
  30. Qiu, S.; Liu, J.; Shi, Y.; Zhang, R. Hidden policy ciphertext-policy attribute-based encryption with keyword search against keyword guessing attack. Sci. China Inf. Sci. 2017, 60, 052105. [Google Scholar] [CrossRef]
  31. De Caro, A.; Iovino, V. jPBC: Java pairing based cryptography. In Proceedings of the 2011 IEEE Symposium on Computers and Communications (ISCC), Corfu, Greece, 28 June 28–1 July 2011; pp. 850–855. [Google Scholar]
Figure 1. System Model of Our Scheme.
Figure 1. System Model of Our Scheme.
Cryptography 04 00028 g001
Figure 2. The performance comparison of various schemes.
Figure 2. The performance comparison of various schemes.
Cryptography 04 00028 g002
Table 1. Notations for performance analysis.
Table 1. Notations for performance analysis.
NotationDescription
E G The time of a modular exponentiation in G
E G T The time of a modular exponentiation in G T
P a i r The time of a bilinear pairing
HThe time of hash operation mapping a bit-string to an element in G
| G | The number of elements in G
| G T | The number of elements in G T
| Z p | The number of elements in Z p
SThe number of a data user’s attribute
NThe number of attributes that are involved in a data owner’s access control policy
Table 2. The comparison of computation cost.
Table 2. The comparison of computation cost.
AlgorithmCP-ABKS [22]CP-ABSE [23]PEKS-CPABE (Ours)
KeyGen ( 2 S + 2 ) E G + S H ( 2 S + 3 ) E G + S H ( S + 2 ) E G
Encryption ( 2 N + 4 ) E G + N H ( 2 N + 2 ) E G + E G T + 2 P a i r + N H ( 2 N + 1 ) E G + E G T + 2 P a i r
TrapGen ( 2 S + 4 ) E G E G E G + H
Search ( 2 N + 3 ) P a i r + N E G T ( 2 N + 1 ) P a i r + N E G T ( 2 N + 1 ) P a i r + N E G T
Table 3. The comparison of storage cost.
Table 3. The comparison of storage cost.
AlgorithmCP-ABKS [22]CP-ABSE [23]PEKS-CPABE (Ours)
KeyGen ( 2 S + 1 ) l o g | G | ( 2 S + 2 ) l o g | G | ( S + 1 ) l o g | G |
Encryption ( 2 N + 3 ) l o g | G | ( 2 N + 1 ) l o g | G | + l o g | G T | ( 2 N + 1 ) l o g | G | + l o g | G T |
TrapGen ( 2 S + 3 ) l o g | G | ( 2 S + 1 ) l o g | G | ( S + 1 ) l o g | G |
Back to TopTop