# Case Study: The Bilinear Padings And Complexity Assumptions

The first symmetric key schemes for keyword search over encrypted data are proposed in [27]. The authors consider a setting in which the sender of file encrypts each word of a file separately. Goh [15] proposed a method for secure index using Bloom filters and introduced the notion of semantic security against adaptive chosen-keyword attacks. Determining whether a file contains a keyword can be done securely in constant time. In the public key setting, Boneh et al.[5] first proposed public key scheme for keyword search, where anyone can use public key and write to the data stored on remote server, but only authorized recipients with the secret key can search. An efficient implementation of a public key work for keyword search

*…show more content…*

Section 2 gives the preliminaries. Then we introduce the outline of the proposed scheme, notations, semantic security of the SSE-KFF-CKS scheme and construction of SSE-KFF-CKS in Section 3. Section 4 introduces the security analysis. Finally, Section 5 provides brief conclusions. PRELIMINARIES

2.1. The Bilinear Pairings and Complexity Assumptions

We briefly show theoretical background and complexity assumptions that used throughout our paper. Bilinear maps: We say a map e ̂:G_1×G_1→ G_2 is a bilinear map if the following properties hold: G_1and G_2are cyclic groups of the same prime order q and e ̂(g,g) is efficiently computable; For all a,b∈Z_q and g∈G_1, then e ̂(g^a,g^b) = e ̂〖(g,g)〗^ab; e ̂(g,g) is non-degenerate. That is, if g generates G_1 the e ̂(g,g) generates G_2.

The above bilinear map is called symmetric pairings. Decisional Diffie-Hellman (DDH) problem: We say that the decisional Diffie-Hellman (DDH) problem is hard if, for any PPT distinguisher A, the function

|Pr[A(G_1,q,g,g^a,g^b,g^c )=1]-Pr[A(G_1,q,g,g^a,g^b,g^ab )=1]|, is negligible.

2.2. Outline of the Conjunctive Keyword Searchable Encryption [16]

A conjunctive keyword searchable encryption (CKSE) consists of the following four algorithms: KeyGen(1^k): It is run by the senders to initiate the scheme. It takes a security parameter k, and returns a secret key

*…show more content…*

This algorithm takes the security parameter σ as input to create the following parameters: q as a large prime, two groups G_1,G_2 of order q and a bilinear map e ̂:G_1×G_1→ G_2,g is a random generator of G_1, e is random element of Z_q^* and one cryptographic hash Functions H:〖{0,1}〗^*⟶G_1. FilEncrypt: To protect data privacy and undesired accesses, the file collection F should be encrypted before outsourcing them onto remote servers which are not within their trusted domains. To do so, S encrypts each file F_i∈F using a standard symmetric encryption algorithm(AES). Each file F_i comprising of an unique identifier 〖ID〗_i∈〖{0,1}〗^n. To protect the file identifiers 〖ID〗_i, S encrypts this 〖DI〗_i also with AES encryption technique, such technique assurances that if the same file identifier is encrypted multiple times, it will create different ciphertexts but all decrypted to the same value. KeyEncrypt: S extracts the conjunctive keyword W_(F_i ) from each file F_i∈F and encrypts them. To do so, the sender creates m! possible permutations set of these keywords sequence P_(F_i )={〖Pr〗_1,〖Pr〗_2,…,〖Pr〗_m! } and makes each permutation 〖Pr〗_j looks like one keyword using concatenation operation as 〖Pr〗_j={W_1 || W_2 ||...||W_m}, where j = 1,...,m!, then he chooses a random number f∈Z_q^*. Finally the algorithm KeyEncrypt returns C_j for each permutation 〖Pr〗_j as