Searchable encryption in a public-key setting

SEARCHABLE ENCRYPTION IN A PUBLIC-KEY SETTING provides flexibility as there is no need of complicated secret key-sharing processes among the users as compared to the symmetric-key setting, which makes it suitable for the multi-user shared cloud storage environment. Cloud storage is becoming very popular among organizations because of features like optimized storage cost, ease of data management, and anytime anywhere access capabilities, and slowly cloud storage is becoming a necessity. However, organizations feel somewhat reluctant to adopt this platform because of security concerns. The data stored at the third-party cloud server may not be safe if it is stored as it is in plaintext form. To resolve the trust issues, it is suggested to store the data in encrypted form. This solves the problem; however, the selective access of the data becomes infeasible. One trivial solution is to first download all the data and decrypt it locally, but in that case, why would someone use cloud storage, if everything has to be done manually? The user must be able to retrieve only the desired data from the encrypted data stored at the cloud server. The first requirement to retrieve the desired data is the ability to perform a search over the encrypted data. A searchable encryption technique plays a critical role in this scenario. As we know, searchable encryption can be developed using either the symmetric-key or the public-key setting. Using a symmetric-key setting to create the searchable encryption scheme for the shared cloud storage environment may cause a lot of complexity in terms of sharing the secret key among the cloud users. As the number of users increases, the internal secret key distribution process also becomes difficult. Therefore, the public-key setting is preferred. In this chapter, we will discuss all aspects of the searchable encryption scheme in a public-key setting.

System Definition And System Model

In this section, we will formally define searchable encryption by introducing the different algorithms involved in a searchable encryption scheme and also provide the correctness condition for the searchable encryption schemes using the probabilistic definitions given in Chapter 4. Further, we will discuss the architecture of a searchable encryption system and explain the role of each entity involved in the system.

System Definition

Like any encryption scheme, the searchable encryption scheme also consists of the four basic algorithms: key generation, index generation, trapdoor generation, and search. These algorithms are derived from the algorithms in an encryption scheme, and we will discuss the similarity and relationship between each algorithm here and the algorithms in any standard public-key encryption (PKE) scheme.

[Kpilb, Kpri] <— GenKey(”): The key-generation algorithm here and in any standard PKE scheme are the same. This algorithm also takes the security parameter (unary format) and outputs the public and private key pairs, like any PKE scheme.

C, <— GenIndex(Kp,,Wj): The index-generation algorithm is the same as the encryption algorithm in any PKE scheme. It also takes the public key and encrypts the keywords associated with the data file using this public key. Usually, in a PKE scheme, we encrypt a message with the public key, here the message is equivalent to the keyword. The collection of ciphertext of the keyword is sometimes called the encrypted index because, by default, the direct or the inverted index approach is implemented by the cloud server to store the encrypted data files and their associated encrypted keywords. Thus, in the context of searchable encryption this algorithm is called the index-generation algorithm; otherwise, it is merely an encryption algorithm.

T GenTrap(Kpri, w,)' The trapdoor-generation algorithm is similar to the decryption algorithm in a PKE scheme in terms of one input, i.e., the private key of the user. But instead of taking the ciphertext at this step, a searchable encryption scheme conserves it for the search step. Typically, the secret key is used for decryption, but here we want to delegate our search capability to the cloud server using this secret key but without disclosing it. Here, for each keyword we want to search, we generate a kind of secret key for that keyword, and in the cryptographic community, it is called the search trapdoor or sometimes the search token. The search trapdoor, just like a usual computer trapdoor, facilitates the cloud server performing a search over the encrypted data.

0/1 <— Searcb{Tj, C,): The search algorithm is a new algorithm concerning PKE schemes. This algorithm uses the trapdoor of the keyword and searches each ciphertext for that keyword. If a match is found it returns 1, otherwise it returns 0. Sometimes it is explicitly shown in a scheme that it returns a reference of the data file associated with that keyword; otherwise, it is implicitly assumed that the associated data files will be provided to the user who generated the trapdoor.

Equation 5.1 states that we conduct an experiment where we have generated a public-private key pair, and using the public key, we have appropriately encrypted a keyword to get its ciphertext, and using the corresponding private key, we generated the trapdoor for the same keyword. After that, we provided both the ciphertext and search trapdoor to the search algorithm. If the search algorithm returns binary value 1 with probability one, then we say our scheme is always correct.

This a comprehensive system definition that we have discussed; however, in the literature there exist some variants of this definition depending upon the type of method and underlying technique used for developing the searchable encryption scheme. The searchable encryption schemes may either be designed using the core of the underlying encryption scheme (like we have just discussed above) or may use a transformation method that converts the underlying encryption scheme into the searchable encryption. The system definition of a searchable encryption scheme developed using the transformation method is stated as follows:

[PKse, SKse]PP, of the underlying encryption schemes are used as the public key of the searchable encryption scheme, PKse (it may include some other parameters also in addition to public parameters of the underlying encryption scheme, for example the hashes defined for mapping purpose), and the master secret key, MSK, is used as the corresponding secret key in the searchable encryption scheme, SKse-

T, <— GenTrap(SKsE, w,Y This algorithm internally calls the key-generation algorithm of the underlying encryption scheme; the keyword is taken as input after mapping through some hash function. For example: if IBE is used as an underlying scheme, then a hash function, H, is used which maps each keyword with a unique identity in the identity space, T, <- GenKey(MSKiBE, H[w,))-

C, GenIndex(PKsE,Wi): This algorithm internally calls the encryption algorithm of the underlying encryption scheme. Taking the same example of an IBE scheme, this algorithms call Епс{РРш, H[w,), m:) the algorithm which takes the keyword after application of a hash function (maps keyword to identity) and randomly selects a message, to encrypt.

0/1 Searcb(PKsE, T, C,): This algorithm internally calls the decryption algorithm of the underlying scheme. Taking the same example of an IBE scheme, this algorithms calls DeciPPm, T, Q) and outputs binary value 1 if the decryption algorithm correctly outputs the encrypted message, m,; otherwise, it returns 0.

The above-stated steps present the variation of the searchable encryption definition based on the type of methodology used for developing a searchable encryption scheme. Next, we will discuss another variation depending upon the type of underlying scheme used. Here, we will consider that ABE is used as an underlying scheme and discuss the definition of the corresponding searchable encryption scheme concerning ABE. For joint presentation, let Ik denote the input to the key-generation algorithm, GenKey and Ie denotes the input to the generate index algorithm, Genlndex. In KP-ABE, Ik and Ie are the access policy and the set of attributes, respectively. In CP-ABE, Ik and Ie are the set of attributes and the access policy, respectively.

(PP, MSK) The setup algorithm takes the attribute universe, Att = [attb att,,.....,аЩщ] and keyword space,

W = [wuw,,....., t^|K,|), in addition to the security parameter, 1", and

outputs the public parameters, PP , and master secret key, MSK.

SK„ Ik): This algorithm takes the MSK and the credentials of a user, u, Ik, and generates his private key corresponding to his credentials, i.e. SK„.

C, <— GenIndex(PP, w, e W, IE): This algorithm encrypts the keyword, w„ using Ie and PP and outputs the ciphertext, C,.

T, <— GenTrap(SK„, w, e W): This algorithm generates the trapdoor for the keyword, w„ using the secret key of the user u, SK„.

0/1 <— Search(PP, C, , T;): This algorithm will be executed only if the satisfiability condition holds between Ik and Ie- If the satisfiability condition holds, this algorithm searches for the keyword contained in the trapdoor by searching all the ciphertexts one by one and returns 1 if a match is found, otherwise it returns 0

< Prev   CONTENTS   Source   Next >