## 4 Our Construction
### Scheme Construction
Identical to the previous evaluation with the synthetic dataset, we query the top 20 most frequent keywords and calculate the average rate of document retrieval after repeating the experiment 20 times. Figure 4(b) shows the retrieval rate when querying the \(i\)th most frequent keywords. In the experiment, the 3 rd and 2 nd most frequent keywords show the highest and the lowest retrieval rates of 99.49% and 98.11%, respectively. On average, the proposed scheme retrieves 98.96% of the matching documents, showing 1.04% utility loss, which is almost the same as the experimental result with the synthetic dataset. **Discussion. ** The utility loss is an inevitable trade-off for providing higher security without degrading the efficiency of the proposed scheme, as many of the other schemes adopt a differential privacy technique to obfuscate access and search patterns [24; 25]. Even if the utility loss rate is very low (which is approximately 1% in the proposed scheme), the possibility of utility loss should affect the number of documents retrievable by the client. A simple solution to mitigate this problem is to add redundancy in the stored data

Figure 4: Search latency. (**a**) Search latency depending on \(|FD|\). (**b**) Search latency comparison of different schemes. or to send redundant queries for a single search. For example, [PERSON] et al. scheme [24] adopted erasure code to add redundancy to the stored data. On retrieval, the encoded message can be reconstructed into its original one even though some parts of the message are lost. Therefore, the erasure coding method may be applied to our design scheme to eliminate utility loss. However, how to minimize such additional overheads further without incurring any utility loss while guaranteeing Type-II backward privacy is a challenging and open problem in the literature. ## 7 Related Work

Since the first proposal in 2000 [26], a number of searchable symmetric encryption (SSE) schemes have been proposed for formally defining the security model [3], improving efficiency [1,27], and supporting expressive queries [28,29]. Recently, several works have been introduced on how access pattern and search pattern leakages can be exploited by an adversary to break the security of SSE [17,30]. [PERSON] et al. [30] exploited the search pattern leakages to recover the plaintext of the query or reconstruct the client's indexed documents. [PERSON] et al. [17] introduced a file injection attack on SSE schemes that exploits access patterns on file identifiers to identify what specific file identifiers correspond to the maliciously injected file. Another important research area in SSE is to support dynamic operations in SSE, which enables a client to perform keyword searches as well as update operations on the encrypted documents, known as dynamic symmetric searchable encryption (DSSE) [1,27]. [PERSON] et al. [2] and [PERSON] et al. [4,5] first introduced two fundamental security requirements for DSSE, that is, forward and backward privacy. Recently, [PERSON] et al. [14] introduced a non-interactive forward and backward private DSSE method by constructing revocable encryption. Even though it could reduce the information leakage by making the deletions oblivious to the server, it allows additional information leakage such as the number of deleted documents and candidate timestamps of deletion updates, which can be further exploited by an adversary to violate the backward privacy via obtaining the deletion history. In addition, [PERSON] et al. [11] proposed a Type-II backward private scheme by leveraging Intel SGX enclave as a server-side proxy and constructed a more efficient scheme than [PERSON] et al. Bunker-B [8]. Despite the improvement of its efficiency, the [PERSON] et al. [11] scheme allows more information leakages than Bunker-B, which can be abused to violate its backward privacy. Therefore, accomplishing high efficiency while minimizing exploitable information leakage is still a challenging and open problem in DSSE literature.