Broad Categories Of Searchable Encryption In A Public-key Setting

In this section, we will discuss different categories of SE schemes based on the type of underlying encryption scheme used to develop the searchable encryption schemes [1]. In public-key setting there are some leading techniques like IBE [2, [3]4], ABE [57], hidden vector encryption (HVE) etc. which are frequently used for the construction of searchable encryption scheme. Among these, we will discuss the searchable encryption schemes using the first two primitives, i.e. IBE and ABE.

Ibe-based Se Schemes

The first IBE-based searchable encryption scheme was developed by Boneh et al [8]; a detailed description of this scheme and some of its variants has already been given in Chapter 3. In this section, we will discuss the searchable

Transformation mechanism from IBE to searchable encryption

Figure 5.4 Transformation mechanism from IBE to searchable encryption.

encryption schemes developed using a transformation from the IBE scheme. The general transformation mechanism from an IBE to searchable encryption is shown below in Figure 5.4.

The first searchable encryption using the transformation method was proposed by Khader [9]. A transformation method was applied on a k-resilient IBE [2] scheme to construct the PEKS scheme. They remarked on some facts about the transformation mechanism, such as the IBE scheme which we are planning to transform to IBE must be anonymous, otherwise it would expose the keywords. Another fact concerns the consistency of the resulting SE scheme; they stated that the underlying scheme must be secure in the appropriate security model, because only then would the resulting scheme be consistent and secure. The proposed scheme is consistent because the underlying IBE scheme is secure against chosen ciphertext attack. Further, they performed multi-keyword search and also eliminated the need for the secure channel.

PEKS revisited

A formalization of the transformation mechanism from anonymous IBE to PEKS scheme was given by Abdalla et al. [10]. They formally proved the consistency of the resulting scheme. Further, they proposed the following extensions to the basic idea: i) added a HIBE (anonymous hierarchical IBE) to the searchable encryption transformation, and ii) added the concept of temporary keyword search. The temporary keyword search prevents the server from learning about the past and future keyword ciphertexts once the server has received the trapdoor. Hence, even if the server memorizes the trapdoor it cannot find the link between the trapdoor and the keyword ciphertext. This was achieved by limiting the duration for which the trapdoor is valid.


An instantiation of the transformation mechanism was first given by Xu et al [11]. For demonstration purposes they have used an IBE scheme by Boneh and Franklin [12]. Further, they have developed a method to make their scheme immune to KGA. In their method, they divided the trapdoor into fuzzy and exact trapdoors such that two or more keywords share the same fuzzy trapdoor. When the receiver wanted to search something then he/she would send the fuzzy trapdoor to the cloud server. The cloud server could not guess the keyword even if had the fuzzy trapdoor for all the keywords, which resulted in a scheme which was immune to KGA. To construct the fuzzy trapdoor, they used a fuzzy function which returned the same fuzzy value for every two keywords if the keyword space was even. If the keyword space was odd, then the last three keywords had the same fuzzy value and for the rest of the keywords every two keywords had the same fuzzy value. Therefore, with a probability of 1/2 or 1/3 the malicious cloud server could still guess the keyword associated with the search trapdoor. Flence, to a make a scheme more secure against KGA there is a need to further reduce this probability and this was achieved by designing a fuzzy function which used the modulus operator and the concept of congruence class [13]. They designed their fuzzy function such that k keywords share the same fuzzy trapdoor, thus reduced the keyword guessing probability to 1/k and hence improved the security against KGA.

Table 5.1 compares the storage and computational cost.

Abe-based Se Schemes

Attribute-based searchable encryption (ABSE) is a technique that enables secure search over encrypted data stored in the cloud [14]. In an ABSE scheme, the finegrained access control is achieved with the help of an access policy/structure

Table 5.1 Comparative analysis of the existing schemes in literature


Storage cost

Computational cost

PEKS based on k-Resilient IBE

Khader [9]

Encrypted Index



PEKS using fuzzy function for keyword search trapdoor

Xu et al. [11]

Encrypted Index



Mamta et al. [13]

Encrypted Index



which represents the relations among various attributes a user may possess. This access policy is either associated with the ciphertext or with the secret key of the user and thus results in two design frameworks and either one of them can be used as ABE. If the access policy is embedded in the ciphertext then it is called ciphertext-policy ABE (CP-ABE) [15, 16] and if it is associated with the secret key, then it is called key-policy ABE (KP-ABE) [6, 17].

In CP-ABE, the data owner has full control over his/her data because the access policy is associated with the ciphertext through which the data owner can define the users who can have access to his/her data. On the other hand, KP-ABE is suitable for scenarios where the data owner wants to broadcast his/her data. Here, only those users whose access policy agree with the attributes present in the broadcasted data will be able to gain access to the data. In both the frameworks, to provide fine-grained access control, there is a need of an extra entity called “attribute” which will decide who will access what. An attribute can be about anyone or anything. For example, there is a Ph.D. scholar in the department of computer engineering. Here, Ph.D. and computer engineering are the attributes of that user. If the institute has released marks of the computer engineering department, then a user who possess this attribute will be able to see his/her marks. Because of these attributes there will be an increase in same number of components in the ciphertext and the secret key of the user. Thus, there is an increase in complexity both in terms of storage cost and computational cost. Hence, it is required to develop secure and efficient ABSE schemes where this cost can be reduced by eliminating dependency on the attributes and making the size of ciphertext and secret key etc. constant. Many ABSE schemes have been proposed in the literature to support multi-user cloud storage environment [18, 19, 20]. The combination of ABE and SE definitely provides fine-grained search capabilities but it is achieved at the cost of increased complexity both in terms of storage cost and computational cost [21], [22].

Considering the page limit, we will provide highlights of some of KP-ABE- and CP-ABE based searchable encryption schemes.

< Prev   CONTENTS   Source   Next >