2.1 Notations and system model

Let D = {d₁, … d_n} be the set of document collection, C = {C₁, … C_n} be the encrypted collection of documents and W = {w₁, …, w_m} be the set of keywords. Let F = {f₁, …, f_n} denote the file identifiers of documents given by f_i = id(C_i). A collection of document D is to be outsourced to the Cloud Service Provider (CSP). The data owner encrypts the document set D to obtain a encrypted document collection C. To enable privacy preserving searching over the encrypted document collection C, a secure encrypted index denoted by γ is built using BuildIndex. The encrypted document collection C, the secure encrypted Index γ are outsourced to the CSP. An authorised Data User (DU) acquires a search token denoted by τ_q generated using SrchToken corresponding to a given query keyword w_q from the Data Owner (DO). The search token τ_q is then sent to the CSP using a standard communication protocol. The CSP searches for the matching documents for the query keyword using Search over the encrypted index γ preserving privacy. The Search algorithm outputs a set of file identifiers relevant to the query denoted by F_q that contain the query keyword. The DO updates the index using Update whenever the document changes or files need to be added/deleted. The overall system working mechanism of the search is shown in Fig 1. We use the notation = to denote a deterministic assignment, ← a probabilistically computed assignment and ←_$ an uniformly sampled assignment.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 1. System model.

https://doi.org/10.1371/journal.pone.0256223.g001

2.2 Security definitions

The construction of the Pindex scheme aims to securely perform computations at the CSP on the encrypted data while preserving privacy and is defined as in [9]:

Definition 1 (Pindex). Pindex is a dynamic searchable encryption scheme consisting of a tuple {KGen, Enc₁, Dec₁, Enc₂, Dec₂, BuildIndex, SrchToken, Search, UpdToken, Update} of ten algorithms such that:

1. K ← KGen(1^λ) is a probabilistic polynomial time algorithm that outputs a secret key K ← {pk, sk, k} when given as input a security parameter 1^λ
2. c ← Enc₁(k, f) is a CPA-secure deterministic polynomial time algorithm that outputs a sequence of encrypted ciphertexts c when given as input a secret key k and a file f.
3. f = Dec₁(k, c) is a deterministic polynomial time algorithm that outputs a file f when given as input a secret key k and a ciphertext c.
4. c ← Enc₂(pk, m, r) is a CPA-secure probabilistic polynomial time additive homomorphic algorithm that outputs an encrypted ciphertext c when given as input a secret key pk, a message m and randomness r.
5. m = Dec₂(sk, c) is a deterministic polynomial time algorithm that outputs m when given as input a secret key sk and a ciphertext c.
6. (γ, Γ) ← BuildIndex(K, δ, V, D, Enc₂) is a probabilistic polynomial time algorithm that outputs a encrypted index γ and a parameter hash table Γ when given as input a secret K, vector V, primitive Enc₂, document collection D and a index δ.
7. τ_q ← SrchToken(pk, w_q, Γ) is a probabilistic polynomial time algorithm that outputs a search token τ_q when given as input a secret key pk, query keyword w_q and a parameter hash table Γ.
8. F_q ← Search(γ, τ_q) is a deterministic polynomial time algorithm that outputs a set of identifiers F_q ⊆ D when given as input an encrypted index γ and a search token τ_q.
9. τ_u ← UpdToken(pk, f_i, u, w_u) is a probabilistic polynomial time algorithm. Given a secret key K, update keyword w_u and a file f_i as input, the algorithm outputs an update token τ_u for the update type u ∈ {add, delete}.
10. γ′ ← Update(γ, τ_u) is a deterministic polynomial time algorithm that outputs an updated encrypted index γ′ given an encrypted index γ and an update token τ_u.

A scheme as defined above is secure when it is designed based on the real/ideal security paradigm. The paradigm requires defining correctness and privacy. The correctness captures the notion that the specified polynomial time algorithms in Definition 1 outputs correctly and it is given as:

Definition 2 (Correctness). Let π be a dynamic searchable encryption scheme as given in Definition 1. Such π is said to be correct if , ∀K: K ← KGen(1^λ), ∀(δ, f), ∀γ: γ ← BuildIndex(K, δ, V, D, Enc₂), ∀c: c ← Enc₁(k, f) and for all update operations of Update(γ, τ_u), where τ_u is the update token obtained by ∀(f, τ_u): τ_u ← UpdToken(pk, f_i, w) and all u ∈ {add, delete}, ∀(w, τ_q: τ_q ← SrchToken(pk, w, Γ), ∀F_q: F_q ← Search(γ, τ_q), the plaintext f_w = {Dec₁(k, c_i):i ∈ F_q} are all plaintexts in f containing keyword w.

Most of the dynamic searchable encryption schemes leak information which could be exploited to launch attacks such as file injection attacks to recover the encryption key. For example, information leak such as file identifiers returned for a respective search or update query cannot be prevented. The leakage function captures the notion of allowable leakages in a dynamic searchable encryption defined as in [9]:

Definition 3 (Leakage). The leakage functions are defined as follows:

1. Search Pattern : It is defined by a one dimensional binary matrix of length m × n. Given a search keyword w at t, if the search at time i ≤ t is for the keyword w then it is marked as 1 at i and 0 otherwise.
2. Access Pattern Δ(δ, f, w, t): It is defined as the set of identifiers f_w at time t given a search query for keyword w at time t.
3. : The function outputs the number of keywords m, the number of files n, the identifiers i of the file and the size of each file when given the index δ and set of file identifiers.
4. : The function outputs and Δ(δ, f, w, t) for a search query at time t, given the index δ, set of files f and keyword w as input.

The definition of privacy or security captures the notion that the view of each party can be separately simulated given the leakage function and it is defined as:

Definition 4 (Security). Let π be a dynamic searchable encryption scheme as defined in Definition 1. Let be a stateful adversary, Sim be a stateful simulator and are stateful leakage algorithms in the following experiments:

1. : The challenger runs K ← KGen. The adversary outputs and receives (γ, Γ) ← BuildIndex(K, δ, V, D, Enc₁) from . Each time the adversary computes q ∈ {w, f_i} and makes polynomial number of adaptive queries. obtains from a search token τ_q ← SrchToken(pk, w, Γ) whenever it wants to perform a search query q = w. If wants to make a update query q = f_i it receives a update token τ_u ← UpdToken(pk, f_i, w_u) from . returns an output bit b at the end of the experiment.
2. : Sim outputs (γ, c) to when given (δ, f) and . then can make polynomial number of adaptive queries q ∈ {w, f_i}. makes a search query q = w then the simulator is given and when q is update query, the Sim is given a new including the adaptive query history by . Also, the Sim returns a token τ to appropriately. then returns an output bit b at the end of the experiment.

The scheme π is said to be –secure against adaptive dynamic chosen-keyword attacks if for all PPT adversaries , there exists a PPT simulator Sim such that (1)

A dynamic searchable scheme is considered secure if no information is revealed during execution of all its operations. However, designing such schemes which do not leak any information is a challenge. For example, when a search or update is performed for the keyword w, the CSP can correlate the file identifiers with it’s query and learn about the outsourced data. Therefore, there is a need for stronger security guarantees for dynamic searchable schemes.

Definition 5 (Forward private). A dynamic searchable encryption scheme which is -adaptively secure is said to be forward private if the following holds: (2) where is the update leakage function, {f_i, μ_i} is the set of document-number of keywords updated pair, f_i is the document updated, μ_i is the number of keywords updated on respective f_i and a stateless function.

The forward private definition 5 states that the server should be able to learn only about the file identifier(s), size of file(s) and number of keywords contained in file(s) after observing searches before and after a dynamic update operation op ∈ {Add, Delete} over encrypted index is performed.

2.3 Homomorphic and orthogonality

The design of dynamic searchable schemes satisfying definitions 4 and 5 more often requires the use of encryption mechanisms called homomorphic cryptosystems as a building block.

Definition 6 (Homomorphic). A public key encryption scheme E = (KGen, Enc, Dec, M, C) is said to be homomorphic if it holds that Dec(sk, c₁ ⋄ c₂) = m₁ ⋄ m₂ for all m₁, m₂ ∈ M and c₁, c₂ ∈ C with m₁ = Dec(sk, c₁) and m₂ = Dec(sk, c₂) such that for all c obtained from Enc(pk, m), c belongs to C.

The proposed Pindex uses Paillier cryptosystem to instantiate the encryption which exhibits homomorphic addition property. The group operation ⋄ for Paillier cryptosystem has homomorphic property such that Dec(sk, c₁ ⋄ c₂) = m₁ + m₂ [16]. Let V = v₁, v₂ …, v_|W| be a matrix of mutually orthogonal vectors where v_i is the i^th row vector and |W| is the number of keywords in the keyword collection W. A square n × n matrix V with elements ±1 that satisfies V × V^T = nI_n is called a Hadamard matrix of order n [17, 18]. Such matrices make cross correlation values to be zero and this property is used in the design of the proposed search and update mechanism of Pindex.

3.1 Multi-linked hash map construction

The two dimensional matrix M_mn whose elements are stored in a multi-linked hash map δ, where each element {m_ij: m_ij = [next, prev], m_ij ∈ M_mn,1 ≤ i ≤ m,1 ≤ j ≤ n} has link to the next non-empty element in the respective row i and column j. The row links are implemented by orthogonal vectors and respective column links using pointers as shown in Fig 2. The hash table value δ(i) is orthogonally linked row values for all 1 ≤ i ≤ m as given below: (3)

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 2. Multi-linked hash map δ.

https://doi.org/10.1371/journal.pone.0256223.g002

Eq 3 shows that each value is a sum of inner product of the orthogonal vector v_j and a pointer to the next non-empty value in the column j. Each v_j represents a column and all v_j’s are mutually orthogonal 4. (4)

Hence, assuming y such that y = j, (5) where m_ij by definition is a pointer to the next non-empty element in the column j and <.,.> denotes vector inner product. Therefore, all the non-zero elements in the column j can be retrieved using the recursive function: (6)

The hash table value δ can be used as an index for retrieving documents containing a given keyword. Let the rows and columns in matrix M represent documents and keywords respectively. Each element in a column j is a pointer to next document containing the keyword w_j. Each row i is encoded as an orthogonal sum of product of keyword vector v_j and the next document f_i containing keyword w_j and stored in a keyword multi-linked hash map as δ(f_i). Each element m_ij = [f_next, f_prev] represents the next and previous file of f_i containing the keyword w_j and an empty value m_ij = ∅ represents that w_j ∉ f_i. Therefore, using Eq 6 set of all documents F_q containing query keyword w_q can be retrieved in F_q ⊆ F in sub-linear time as for all practical queries |F_q| ⋘ |F|. The multi-linked hash map data structure is designed as described above such that it supports addition of new documents which includes encoding a row, adding encoded value and updating either the last or first row pointers accordingly. The multi-linked hash map data structure design improves search to sub-linear time and supports parallel execution of search and updates.

3.2 Algorithm K ← KGen(1^λ)

It is a probabilistic polynomial time algorithm which generates the secret parameters used for building index and encryption. The Pindex algorithm uses Paillier Cryptosystem for building the index and generation of search and update tokens. The key (pk, sk) generation setup is described in [18] where pk denotes the public key and sk denotes the private key of Paillier cryptosystem. The KGen also generates a secret key k to be used by Enc₁ for encrypting the document collection D. The design choice for Enc₁ is the CPA-secure AES while the design choice for Enc₂ is the CPA-secure Paillier cryptosystem which also exhibits additive homomorphic properties.

3.3 Algorithm c ← Enc₂(K, m, r)

It is a probabilistic algorithm, given a message m ∈ P and a public key pk = (n, g), Enc₂(pk, m, r) returns the ciphertext c = g^mrⁿ mod n², where given r is a random value chosen such that .

3.4 Algorithm m = Dec₂(sk, c)

It is a probabilistic algorithm, given a ciphertext c ∈ C and a private key sk = (p, q, λ), Dec₂(sk, c) returns the message m. (7)

3.5 Algorithm (γ, Γ) ← BuildIndex(K, δ, V, D, Enc₂)

BuildIndex algorithm constructed by the data owner takes as input five parameters namely the document set F = {f₁, f₂,…, f_|D|}, keyword set W = {w₁, w₂,…w_|W|}, a pre-built multi-linked hash map δ as described in section 3.1 for F, mutually orthogonal vector V and the key K as input. The algorithm outputs multi-linked hash map index γ and keyword parameter hash table Γ. The algorithm computes:

1. For each row i or file f_i in δ:
    For each column j or word w_j in f_i:
     if m_ij ≠ ∅ and Γ(w_j) = ∅ then compute Γ(w_j) = (v ←_$ V_w, r ←_$ Z_n)
      Compute s ← Enc₂(pk, w_j, r)
      Compute γ(0) = γ(0) + v.s.f and γ(f_i) = γ(f_i) + v.s.⊥
     if m_ij ≠ ∅ and Γ(w_j) ≠ ∅ then retrieve (v, r) = Γ(w_j)
      Compute s ← Enc₂(pk, w_j, r)
      if f_next ≠ ∅ then compute γ(f_i) = γ(f_i) + v.s.f_next otherwise γ(f_i) = γ(f_i) + v.s.⊥
    Compute v_r ←_$ V_r and r′ ←_$ Z_m
    Compute γ(f_i) = γ(f_i) + v_r.r′
2. Return (γ, Γ)
3. Send γ to CSP and Γ is kept secret at the DO

The pictorial representation of index structure is given in Fig 3. The encrypted index (γ, Γ) can be observed to be designed such that the link can be traversed vertical through the pointers and traversed horizontal through the orthogonal property without leaking critical information.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 3. Index structure.

https://doi.org/10.1371/journal.pone.0256223.g003

3.6 Algorithm τ_s ← SrchToken(w_q, pk, V)

The SrchToken algorithm is computed by the Data Owner. It takes a query keyword w_q ∈ W, key pk, set of mutually orthogonal vectors V as input and outputs a search token τ_q. The algorithm is given below:

1. Get the keyword secret (v, r) ← Γ(w_q) from the keyword parameter hash table Γ and compute such that rr⁻¹ ≡ 1 mod n²
2. Compute s⁻¹ ← Enc₂(pk, −w_q, r⁻¹) and returns to DU the search token τ_q by computing: (8) where and v′ ←_$ V_r

The trapdoor τ_q is designed to contain the encrypted keyword parameters embedded with the corresponding orthogonal vector v and random v′.r′ are added at each instance to make the token appear indistinguishable even when the same query is repeated.

3.7 Algorithm F_q ← Search(γ, τ_q)

The Search algorithm is computed at CSP and it takes as input the encrypted index γ, search token τ_q, key pk and outputs F_q = {f₁, f₂,‥f_n}. F_q is the set of document identifiers such that w_q satisfies w_q ∈ W and ⊥ otherwise, where ⊥ denotes null. The search algorithm is given below:

1. Compute 〈γ(0), τ_q〉 to obtain the first file pointer f_q = f₁ of document containing the keyword w_q.
2. If f_q = ∅ then there are no documents matching the query keyword w_q or the search token is invalid. The algorithm terminates returning ⊥.
3. Otherwise, obtain all f_q computing recursively as given below with base condition f_q = f₁ until f_q = ⊥ (9)
4. Return all file identifiers {f₁, …, f_q, …, |F_q|} obtained.

Thus, it can be observed that the design of the search algorithm is simple and dependent on the search token design. Since, the search token is designed to be created with the orthogonally embedded encrypted keyword parameters (v.s⁻¹) and the index contains (v, s), a inner product of the two will result in retrieving the corresponding document identifiers. The proof of correctness for which is presented in section 4.

3.8 Algorithm τ_q ← UpdToken(pk, f, u, w)

The UpdToken probabilistic algorithm is computed by the DO. The algorithm returns an update token to the CSP for securely updating the index. We define a header node to be the node pointed by γ(0) or the row when i = 1 in δ, a terminal node to be the last file containing ⊥ for a w in δ and any other node as intermediate nodes containing a keyword w. The algorithm computes:

1. When the update operation is DeleteKeyword w ∈ W from document f then compute:
   1. Get (v, r) ← Γ(w), compute s ← Enc₂(pk, w, r)
   2. When f is the header node, compute τ₁ ← v.s.f_next, τ₂ ← v.s.f and return τ ← (τ₁, τ₂, f₁ = 0, f₂ = f)
   3. When f is the terminal node, compute τ₁ ← v.s.⊥, τ₂ ← v.s.f and return τ ← (τ₁, τ₂, f₁ = f_prev, f₂ = f)
   4. When f is an intermediate node, determine f_next, f_prev, compute τ₁ ← v.s.f_next, τ₂ ← v.s.f and return τ_u ← (τ₁, τ₂, f₁ = f_prev, f₂ = f)
2. When the update operation is DeleteFile for a document f then compute:
   1. Get (v, r) ← Γ(w), compute s ← Enc₂(pk, w, r),
   2. When f is the header node, compute and return τ ← (τ₁, τ₂, f₁, f₂ = f)
   3. When f is the terminal node, compute and return τ ← (τ₁, τ₂, f₁, f₂ = f)
   4. When f is an intermediate node, determine f_next, f_prev, compute and return τ_u ← (τ₁, τ₂, f₁, f₂ = f)
3. When the update operation is AddKeyword w ∈ W to document f then compute:
   1. Get , compute s ← Enc₂(pk, w, r)
   2. When f is the header node, compute τ₁ ← v.s.f, τ₂ ← v.s.f_next and return τ ← (τ₁, τ₂, f₁ = 0, f₂ = f)
   3. When f is the terminal node, compute τ₁ ← v.s.f, τ₂ ← v.s.⊥ and return τ ← (τ₁, τ₂, f₁ = f_prev, f₂ = f)
   4. When f is an intermediate node, determine f_next, f_prev in respect of f, compute τ₁ ← v.s.f, τ₂ ← v.s.f_next and return τ_u ← (τ₁, τ₂, f₁ = f_prev, f₂ = f)
4. When the update operation is AddFile for a document f then compute:
   1. Get
   2. Compute s ← Enc₂(pk, w, r)
   3. Add f as the header node by computing and return τ_u = (τ₁, τ₂, f₁ = 0, f₂ = f)

3.9 Algorithm γ′ ← Update(γ, τ_u, f₁, f₂)

This algorithm takes an index γ, an update token τ_u = (τ₁, τ₂) and the public key pk as input and updates the encrypted index. The updated index γ′ is computed by Update algorithm is given below:

1. When the update operation u ∈ {DeleteKeyword, DeleteFile}
2. When the update operation u ∈ {AddKeyword, AddFile}

The rationale behind the design of Update described above and depicted in Fig 4 is based on exploiting the orthogonal property of V and homomorphic property of s used in creating the index (γ, Γ). This enables addition and deletion over encrypted index such that the tokens are indistinguishable guaranteed by CPA-security.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 4. Update working.

https://doi.org/10.1371/journal.pone.0256223.g004

5.1 Multi-link index

Building the multi-linked index is a one-time process carried out by the data owner. The multi-linked dynamic searchable index γ can be constructed using two steps. First, encrypting the keyword w using Paillier cryptosystem if it belongs to document f and secondly computing the encrypted index γ which is a multi-link between the document f and keywords w_i ∈ W. Therefore the time cost of index generation is proportional to the number of files and number of keywords contained in each file. It can be observed from Fig 5a that the time cost for building the index with varying number of documents of the proposed system performs relatively better than MRSE. This is due to use of relatively small matrix dimensions in the design and computationally less intensive operations like scalar multiplications (|W| operations) and vector additions (|W| + 1 operations).

5.2 Search token generation

The search token τ_q is constructed for the keywords in the query. The process involves retrieving the pair (v, r) from the parameter hash table Γ and encrypting the query keyword w_q. The time cost for search token depends on the number of query keywords. Fig 5b shows the time cost for generating the search token in logarithmic scale for document size n = |D| = 1000 and varying the size of the query keyword. It is observed that Pindex performance is better than MRSE. This is because our scheme use less computationally intensive operations and the number of operations involved in building a trapdoor is minimum. The operations include two scalar multiplications, one vector addition for indistinguishability and one lookup.

5.3 Search

Search operation executed by the cloud server consists of multiplying the search token τ_q with the encrypted index γ. If w_q ∈ W, the first pointer is computed and recursively the multi linked index is traversed until f_q = ⊥. For a multi-keyword search with |w_q| keywords in a query q and run on p processors parallel which returned |F_q| files then time complexity would be . In MRSE similarity scores for the document set is computed and therefore the time complexity is . The time cost for varying the number of documents for m = |W| = 1000 is shown in Fig 5c and 5d. Search time of Pindex is relatively better than MRSE. Also, it can be observed that as the number of keywords per query is increased, the corresponding increase in time of query to be sub-linear for the proposed design. It is due to optimal number of operations used in the design of search operation which involves just one vector inner product.

5.4 Update

The update (add and delete) of both keywords and document involves adding the update token τ₁ and deleting τ₂ from f_prev. The worst case scenario for update delete file operation is when the number of f_prev equals the number of keywords contained in the file to be deleted. Updates are not compared as MRSE does not support dynamic index, the index has to be rebuilt for updates and the results are shown in Fig 5e and 5f. The time cost for update i.e to add/ delete a keyword is and to add/delete a file is . The proposed method supports dynamic updates unlike MRSE and it can be observed that dynamic updates comprises of building update trapdoor and executing update algorithm. The time to build update trapdoor is significantly less due to the same reasoning as that of building trapdoor and execution of update algorithm involves only vector additions and deletions as given in section 3.

6.1 Searchable encryption

The searchable encryption schemes are primarily classified into Searchable Symmetric Encryption and Public Key Encryption with Keyword Search [2] depending upon the type of encryption primitive used and notion of provable security. The searchable encryption systems is further classified based on the type of search operation into keyword based and semantic based searchable encryption system [23]. The keyword based searchable encryption system uses either specially designed secure encrypted indexes to support search operations over encrypted data or sequential scanning of encrypted documents to support search [4]. The keyword based searchable encryption system are exact search keyword based while the semantic keyword search matches even closest query keywords. The proposed design is based on keyword based searchable encryption schemes using secure encrypted index. The first practical solution to symmetric searchable encryption was proposed by Song et al. [3]. Followed by a number of searchable encryption schemes especially with secure index construction, improved efficiency, security definitions and formalizations [4, 5, 8, 9, 24–26].

6.2 Secure index

To improve performance and decrease the search complexity, clients build keyword-based indexes and outsource it to the cloud. Searchable encryption schemes in literature use a forward, inverted or tree-based index [4, 24, 27, 28]. However, the scalability of the index based schemes can be achieved by either rebuilding the index or by using expensive techniques [5]. The index contains information such as document identifiers, document length, number of keywords in the file. The adversary should not be able to determine the query keyword using statistical analysis. Therefore, the index must not leak information which could aide honest-but-curious CSP to link tokens, keywords and document identifiers. The indexes and the tokens or trapdoors are inherently linked. Deterministic trapdoors are known to leak information therefore probabilistic trapdoors are used. Goh [4] uses forward index using bloom filters per document. The search complexity is proportional to the number of files and bloom filters have an inherent problem of false positives. Chang and Mitzenmacher [24] use prebuilt dictionary of distinct keywords to build the forward index. The search complexity is proportional to the number of files. Inverted index or index per keyword was introduced by [5] and thus reduced the search time to a sub-linear scheme with optimal search time. [26] proposed a scheme based on inverted index using hash tables.

6.3 Dynamic searchable encryption

Dynamism is a main requirement for any searchable encryption scheme to be practical. The first dynamic searchable encryption was proposed by Kamara et al. [8] using inverted index and dynamic addition and deletion of documents. The update complexity is linear to the updated document/keyword pair but the update leaks some information about the documents. Kamara and Pamamanthou [9] proposed a red-black tree index based on an encrypted linked-list multi-map. To insert a new keyword, they added as a new entry to the right list and deletion using a dual representation of the index but update leaks information. Cash et al. [10] proposed a dynamic index using a separate update database to add and delete tuples stored in the revocation list. However, the update is inefficient and leaks significant information. Naveed et al. [11] presented a dynamic searchable encryption with blind storage. Instead of encrypting the index, the stored blocks are scattered using hashing. This scheme leaks the information while adding keyword. Other dynamic searchable encryption schemes are [7, 14, 29–31].

6.4 Forward privacy

There is a trade-off between practicality and security as most of the dynamic searchable encryption schemes leak significant amount of information about the document. Attacker can leverage this leakage to reveal information on the client’s queries. Deterministic encryption schemes leak information regarding size, search, access patterns from the repetition of the queried keyword. File injection attack on dynamic searchable encryption by Zhang et al. [13] triggered much attention on forward privacy schemes. By injecting few carefully selected files, the adversary can recover keywords queried in the past from the information leaked from the search token. Thus, the prior search token needs to be invalidated to achieve forward security. Therefore, a stronger property called forward privacy and an informal definition was introduced by Stefanov et al. [12] based on Oblivious RAM. However, the scheme leads to a search cost and update cost. Existing schemes that achieve forward privacy are generally based on trapdoor permutation or using pseudorandom functions. Bost proposed the first formal definition of forward security and a trapdoor permutation based scheme Sophos [32]. Later proposed Diana [15] a constrained PRF based scheme. A dual dictionary Dual [33] was proposed that simultaneously uses both forward with inverted index and achieves forward privacy using fresh keys. To realize forward security, a symmetric punctured encryption Janus ++ [34] was proposed. Etemad et al. [35] achieve forward privacy by replacing the keys revealed to the server. Sun et al. Aura [36] use a non-interative DSSE using bloom filters and multi-puncturable PRF. Wei et al. [37] proposed an index structure with keyed block chain. Khons [38] uses inverted index and achieves weak forward security by exploitation hidden pointer technique.