Broad Categorization Of Searchable Encryption Schemes
Searchable encryption schemes can be developed using either symmetric key or public-key encryption. In the cloud storage environment, public-key setting is a preferable choice as there are multiple users who can have access to the shared storage and symmetric-key encryption requires key distribution among these users which is a very complicated process, whereas in the public- key setting no such key sharing is required. Therefore, considering the shared cloud storage environment, this book mainly discusses the searchable encryption schemes developed using public-key cryptographic primitive. However, in this chapter, we will mention some pioneering work done in the area of searchable encryption in the symmetric key and discuss some of them in the public-key setting.
Symmetric Searchable Encryption
Symmetric-key primitives allow a single user to read and write data, and allows only the secret key holder to create searchable ciphertexts and trapdoors [13]. The immediate application of symmetric searchable encryption (SSE) can be seen in the scenario where some user wants to store his/her data on the cloud storage in an encrypted form and later he/she can perform search on it to retrieve the required data [14]. The index approach is explicitly mentioned and addressed in the SSE schemes only. The first SSE was proposed by Song et al. [15]. The proposed scheme supports equality query and was developed to handle just one keyword. To encrypt the data, first they break it into fixed size blocks called words and then each word is encrypted independently by inserting a hash value in the specific format. The ciphertext resulting from this process is itself searchable. The cloud server performs search by extracting the hash and looking for the specific format indicated by the user. However, this scheme has a restriction that it needs to break the data into fixed size words which are incompatible with the existing encryption standard. Further, they did nor provide any formal security definition or security proof for their scheme. Later, in 2003 Goh [16] relaxed the fixed size restriction in the Song et al. scheme. They used a direct index approach where an index is built for every data file using bloom filters. In 2005, Chang and Mitzenmacher [17] developed a SSE scheme and, like the Goh scheme, they used a direct index approach where an index is built based on the dictionary of search keywords instead of bloom filters, which inherently have very high false positive rate. In 2006, Curtmola et al. [18] for the first time used an inverted-index approach and achieved the sublinear search time. The comparative analysis of these pioneer works in the domain of SSE in terms of computational complexity and key feature is given below in Table 3.1.
We mentioned earlier that we are considering a cloud storage environment where the data owner may want to share his/her data and is not merely storing it for his/her own use. Indeed, the symmetric-key encryption is fast, but in the scenario which we are considering, the symmetric-key encryption becomes quite complicated due to the distribution of the secret keys to all the users. Therefore, we will discuss searchable encryption in the public-key setting with great detail in Chapter 5 and an overview is presented in the subsequent section.
Table 3.1 Comparative analysis of pioneering works in the SSE domain
Scheme |
Encryption time |
Trapdoor time |
Search time |
Feature |
Song et al. [15] |
OK |
к |
DK |
Sequential scan |
Chang & Mitzenmacher [17] |
D(K + K") |
2k |
D |
Dictionary of search keywords |
E.J.Goh [16] |
DK' |
к |
D к |
Bloom Filter index |
Curtmola et al. [18] |
3K" • D + D(w) |
2k |
D(w) |
Sublinear search time |
Notes:
D — Number of documents К — Number of keywords per document K' — Number of distinct keywords per document K" — Number of distinct keywords in database к — Number of keywords per trapdoor
Searchable Encryption In Public-key Setting
The public-key cryptographic primitives like identity-based encryption and attribute-based encryption are developed using a tool called bilinear maps and often such schemes are called pairing-based cryptographic schemes. The searchable encryption schemes in a public-key setting will obviously use this tool. Therefore, before we start our discussion on public-key based searchable encryption schemes, let us discuss some interesting facts about this powerful tool first.
Bilinear map
Bilinear map is a function which maps elements from one cyclic group to elements in another cyclic group. Bilinear maps are often called bilinear pairings because they take a pair of two elements from the source group and map that pair to an element in the target group.
Let G_{b}G_{2} be the source cyclic groups of prime order, p, and Gr be the target cyclic group of same prime order, p, and g,h be the generators of the source group, G_{b} and G_{2} respectively. Let e be a map between Gj and G_{2}, e: Gj xG_{2} —>Gt, it is called a bilinear map if it satisfies the following conditions:
- • V X = g" e G_{t} and У = b^{1}’ e G_{2}: e(g", h^{v}) = e(g, /?)'"' where u,v e Z_{f}. This is called the bilinearity property.
- • e(g, b) is the generator of the target group, Gj, if g, h are the generators of source groups Gj and G_{2} respectively. This property is called non-degeneracy.
- • V X e Gj and У e G_{2}; e(l,m) is efficiently computable.
If e maps every pair to the identity element in Gj, then we say the bilinear map is degenerate, i.e. if there is only first condition then it also allows degenerate maps. Therefore, the second is added to make the bilinear map valid.
3.3.2.1.1 Relation between the source and the target groups in e
Among all the source and the target groups there exists isomorphism, since all of them are cyclic and have the same order. However, they possess different elements and the operation between the elements may also be different which makes them distinct from each other. If G, = G_{2}, i.e. both the source groups are exactly identical, then the associated map is called the symmetric bilinear map and if both are different, then the associated map is called the asymmetric bilinear map. Further, the order of the source and the target groups may also be composite instead of some prime, p. Most of the constructions consider prime order groups, some examples do exist in the literature which consider composite order groups. If the source and the target groups are all equal, then the associated map is called self bilinear map. Such maps do not exist and it is an open problem to build one.
In some existing works, another notation has been seen where the bilinearity property is expressed as e(uX, vY) = instead of e[X", Y' ), where X, Y are the elements of the source groups. This case is seen when the groups are written addidvely, however the multiplicative notation is more popular.
3.3.2.1.2 How the source and target groups are chosen
For the source groups, typically an elliptic curve over some finite field, F_{p} is used. There are different types of pairing, type A, Al, D, E, F and G [19] that result from choosing elliptic curves of different embedding degree. While the target group is generally a finite field.
The Weil [20] and Tate [21, 22] pairing are the only known example of bilinear pairing. The Weil pairing was practically used by Boneh and Franklin [23] in the construction of an identity-based encryption scheme.