Efficient backward private searchable encryption

Dynamic Searchable Symmetric Encryption (DSSE), apart from providing support for search operation, allows a client to perform update operations on outsourced database efficiently. Two security properties, viz., forward privacy and backward privacy are desirable from a DSSE scheme. The former captures that the newly updated entries cannot be related to previous search queries and the latter ensures that search queries should not leak matching entries after they have been deleted. These security properties are formalized in terms of the information leakage that can be incurred by the respective constructions. Existing backward private constructions either have a non-optimal communication overhead or they make use of heavy cryptographic primitives. Our main contribution consists of two efficient backward private schemes Π BP and Π WBP that aim to achieve practical efficiency by using light weight symmetric cryptographic components only. In the process, we also revisit the existing definitions of information leakage for backward privacy [Bost et al. (In ACM CCS (2017) 1465–1482 ACM Press)] and propose a relaxed formulation. Π BP is the first construction to achieve backward privacy in the general setting with optimal communication complexity. Our second construction, Π WBP , is the first single round-trip scheme achieving backward privacy in a restricted setting with optimal communication complexity using light weight symmetric cryptographic primitives. The prototype implementations of our schemes depict the practicability of the proposed constructions and indicate that the cost of achieving backward privacy over forward privacy is substantially small. The performance results also show that the proposed constructions outperform the currently most efficient scheme achieving backward privacy.

Keywords: Dynamic Searchable Symmetric Encryption; backward privacy; forward privacy

Due to a variety of crucial benefits, enterprises outsource their data to cloud resident storage. If the outsourced data is stored as plaintext on remote servers then it may be intercepted by adversaries. Hence, data is stored in encrypted form on remote servers. However, if the client has to decrypt the whole data in order to get results for a search query, it defeats the purpose of outsourcing data. Generic tools such as fully homomorphic encryption [[20]] or oblivious RAM [[23], [40]] can be considered to construct protocols that leak almost no information to the server. But as of now, these tools are costly for large databases and hence, are impractical.

A practical solution to this problem is Searchable Symmetric Encryption ( $\mathsf{SSE}$ ) [[10], [13], [37]] that trades efficiency for security. Dynamic Searchable Symmetric Encryption ( $\mathsf{DSSE}$ ) [[9], [28], [34]] adds a vital feature to static $\mathsf{SSE}$ schemes, i.e., the ability for the client to efficiently perform update operations remotely on the outsourced database with the guarantee that minimal information is leaked to the server in the process. These constructions of $\mathrm{(}\mathsf{D}\mathrm{)}\mathsf{SSE}$ that aim to achieve an acceptable balance between security and performance, explicitly describe the leakage profile and formally prove that the information leaked from the scheme is bounded by the leakage profile.

Simultaneously with the works on constructing $\mathsf{SSE}$ schemes with improved efficiency, security and expressiveness of queries [[10], [17], [27]], there is another line of work that shows the real-world consequences of these leakages [[1], [8], [44]]. Zhang et al. [[44]] through file injection attack showed that it is possible to reveal the contents of past search queries of $\mathsf{DSSE}$ schemes with a few injection of documents and Abdelraheem et al. [[1]] showed that the consequences of this attack is even more devastating in the case of relational databases.

Because of the file injection attack, forward privacy has garnered significant interest in the research community. The notion of forward privacy was introduced in [[39]], while it was first formalized in [[4]]. In hindsight, the first $\mathsf{DSSE}$ scheme that satisfied the notion of forward privacy was proposed in 2005 [[12]]. Along with forward privacy, Stefanov et al. [[39]] asserted that backward privacy should also be satisfied by a $\mathsf{DSSE}$ scheme. Informally, backward privacy states that search queries should not leak matching entries after they have been deleted. The notion of backward privacy was first formalized by Bost at el. [[6]].

Kamara et al. [[28]] proposed the first sublinear (in the size of the database) $\mathsf{DSSE}$ scheme. Forward private scheme $\mathrm{\Sigma }\mathit{o}\mathit{\varphi }\mathit{o}\mathit{\zeta }$ [[4]] achieves optimal communication complexity (linear in the size of result set) but it makes use of asymmetric cryptographic primitives and does not support parallel processing. A $\mathsf{GGM}\text{-}\mathsf{PRF}$ [[22]] based forward private $\mathsf{DSSE}$ scheme $\mathsf{Diana}$ was proposed in [[6]]. $\mathsf{Diana}$ makes use of symmetric cryptographic primitives only and supports parallel processing but doesn't have optimal computational and communication complexity. Asymptotically optimal forward private $\mathsf{DSSE}$ schemes that make use of symmetric cryptographic primitives only and support parallelism were proposed in [[16], [30], [38]]. Further, $\mathsf{FASTIO}$ scheme [[38]] ensures a reasonable locality [[9]], a measure of I/O efficiency.

The notion of backward privacy was first formally described in [[6]], through three different definitions, in the ascending order in terms of information leakage, called respectively $\mathtt{BPIP}$ , $\mathtt{BPUP}$ and $\mathtt{WBP}$ . Bost et al. [[6]] proposed a generic way to achieve backward privacy from any forward private $\mathsf{DSSE}$ scheme. However, the communication complexity of the derived backward private scheme isn't optimal. In [[6]], a backward private scheme ${\mathsf{Diana}}_{\mathsf{del}}$ based on constrained pseudo-random function ( $\mathsf{CPRF}$ ) [[3], [7], [29]] and a backward private $\mathsf{Janus}$ framework based on a puncturable encryption scheme with a particular incremental update property [[26]], were also proposed. The communication and computational complexity of search and update protocols of ${\mathsf{Diana}}_{\mathsf{del}}$ are not optimal. The search protocol in $\mathsf{Janus}$ is single-roundtrip and has an optimal communication complexity. However, the computational complexity of search protocol is $\mathit{O}\mathrm{(}{\mathit{n}}_{\mathit{w}}·{\mathit{d}}_{\mathit{w}}\mathrm{)}$ , where ${\mathit{n}}_{\mathit{w}}$ and ${\mathit{d}}_{\mathit{w}}$ respectively denote the number of documents matching keyword w and delete operations performed on keyword w. As acknowledged in [[6]], with just a few hundred deletions per keyword, $\mathsf{Janus}$ will not be practical because of both computational and storage overhead reasons. Further, [[6]] has imposed the following restriction on ${\mathsf{Diana}}_{\mathsf{del}}$ and $\mathsf{Janus}$ : reinsertion of document-keyword pairs that were previously deleted is not allowed. We refer to this constraint as reinsertion restriction in the rest of our paper.

Very recently, there appeared two works on backward private $\mathsf{DSSE}$ [[21], [41]]. Chamani et al. [[21]] proposed a practically efficient $\mathtt{BPUP}$ -secure scheme called $\mathsf{Mitra}$ . Further, by handling delete queries efficiently in this scheme resulted in the most efficient backward private scheme until now, i.e., ${\mathsf{Mitra}}^{\ast }$ . They also proposed two other backward private schemes $\mathsf{Orion}$ and $\mathsf{Horus}$ that achieve quasi-optimal (linear in ${\mathit{n}}_{\mathit{w}}$ upto a logarithmic factor) search computation complexity but make use of Path ORAM [[40]] and as a result are impractical for large databases [[33]]. Sun et al. [[41]] proposed a symmetric puncturable encryption ( $\mathsf{SPE}$ ) scheme and instantiated the $\mathsf{Janus}$ framework with the proposed $\mathsf{SPE}$ scheme. We provide a comprehensive comparative analysis of the performance and security of these schemes vis à vis our proposed schemes in Section 4.4 and 5.

We start with revisiting the notion of information leakage in the context of backward privacy. Our investigation suggests that Weak Backward Privacy ( $\mathtt{WBP}$ ) notion proposed by Bost et al. [[6]] should only be used to argue backward privacy in reinsertion restriction setting. The other two existing notions of information leakage $\mathtt{BPIP}$ and $\mathtt{BPUP}$ are strong in the sense that it seems difficult to obtain a DSSE scheme satisfying these notions with optimal communication complexity. Therefore, like $\mathtt{WBP}$ one may need to relax these stronger notions a bit but unlike $\mathtt{WBP}$ one needs to ensure that the notion of backward privacy is not violated in the general setting. To this end we formalize a relaxed notion of information leakage, $\mathtt{BPLP}$ .

Our main contribution consists of two backward private schemes ${\mathrm{\Pi }}_{\mathsf{BP}}$ and ${\mathrm{\Pi }}_{\mathsf{WBP}}$ that are $\mathtt{BPLP}$ and $\mathtt{WBP}$ secure respectively. We start with a simple forward private scheme ${\mathrm{\Pi }}_{\mathsf{FP}}$ , that serves as a building block for our backward private schemes. Currently, ${\mathsf{Mitra}}^{\ast }$ [[21]] is the most suitable backward private candidate for adoption in practice as it makes use of only light weight symmetric components and has low leakage level. However, one limitation of ${\mathsf{Mitra}}^{\ast }$ is that the communication complexity isn't optimal. We address this issue in our main construction ${\mathrm{\Pi }}_{\mathsf{BP}}$ . ${\mathrm{\Pi }}_{\mathsf{BP}}$ makes use of tags generated using a pseudo random permutation ( $\mathsf{PRP}$ ) which ensures that only the tags corresponding to the set of documents currently matching the keyword w are returned to the client. Thus, ${\mathrm{\Pi }}_{\mathsf{BP}}$ avoids unnecessary communication overhead, while at the same time ensuring that any information violating the notion of backward privacy is not leaked to the server. To the best of our knowledge, ${\mathrm{\Pi }}_{\mathsf{BP}}$ is the first practical backward private scheme that has optimal update and search communication complexity and uses symmetric cryptographic primitives only. Further, ${\mathrm{\Pi }}_{\mathsf{BP}}$ is easily parallelizable, provides reasonable locality and allows reinsertion of document-keyword pair. With a simple modification in ${\mathrm{\Pi }}_{\mathsf{BP}}$ , we construct a single roundtrip weak backward private scheme ${\mathrm{\Pi }}_{\mathsf{WBP}}$ that improves upon the concrete communication overhead in Search protocol by more than 50%. Both the proposed constructions are forward private as well. A comparison of our schemes with some prior works [[6], [21], [41]] is provided in Table 1.

Table 1 Comparison of backward private schemes ${\mathrm{\Pi }}_{\mathsf{BP}}$ and ${\mathrm{\Pi }}_{\mathsf{WBP}}$ with some prior works

All the constructions are also forward private. The client storage for all the constructions is

$\mathit{O}\mathrm{(}\mathit{m}log\mathrm{(}\mathit{n}\mathrm{)}\mathrm{)}$

except

$\mathsf{Orion}$

, where the corresponding complexity is

$\mathit{O}\mathrm{(}1\mathrm{)}$

. See Table 2 for the notations used. Generally,

${\mathit{o}}_{\mathit{w}}^{\prime }\mathrm{<}{\mathit{n}}_{\mathit{w}}·{\mathit{d}}_{\mathit{w}}$

, as the former has an additive factor whereas the latter has a multiplicative factor.

${\mathrm{\Pi }}_{\mathsf{FP}}$ is the most efficient forward private scheme in literature. Our implementation results show that the performance of ${\mathrm{\Pi }}_{\mathsf{WBP}}$ and ${\mathrm{\Pi }}_{\mathsf{BP}}$ is comparable to ${\mathrm{\Pi }}_{\mathsf{FP}}$ . For example, the time taken by the search protocol of ${\mathrm{\Pi }}_{\mathsf{WBP}}$ and ${\mathrm{\Pi }}_{\mathsf{BP}}$ for a search that returned 150,000 results is around 0.60 and 0.73 seconds respectively as compared to 0.54 seconds in ${\mathrm{\Pi }}_{\mathsf{FP}}$ . The performance results indicate that the proposed constructions are 2× faster and improve upon the communication cost by a factor of 1.5–11 compared to the most efficient backward private construction in literature.

The security parameter is denoted by λ. All procedures in our construction implicitly take λ as input. By efficient, we mean probabilistic polynomial-time in λ. All the algorithms (including adversaries and simulators) are assumed to be efficient unless otherwise specified. A function f: $\mathbb{N}\to \mathbb{R}$ is said to be a negligible function iff for all $\mathit{c}\mathrm{>}$ 0, $\exists {\mathit{n}}_0\in \mathbb{N}$ such that $\forall \mathit{n}⩾{\mathit{n}}_0$ , $\mathit{f}\mathrm{(}\mathit{n}\mathrm{)}\mathrm{<}{\mathit{n}}^{-\mathit{c}}$ . The function $\mathsf{neg}\mathrm{(}\mathit{\lambda }\mathrm{)}$ denotes a negligible function in λ. For a finite set X, $\mathit{x}\stackrel{\mathrm{\$}}{\leftarrow }\mathit{X}$ means that x is uniformly sampled from X and $|\mathit{X}|$ denotes the cardinality of set X. $\mathit{x}\leftarrow \mathit{y}$ denotes that variable x is assigned the value of variable y and operator ‖ denotes concatenation. For a data structure $\mathsf{DS}$ , $|\mathsf{DS}|$ denotes the memory space occupied by the data structure in bits. $\mathsf{addr}\mathrm{(}\mathsf{D}\mathrm{)}$ denotes the address in memory at which data structure instance $\mathsf{D}$ is stored. ⊥ denotes null value. For sets ${\mathit{X}}_1\mathrm{,}...\mathrm{,}{\mathit{X}}_{\mathit{n}}$ and Y, $\mathsf{Func}\mathrm{(}{\mathit{X}}_1\times \cdots \times {\mathit{X}}_{\mathit{n}}\mathrm{,}\mathit{Y}\mathrm{)}$ denotes the set of all functions from ${\mathit{X}}_1\times \cdots \times {\mathit{X}}_{\mathit{n}}$ to Y. For set X, $\mathsf{Perm}\mathrm{(}\mathit{X}\mathrm{)}$ denotes the set of all permutations on X. For sets ${\mathit{X}}_1$ and ${\mathit{X}}_2$ , ${\mathsf{Perm}}_{{\mathit{X}}_1}\mathrm{(}{\mathit{X}}_2\mathrm{)}$ denotes the set of all functions from ${\mathit{X}}_1\times {\mathit{X}}_2$ to ${\mathit{X}}_2$ , where for every $\mathit{x}\in {\mathit{X}}_1$ , we have a permutation on ${\mathit{X}}_2$ .

We use pseudo random functions ( $\mathsf{PRF}$ ), pseudo random permutations ( $\mathsf{PRP}$ ) and pseudorandom ciphertexts under chosen plaintext attack (RCPA) secure symmetric key encryption schemes in our constructions.

Pseudorandom Function ( $\mathsf{PRF}$ ) $\mathsf{F}$ is polynomial-time computable in λ and is indistinguishable from a truly random function by any adversary $\mathcal{A}$ .

Let $\mathsf{F}\in \mathsf{Func}\mathrm{(}\mathcal{K}\times \mathcal{I}\mathrm{,}\mathcal{O}\mathrm{)}$ be an efficient, keyed function. For algorithm $\mathcal{A}$ , we define the experiments ${\mathbf{Real}}_{\mathcal{A}}^{\mathsf{PRF}}\mathrm{(}\mathit{\lambda }\mathrm{)}$ and ${\mathbf{Ideal}}_{\mathcal{A}}^{\mathsf{PRF}}\mathrm{(}\mathit{\lambda }\mathrm{)}$ as shown in Fig. 1.

$\mathsf{F}$ is a pseudorandom function if for all probabilistic polynomial-time adversaries $\mathcal{A}$ , ${\mathbf{Adv}}_{\mathsf{F}\mathrm{,}\mathcal{A}}^{\mathsf{PRF}}\mathrm{(}\mathit{\lambda }\mathrm{)}=|Pr[{\mathbf{Real}}_{\mathcal{A}}^{\mathsf{PRF}}\mathrm{(}\mathit{\lambda }\mathrm{)}=1]-Pr[{\mathbf{Ideal}}_{\mathcal{A}}^{\mathsf{PRF}}\mathrm{(}\mathit{\lambda }\mathrm{)}=1]|⩽\mathsf{neg}\mathrm{(}\mathit{\lambda }\mathrm{)}$ .

Pseudorandom permutation ( $\mathsf{PRP}$ ) $\mathsf{F}$ is polynomial-time computable and invertible in λ and is indistinguishable from a truly random permutation by any adversary $\mathcal{A}$ .

Let $\mathsf{F}\in {\mathsf{Perm}}_{\mathcal{K}}\mathrm{(}\mathcal{X}\mathrm{)}$ be an efficient, keyed function. For algorithm $\mathcal{A}$ , we define the experiments ${\mathbf{Real}}_{\mathcal{A}}^{\mathsf{PRP}}\mathrm{(}\mathit{\lambda }\mathrm{)}$ and ${\mathbf{Ideal}}_{\mathcal{A}}^{\mathsf{PRP}}\mathrm{(}\mathit{\lambda }\mathrm{)}$ as shown in Fig. 2.

Graph: Fig. 1. PRF security definition.

Graph: Fig. 2. PRP security definition.

$\mathsf{F}$ is a pseudorandom permutation if for all probabilistic polynomial-time adversaries $\mathcal{A}$ , ${\mathbf{Adv}}_{\mathsf{F}\mathrm{,}\mathcal{A}}^{\mathsf{PRP}}\mathrm{(}\mathit{\lambda }\mathrm{)}=|Pr[{\mathbf{Real}}_{\mathcal{A}}^{\mathsf{PRP}}\mathrm{(}\mathit{\lambda }\mathrm{)}=1]-Pr[{\mathbf{Ideal}}_{\mathcal{A}}^{\mathsf{PRP}}\mathrm{(}\mathit{\lambda }\mathrm{)}=1]|⩽\mathsf{neg}\mathrm{(}\mathit{\lambda }\mathrm{)}$ .

A symmetric key encryption scheme $\mathcal{E}$ consists of three algorithms: $\mathsf{Gen}\mathrm{,}\mathsf{Enc}\text{ and }\mathsf{Dec}$ .

• $\mathsf{Gen}\mathrm{(}\mathrm{)}$ : It outputs a key $\mathsf{k}$ .
• $\mathsf{Enc}\mathrm{(}\mathsf{k}\mathrm{,}\mathsf{m}\mathrm{)}$ : It takes as input the key $\mathsf{k}$ , and a message $\mathsf{m}\in \mathcal{M}$ , where $\mathcal{M}$ is the message space, and outputs a ciphertext $\mathsf{e}$ .
• $\mathsf{Dec}\mathrm{(}\mathsf{k}\mathrm{,}\mathsf{e}\mathrm{)}$ : It takes as input the key $\mathsf{k}$ and a ciphertext $\mathsf{e}$ and outputs a message $\mathsf{m}\in \mathcal{M}$ or ⊥.

Correctness: For all $\mathsf{k}\leftarrow \mathsf{Gen}\mathrm{(}\mathrm{)}$ and for all messages $\mathsf{m}\in \mathcal{M}$ , it is required that $\mathsf{Dec}\mathrm{(}\mathsf{k}\mathrm{,}\mathsf{Enc}\mathrm{(}\mathsf{k}\mathrm{,}\mathsf{m}\mathrm{)}\mathrm{)}=\mathsf{m}$ .

RCPA security notion of symmetric key encryption scheme. The pseudorandom ciphertexts under chosen plaintext attack (RCPA) security notion [[9]] for symmetric key encryption scheme $\mathcal{E}=\mathrm{(}\mathsf{Gen}\mathrm{,}\mathsf{Enc}\mathrm{,}\mathsf{Dec}\mathrm{)}$ is captured in Fig. 3. $\mathsf{Initialize}$ () algorithm generates the key $\mathsf{k}$ using $\mathsf{Gen}$ algorithm of $\mathcal{E}$ and picks a random challenge bit b. The adversary can then adaptively ask queries to $\mathsf{Encrypt}$ () oracle. The game returns true if the adversary's output ${\mathit{b}}^{\prime }$ equals the challenge bit b. In Fig. 3, $\mathcal{C}$ denotes the ciphertext space.

A symmetric key encryption scheme $\mathcal{E}=\mathrm{(}\mathsf{Gen}\mathrm{,}\mathsf{Enc}\mathrm{,}\mathsf{Dec}\mathrm{)}$ is said to have pseudorandom ciphertexts under chosen plaintext attack (RCPA) if no adversary $\mathcal{A}$ can win the game shown in Fig. 3, except with probability at most $\frac{1}{2}+\mathsf{neg}\mathrm{(}\mathit{\lambda }\mathrm{)}$ . This probability is denoted by $Pr[{\text{RCPA}}_{\mathcal{E}}=1]$ .

The advantage of $\mathcal{A}$ in ${\mathrm{RCPA}}_{\mathcal{E}}$ game is defined as follows: ${\mathbf{Adv}}_{\mathcal{E}\mathrm{,}\mathcal{A}}^{\text{RCPA}}\mathrm{(}\mathit{\lambda }\mathrm{)}=2·Pr[{\text{RCPA}}_{\mathcal{E}}=1]-1$ .

Graph: Fig. 3.Security game: RCPAE.

The system consists of two parties: the client $\mathsf{C}$ (data owner) and the server $\mathsf{S}$ . $\mathsf{C}$ , who owns the database $\mathsf{DB}$ , encrypts the database and outsources it to $\mathsf{S}$ . The encrypted copy of the database created ensures that $\mathsf{S}$ responds to $\mathsf{C}$ 's queries (search and update) in an efficient manner with the guarantee that minimal information apart from the intended output of the query operation is leaked to the server. Usually, the encrypted database comprises of a secure index and a collection of encrypted documents. $\mathsf{S}$  responds to $\mathsf{C}$ 's queries with the help of this secure index.

We primarily follow the formalization of Bost et al. [[6]] with certain additions. A keyword is denoted by w and a document is addressed by its identifier $\mathsf{ind}$ . The database $\mathsf{DB}$ can be represented as: $\mathsf{DB}=\{\mathrm{(}{\mathsf{ind}}_{\mathit{i}}\mathrm{,}{\mathsf{W}}_{\mathit{i}}\mathrm{)}:1⩽\mathit{i}⩽\mathit{n}\}$ , where n denotes the number of documents in the database, ${\mathsf{ind}}_{\mathit{i}}\in {\{0\mathrm{,}1\}}^{\ell }$ are distinct document identifiers and ${\mathsf{W}}_{\mathit{i}}\subseteq {\{0\mathrm{,}1\}}^{\ast }$ is a set of keywords matching document ${\mathsf{ind}}_{\mathit{i}}$ , represented by binary strings of arbitrary length. Additionally, we consider the notations described in Table 2.

Table 2 Notations used in $\mathsf{DSSE}$ description

1 *By previous search on w, we mean the last search operation on w before the current search on w.

A $\mathsf{DSSE}$ scheme Π comprises of the following [[6]]:

• $\mathsf{Setup}\mathrm{(}\mathsf{DB}\mathrm{)}$ is a probabilistic algorithm that takes as input the initial database $\mathsf{DB}$ . It outputs ( $\mathsf{s}{t}_{\mathsf{C}}\mathrm{,}\mathsf{EDB}$ ), where the client's state $\mathsf{s}{t}_{\mathsf{C}}$ is given to $\mathsf{C}$ and the encrypted database $\mathsf{EDB}$ is given to  $\mathsf{S}$ . $\mathsf{Setup}$ algorithm is executed by $\mathsf{C}$ .
• $\mathsf{Search}\mathrm{(}\mathsf{q}\mathrm{,}\mathsf{s}{t}_{\mathsf{C}};\mathsf{EDB}\mathrm{)}=\mathrm{(}{\mathsf{Search}}_{\mathsf{C}}\mathrm{(}\mathsf{q}\mathrm{,}\mathsf{s}{t}_{\mathsf{C}}\mathrm{)}\mathrm{,}{\mathsf{Search}}_{\mathsf{S}}\mathrm{(}\mathsf{EDB}\mathrm{)}\mathrm{)}$ is a protocol (possibly probabilistic) between $\mathsf{C}$ and $\mathsf{S}$ . The input of $\mathsf{C}$ is the search query $\mathsf{q}$ and client's state $\mathsf{s}{t}_{\mathsf{C}}$ . The input of $\mathsf{S}$ is the encrypted database $\mathsf{EDB}$ . The output to the client is the updated client's state ${\mathsf{s}{t}_{\mathsf{C}}}^{\prime }$ and the set $\mathsf{Res}$ comprising of document identifiers matching the search query $\mathsf{q}$ . The output to the server is the updated encrypted database ${\mathsf{EDB}}^{\prime }$ .
• $\mathsf{Update}\mathrm{(}\mathsf{q}\mathrm{,}\mathsf{s}{t}_{\mathsf{C}};\mathsf{EDB}\mathrm{)}=\mathrm{(}{\mathsf{Update}}_{\mathsf{C}}\mathrm{(}\mathsf{q}\mathrm{,}\mathsf{s}{t}_{\mathsf{C}}\mathrm{)}\mathrm{,}{\mathsf{Update}}_{\mathsf{S}}\mathrm{(}\mathsf{EDB}\mathrm{)}\mathrm{)}$ is a protocol (possibly probabilistic) between $\mathsf{C}$ and $\mathsf{S}$ . The input of $\mathsf{C}$ is the query $\mathsf{q}=\mathrm{(}\mathsf{op}\mathrm{,}\mathsf{in}\mathrm{)}$ comprising of update operation $\mathsf{op}\in \{\mathsf{add}\mathrm{,}\mathsf{del}\}$ and the document-keyword pairs ( $\mathsf{ind}$ ,w) denoted by $\mathsf{in}$ , and client's state $\mathsf{s}{t}_{\mathsf{C}}$ . The input of $\mathsf{S}$ is the encrypted database $\mathsf{EDB}$ . The output to the client is the updated client's state ${\mathsf{s}{t}_{\mathsf{C}}}^{\prime }$ . The output to the server is the updated encrypted database ${\mathsf{EDB}}^{\prime }$ .

In this work, we consider the case of single keyword search, so, $\mathsf{q}=\mathit{w}$ and $\mathsf{Res}=\mathsf{DB}\mathrm{(}\mathit{w}\mathrm{)}$ in $\mathsf{Search}$ protocol. For simplicity, we consider $\mathsf{in}=\mathrm{(}\mathsf{ind}\mathrm{,}\mathit{w}\mathrm{)}$ , i.e., a single document-keyword pair in $\mathsf{Update}$ protocol. There are two use-cases of $\mathsf{Update}$ protocol in a $\mathsf{DSSE}$ scheme. In the first use-case updates to the $\mathsf{DB}$ are done at document level, such as in storing a collection of text files. In such scenarios, bulk-updates are needed, which can be supported by calling the $\mathsf{Update}$ protocol repeatedly. In the second use-case updates to the $\mathsf{DB}$ are done at keyword-document pair level, such as in record databases which requires a single call to $\mathsf{Update}$ protocol.

Similar to [[9], [28], [30], [39]], for a given query $\mathsf{q}$ , we consider the output of $\mathsf{Search}$ protocol to be the set of document identifiers satisfying $\mathsf{q}$ . This allows us to decouple the storage of documents from the storage of data structures used to realize the search operation, which is the focus of this work. The leakage profile $\mathcal{L}$ in the security definitions for an $\mathsf{SSE}$ scheme can then be given with respect to only the information that gets leaked to adversarial server till the set of document identifiers satisfying $\mathsf{q}$ are determined. The storage of actual documents can be done in a variety of ways [[10]], with varying types of leakages. $\mathsf{SSE}$ schemes are of two types: response-revealing and response-hiding [[27]]. The former reveals the query response in plaintext whereas the latter does not. We use this categorization in our paper.

Security. We consider $\mathsf{S}$ to be honest-but-curious. The security definition follows the real/ideal simulation paradigm [[10], [14]]. The definition is parameterized by a leakage profile $\mathcal{L}$ which captures all the information that the adversary may learn about the encrypted database and $\mathsf{C}$ 's queries through its participation in the protocols. Hence, the view of the adversary in the real world can be simulated by $\mathcal{L}$ . $\mathcal{L}=\{{\mathcal{L}}_{\mathsf{Setup}}\mathrm{,}{\mathcal{L}}_{\mathsf{Search}}\mathrm{,}{\mathcal{L}}_{\mathsf{Update}}\}$ , where ${\mathcal{L}}_{\mathsf{Setup}}$ , ${\mathcal{L}}_{\mathsf{Search}}$ and ${\mathcal{L}}_{\mathsf{Update}}$ correspond to the information leaked in the $\mathsf{Setup}$ , $\mathsf{Search}$ and $\mathsf{Update}$ protocols respectively to the server.

Let $\mathrm{\Pi }=\mathrm{(}\mathsf{Setup}\mathrm{,}\mathsf{Search}\mathrm{,}\mathsf{Update}\mathrm{)}$ be a $\mathsf{DSSE}$ scheme and let $\mathcal{L}=\{{\mathcal{L}}_{\mathsf{Setup}}\mathrm{,}{\mathcal{L}}_{\mathsf{Search}}\mathrm{,}{\mathcal{L}}_{\mathsf{Update}}\}$ be a stateful algorithm. For probabilistic polynomial time ( $\mathsf{PPT}$ ) algorithms $\mathcal{A}$ and $\mathsf{Sim}$ , we define the experiments ${\mathbf{Real}}_{\mathcal{A}}^{\mathrm{\Pi }}\mathrm{(}\mathit{\lambda }\mathrm{)}$ and ${\mathbf{Ideal}}_{\mathcal{A}\mathrm{,}\mathsf{Sim}}^{\mathrm{\Pi }}\mathrm{(}\mathit{\lambda }\mathrm{)}$ as follows:

${\mathbf{Real}}_{\mathcal{A}}^{\mathrm{\Pi }}\mathrm{(}\mathit{\lambda }\mathrm{)}$ .  $\mathcal{A}\mathrm{(}{1}^{\mathit{\lambda }}\mathrm{)}$ chooses $\mathsf{DB}$ . The experiment then runs $\mathrm{(}\mathsf{s}{t}_{\mathsf{C}}\mathrm{,}\mathsf{EDB}\mathrm{)}\leftarrow \mathsf{Setup}\mathrm{(}\mathsf{DB}\mathrm{)}$ and gives $\mathsf{EDB}$ to $\mathcal{A}$ . Then $\mathcal{A}$ makes polynomial number of adaptive queries. For each query $\mathsf{q}$ , if $\mathsf{q}$ is a search query (resp. update query), the game runs $\mathrm{(}\mathsf{Res}\mathrm{,}\mathsf{s}{t}_{\mathsf{C}}\mathrm{,}\mathsf{EDB}\mathrm{)}\leftarrow \mathsf{Search}\mathrm{(}\mathsf{q}\mathrm{,}\mathsf{s}{t}_{\mathsf{C}};\mathsf{EDB}\mathrm{)}$ (resp. $\mathrm{(}\mathsf{s}{t}_{\mathsf{C}}\mathrm{,}\mathsf{EDB}\mathrm{)}\leftarrow \mathsf{Update}\mathrm{(}\mathsf{q}\mathrm{,}\mathsf{s}{t}_{\mathsf{C}};\mathsf{EDB}\mathrm{)}$ ) and gives the generated transcript to $\mathcal{A}$ . Eventually $\mathcal{A}$ returns a bit that the game uses as its own output.

${\mathbf{Ideal}}_{\mathcal{A}\mathrm{,}\mathsf{Sim}}^{\mathrm{\Pi }}\mathrm{(}\mathit{\lambda }\mathrm{)}$ .  $\mathcal{A}\mathrm{(}{1}^{\mathit{\lambda }}\mathrm{)}$ chooses $\mathsf{DB}$ . The experiment then runs $\mathsf{EDB}\leftarrow \mathsf{Sim}\mathrm{(}{\mathcal{L}}_{\mathsf{Setup}}\mathrm{(}\mathsf{DB}\mathrm{)}\mathrm{)}$ and gives $\mathsf{EDB}$ to $\mathcal{A}$ . Then $\mathcal{A}$ makes polynomial number of adaptive queries. For each query $\mathsf{q}$ , if $\mathsf{q}$ is a search query (resp. update query), the game gives transcript generated by $\mathsf{Sim}\mathrm{(}{\mathcal{L}}_{\mathsf{Search}}\mathrm{(}\mathsf{q}\mathrm{)}\mathrm{)}$ (resp. $\mathsf{Sim}\mathrm{(}{\mathcal{L}}_{\mathsf{Update}}\mathrm{(}\mathsf{q}\mathrm{)}\mathrm{)}$ ). Eventually $\mathcal{A}$ returns a bit that the game uses as its own output.

We say that Π is $\mathcal{L}$ -semantically secure against adaptive attacks if for all adversaries $\mathcal{A}$ , there exists an algorithm $\mathsf{Sim}$ such that $|Pr[{\mathbf{Real}}_{\mathcal{A}}^{\mathrm{\Pi }}\mathrm{(}\mathit{\lambda }\mathrm{)}=1]-Pr[{\mathbf{Ideal}}_{\mathcal{A}\mathrm{,}\mathsf{Sim}}^{\mathrm{\Pi }}\mathrm{(}\mathit{\lambda }\mathrm{)}=1]|⩽\mathsf{neg}\mathrm{(}\mathit{\lambda }\mathrm{)}$ .

Common leakage. We follow some of the notations of common leakages from [[4], [6]]. The leakage profile $\mathcal{L}$ keeps as state the query list $\mathbf{\text{Q}}$ , i.e., the list of all queries issued so far along with their timestamp. Basically, the timestamps are a sequence of integers. The entries in $\mathbf{\text{Q}}$ are $\mathrm{(}\mathit{u}\mathrm{,}\mathit{w}\mathrm{)}$ for a search query on w, or $\mathrm{(}\mathit{u}\mathrm{,}\mathsf{op}\mathrm{,}\mathrm{(}\mathsf{ind}\mathrm{,}\mathit{w}\mathrm{)}\mathrm{)}$ for an update query $\mathrm{(}\mathsf{op}\mathrm{,}\mathrm{(}\mathsf{ind}\mathrm{,}\mathit{w}\mathrm{)}\mathrm{)}$ , where u denotes the timestamp of the query. Corresponding to the search queries, the search pattern $\mathsf{sp}\mathrm{(}\mathit{w}\mathrm{)}$ can be defined as $\mathsf{sp}\mathrm{(}\mathit{w}\mathrm{)}=\{\mathit{u}:\mathrm{(}\mathit{u}\mathrm{,}\mathit{w}\mathrm{)}\in \mathbf{\text{Q}}\}$ .

We also use the notation $\mathsf{Hist}\mathrm{(}\mathit{w}\mathrm{)}$ that denotes the list of all the modifications made to $\mathsf{DB}\mathrm{(}\mathit{w}\mathrm{)}$ over the time. It consists of ${\mathsf{DB}}_0\mathrm{(}\mathit{w}\mathrm{)}$ , the set of document indices matching w at setup, and a list $\mathsf{UpHist}\mathrm{(}\mathit{w}\mathrm{)}$ , comprising of the updates of documents matching w, called the update history. For example, consider two documents 1 and 2 matching w. Suppose, the update queries are $\mathrm{(}\mathsf{add}\mathrm{,}\mathrm{(}1\mathrm{,}\mathit{w}\mathrm{)}\mathrm{)}$ , $\mathrm{(}\mathsf{add}\mathrm{,}\mathrm{(}2\mathrm{,}\mathit{w}\mathrm{)}\mathrm{)}$ and $\mathrm{(}\mathsf{del}\mathrm{,}\mathrm{(}1\mathrm{,}\mathit{w}\mathrm{)}\mathrm{)}$ at timestamp 3, 12 and 20 respectively, then $\mathsf{UpHist}\mathrm{(}\mathit{w}\mathrm{)}=[\mathrm{(}3\mathrm{,}\mathsf{add}\mathrm{,}1\mathrm{)}\mathrm{,}\mathrm{(}12\mathrm{,}\mathsf{add}\mathrm{,}2\mathrm{)}\mathrm{,}\mathrm{(}20\mathrm{,}\mathsf{del}\mathrm{,}1\mathrm{)}]$ .

$\mathsf{Updates}\mathrm{(}\mathit{w}\mathrm{)}$ denotes the set of timestamps of updates on w. Formally,

$$\begin{array}{l}\hfill \mathsf{Updates}\mathrm{(}\mathit{w}\mathrm{)}=\{\mathit{u}|\mathrm{(}\mathit{u}\mathrm{,}\mathsf{add}\mathrm{,}\mathrm{(}\mathsf{ind}\mathrm{,}\mathit{w}\mathrm{)}\mathrm{)}\in \mathbf{\text{Q}}\text{ or }\mathrm{(}\mathit{u}\mathrm{,}\mathsf{del}\mathrm{,}\mathrm{(}\mathsf{ind}\mathrm{,}\mathit{w}\mathrm{)}\mathrm{)}\in \mathbf{\text{Q}}\}.\end{array}$$

${\mathsf{Updates}}^{\mathsf{op}}\mathrm{(}\mathit{w}\mathrm{)}$ is exactly like $\mathsf{Updates}\mathrm{(}\mathit{w}\mathrm{)}$ except along with the timestamp it also stores $\mathsf{op}$ corresponding to the update query.

Correctness. We say that a $\mathsf{DSSE}$ scheme is correct if the $\mathsf{Search}$ protocol returns the correct results for the keyword being searched (i.e., $\mathsf{DB}\mathrm{(}\mathit{w}\mathrm{)}$ ), except with negligible probability. We follow a similar formalization as [[9]].

In Fig. 4, the adversary $\mathcal{A}$ makes $\mathit{p}\mathrm{(}\mathit{\lambda }\mathrm{)}$ many queries, for some polynomial p. $\mathsf{Transcript}[\mathsf{Protocol}]$ means the view of server in $\mathsf{Protocol}$ . ${\mathrm{T}}_0=\varnothing$ and ${\mathrm{T}}_{\mathit{i}}=\{{\mathit{\tau }}_{\mathit{j}}:1⩽\mathit{j}⩽\mathit{i}\}$ , 1 $⩽\mathit{i}⩽\mathit{p}\mathrm{(}\mathit{\lambda }\mathrm{)}$ . Here, ${\mathit{\tau }}_{\mathit{j}}$ denotes the transcript of the jth query.

Graph: Fig. 4. DSSE correctness.

Let $\mathrm{\Pi }=\mathrm{(}\mathsf{Setup}\mathrm{,}\mathsf{Search}\mathrm{,}\mathsf{Update}\mathrm{)}$ be a $\mathsf{DSSE}$ scheme. For algorithm $\mathcal{A}$ we define the experiment ${\mathbf{DSSECor}}_{\mathcal{A}}^{\mathrm{\Pi }}\mathrm{(}\mathit{\lambda }\mathrm{)}$ as shown in Fig. 4.

We say that Π is correct if for all adversaries $\mathcal{A}$ , $Pr[{\mathbf{DSSECor}}_{\mathcal{A}}^{\mathrm{\Pi }}\mathrm{(}\mathit{\lambda }\mathrm{)}=1]⩽\mathsf{neg}\mathrm{(}\mathit{\lambda }\mathrm{)}$ .

As discussed earlier, two security properties, viz., forward privacy and backward privacy are desirable from a $\mathsf{DSSE}$ scheme. Informally speaking, the former captures that the newly updated entries cannot be related to previous search queries and the latter ensures that the search queries should not leak any information about indexes of deleted files. In the context of searchable encryption, the usual practice [[9], [13], [27]] is to argue security of $\mathsf{SSE}$ schemes by formulating a leakage profile $\mathcal{L}$ and proving that the leakage incurred in the proposed scheme is bounded by $\mathcal{L}$ . Recent works in the context of $\mathsf{DSSE}$ [[4], [6]] abstract out the information leakage incurred by a DSSE scheme in the form of definitions and attempt to justify that the formalized leakage profile adheres to the notion of forward/backward privacy. However, there could be several leakage profiles that capture the security notion in hand. One can choose among these formulations of leakage to achieve some sort of optimal balance between security and efficiency for the given context. Hence, the exercise of abstracting leakage-profiles of proposed constructions as alternative candidate definitions (as was the case for $\mathsf{SSE}$ [[8]]) may smoothen future evaluation of these leakages.

The question of what is the right definition of security is a vexed one [[31]]. Even for a widely used cryptographic primitive like digital signature, it has been argued that the accepted standard definition of security [[24]] does not take into account various issues that may crop up depending upon the application scenarios [[32], [35], [43]]. In the context of $\mathsf{DSSE}$ , security is argued by formally describing a leakage profile $\mathcal{L}$ and showing that the leakage incurred in construction is bounded by $\mathcal{L}$ . Hence, it is but natural that for a relatively new crypto/security protocol like $\mathsf{DSSE}$ , one needs to look at the formulations of leakage profiles from various perspectives. In this section, we perform a critical analysis of the existing notions of information leakage in backward private DSSE followed by an alternative formulation.

Bost at el. [[6]] made a seminal contribution in the area of $\mathsf{DSSE}$ by formalizing the notion of backward privacy through three different formulations viz., $\mathtt{BPIP}$ , $\mathtt{BPUP}$ and $\mathtt{WBP}$ , arranged in the ascending order in terms of information leakage. Naturally, like any other formalization of security these notions require further investigation. In that vein, we first reason why weak backward privacy ( $\mathtt{WBP}$ ) cannot be used to argue backward privacy in general and instead be reserved for backward privacy in a restricted setting only. Second, we introduce a relaxed leakage profile (Definition 3.5) that captures the notion of backward privacy. Finally, we introduce a desirable property for $\mathsf{DSSE}$ scheme called inverse backward privacy.

For simplicity we will assume that, $\mathsf{DB}$ is initially empty. Thus, the $\mathsf{Setup}$ algorithm leaks no information. If $\mathsf{DB}$ is not initially empty, typically, ${\mathcal{L}}_{\mathsf{Setup}}=\mathit{N}$ , where N denotes the number of document-keyword pairs. Let ${\mathcal{L}}_1$ and ${\mathcal{L}}_2$ denote two leakage profiles. If ${\mathcal{L}}_1$ leaks less than ${\mathcal{L}}_2$ , we denote it as ${\mathcal{L}}_1⪯{\mathcal{L}}_2$ . By the proposition, " ${\mathcal{L}}_1$ leaks less than ${\mathcal{L}}_2$ " we mean that ${\mathcal{L}}_1$ gives less information about the database and the queries to the simulator than ${\mathcal{L}}_2$ , or, said otherwise, that every information given by ${\mathcal{L}}_1$ can be inferred from ${\mathcal{L}}_2$ . If ${\mathcal{L}}_1$ leaks strictly less than ${\mathcal{L}}_2$ , we denote it as ${\mathcal{L}}_1\prec {\mathcal{L}}_2$ .

We recall the strongest notion of forward privacy discussed in [[6]]. Informally, a $\mathsf{DSSE}$ scheme is forward private if the $\mathsf{Update}$ protocol leaks no information about the updated keywords. Definition 3.1 captures that an update operation doesn't leak more than the operation $\mathsf{op}=\{\mathsf{add}\mathrm{,}\mathsf{del}\}$ of the update query $\mathsf{q}$ .

( $\mathtt{FP}\text{-}\mathtt{I}$ ). An $\mathcal{L}=\{{\mathcal{L}}_{\mathsf{Setup}}\mathrm{,}{\mathcal{L}}_{\mathsf{Search}}\mathrm{,}{\mathcal{L}}_{\mathsf{Update}}\}$ -semantically secure against adaptive attacks $\mathsf{DSSE}$ scheme Π is $\mathtt{FP}\text{-}\mathtt{I}$ iff ${\mathcal{L}}_{\mathsf{Setup}}\mathrm{,}{\mathcal{L}}_{\mathsf{Search}}\mathrm{,}{\mathcal{L}}_{\mathsf{Update}}$ can be written as:

$$\begin{array}{ll}\hfill & {\mathcal{L}}_{\mathsf{Setup}}\mathrm{(}\mathrm{)}=\varnothing .{\mathcal{L}}_{\mathsf{Search}}\mathrm{(}\mathit{w}\mathrm{)}⪯\{\mathsf{sp}\mathrm{(}\mathit{w}\mathrm{)}\mathrm{,}\mathsf{Hist}\mathrm{(}\mathit{w}\mathrm{)}\}.\\ \hfill & {\mathcal{L}}_{\mathsf{Update}}\mathrm{(}\mathsf{op}\mathrm{,}\mathrm{(}\mathsf{ind}\mathrm{,}\mathit{w}\mathrm{)}\mathrm{)}⪯\{\mathsf{op}\}.\end{array}$$

The notion of backward privacy was informally introduced in [[39]]. Intuitively, a backward private search for a keyword w should not reveal which documents in the past (which are now removed from the database) contained w. Like any other security property in the context of $\mathsf{SSE}$ , there could be several formulations of leakage profiles capturing this notion. Backward privacy was formalized in [[6]], through three different definitions, in the ascending order of information leakage, called respectively $\mathtt{BPIP}$ , $\mathtt{BPUP}$ and $\mathtt{WBP}$ . Informally, these formulations of leakages are described below:

• Backward Privacy with insertion pattern ( $\mathtt{BPIP}$ ): During a search on some keyword w, $\mathtt{BPIP}$ schemes leak the documents currently matching w, when they were inserted, and the total number of updates on w.
• Backward Privacy with update pattern ( $\mathtt{BPUP}$ ): During a search on w, $\mathtt{BPUP}$ schemes leak the documents currently matching w, when they were inserted, and when all the updates on w happened (but not their contents).
• Weak backward privacy ( $\mathtt{WBP}$ ): During a search on w, $\mathtt{WBP}$ schemes leak the documents currently matching w, when they were inserted, when all the updates on w happened, and which deletion update canceled which insertion update.

Let us demonstrate the differences between these notions with an example. Consider the following entries in query list ${\mathbf{\text{Q}}}_1$ corresponding to keyword w: $\mathrm{(}1\mathrm{,}\mathsf{add}\mathrm{,}\mathrm{(}{\mathsf{ind}}_1\mathrm{,}\mathit{w}\mathrm{)}\mathrm{)}$ , $\mathrm{(}4\mathrm{,}\mathsf{add}\mathrm{,}\mathrm{(}{\mathsf{ind}}_2\mathrm{,}\mathit{w}\mathrm{)}\mathrm{)}$ , $\mathrm{(}5\mathrm{,}\mathsf{del}\mathrm{,}\mathrm{(}{\mathsf{ind}}_1\mathrm{,}\mathit{w}\mathrm{)}\mathrm{)}$ , $\mathrm{(}12\mathrm{,}\mathsf{add}\mathrm{,}\mathrm{(}{\mathsf{ind}}_3\mathrm{,}\mathit{w}\mathrm{)}\mathrm{)}$ . Let us consider the leakage for each definition after a search query on w at timestamp 15. The first notion reveals that ${\mathsf{ind}}_2$ and ${\mathsf{ind}}_3$ match keyword w and that this entries were added at time 4 and 12 respectively. It also reveals that there were a total of 4 updates for w. The second notion, additionally reveals that updates on w happened at time 1, 4, 5 and 12. Finally, the third definition also reveals that the index that was added for w at time 1 was deleted at time 5.

We now recall the additional leakage functions from [[5]] apart from the ones described in Section 2.4, that are required to formally capture the notions of backward privacy mentioned above.

For a keyword w, $\mathsf{TimeDB}\mathrm{(}\mathit{w}\mathrm{)}$ is the list of all documents matching w, excluding the deleted ones together with the timestamp of when they were inserted in the database. Formally, $\mathsf{TimeDB}\mathrm{(}\mathit{w}\mathrm{)}$ can be constructed from the query list Q as follows:

$$\begin{array}{ll}\hfill & \mathsf{TimeDB}\mathrm{(}\mathit{w}\mathrm{)}=\{\mathrm{(}\mathit{u}\mathrm{,}\mathsf{ind}\mathrm{)}|\mathrm{(}\mathit{u}\mathrm{,}\mathsf{add}\mathrm{,}\mathrm{(}\mathit{w}\mathrm{,}\mathsf{ind}\mathrm{)}\mathrm{)}\in \mathbf{\text{Q }}\text{and }\\ \text{(1)}& \hfill & \forall {\mathit{u}}^{\prime }\mathrm{>}\mathit{u}\mathrm{,}\mathrm{(}{\mathit{u}}^{\prime }\mathrm{,}\mathsf{del}\mathrm{,}\mathrm{(}\mathit{w}\mathrm{,}\mathsf{ind}\mathrm{)}\mathrm{)}\notin \mathbf{\text{Q}}\}.\end{array}$$

The deletion history $\mathsf{DelHist}\mathrm{(}\mathit{w}\mathrm{)}$ of w is the list of timestamps for all deletion operations, together with the timestamp of the inserted entry it removes. Formally, $\mathsf{DelHist}\mathrm{(}\mathit{w}\mathrm{)}$ is constructed as:

$$\begin{array}{ll}\hfill \mathsf{DelHist}\mathrm{(}\mathit{w}\mathrm{)}=\{& \mathrm{(}{\mathit{u}}^{\mathsf{add}}\mathrm{,}{\mathit{u}}^{\mathsf{del}}\mathrm{)}|\exists \mathsf{ind}\text{ s.t. }\mathrm{(}{\mathit{u}}^{\mathsf{add}}\mathrm{,}\mathsf{add}\mathrm{,}\mathrm{(}\mathit{w}\mathrm{,}\mathsf{ind}\mathrm{)}\mathrm{)}\in \mathbf{\text{Q }}\text{and }\\ \text{(2)}& \hfill & \mathrm{(}{\mathit{u}}^{\mathsf{del}}\mathrm{,}\mathsf{del}\mathrm{,}\mathrm{(}\mathit{w}\mathrm{,}\mathsf{ind}\mathrm{)}\mathrm{)}\in \mathbf{\text{Q}}\}.\end{array}$$

With these tools, we can now formally define these three notions of backward privacy formally.

An $\mathcal{L}=\{{\mathcal{L}}_{\mathsf{Setup}}\mathrm{,}{\mathcal{L}}_{\mathsf{Search}}\mathrm{,}{\mathcal{L}}_{\mathsf{Update}}\}$ -semantically secure against adaptive attacks $\mathsf{DSSE}$ scheme Π is $\mathtt{BPIP}$ iff ${\mathcal{L}}_{\mathsf{Setup}}\mathrm{,}{\mathcal{L}}_{\mathsf{Search}}\mathrm{,}{\mathcal{L}}_{\mathsf{Update}}$ can be written as:

$$\begin{array}{ll}\hfill & {\mathcal{L}}_{\mathsf{Setup}}\mathrm{(}\mathrm{)}=\varnothing .{\mathcal{L}}_{\mathsf{Update}}\mathrm{(}\mathsf{op}\mathrm{,}\mathrm{(}\mathsf{ind}\mathrm{,}\mathit{w}\mathrm{)}\mathrm{)}⪯\{\mathsf{op}\}.\\ \hfill & {\mathcal{L}}_{\mathsf{Search}}\mathrm{(}\mathit{w}\mathrm{)}⪯\{\mathsf{TimeDB}\mathrm{(}\mathit{w}\mathrm{)}\mathrm{,}{\mathit{o}}_{\mathit{w}}\}.\end{array}$$

An $\mathcal{L}=\{{\mathcal{L}}_{\mathsf{Setup}}\mathrm{,}{\mathcal{L}}_{\mathsf{Search}}\mathrm{,}{\mathcal{L}}_{\mathsf{Update}}\}$ -semantically secure against adaptive attacks $\mathsf{DSSE}$ scheme Π is $\mathtt{BPUP}$ iff ${\mathcal{L}}_{\mathsf{Setup}}\mathrm{,}{\mathcal{L}}_{\mathsf{Search}}\mathrm{,}{\mathcal{L}}_{\mathsf{Update}}$ can be written as:

$$\begin{array}{ll}\hfill & {\mathcal{L}}_{\mathsf{Setup}}\mathrm{(}\mathrm{)}=\varnothing .{\mathcal{L}}_{\mathsf{Update}}\mathrm{(}\mathsf{op}\mathrm{,}\mathrm{(}\mathsf{ind}\mathrm{,}\mathit{w}\mathrm{)}\mathrm{)}⪯\{\mathsf{op}\mathrm{,}\mathit{w}\}.\\ \hfill & {\mathcal{L}}_{\mathsf{Search}}\mathrm{(}\mathit{w}\mathrm{)}⪯\{\mathsf{TimeDB}\mathrm{(}\mathit{w}\mathrm{)}\mathrm{,}\mathsf{Updates}\mathrm{(}\mathit{w}\mathrm{)}\}.\end{array}$$

( $\mathtt{WBP}$ ). An $\mathcal{L}=\{{\mathcal{L}}_{\mathsf{Setup}}\mathrm{,}{\mathcal{L}}_{\mathsf{Search}}\mathrm{,}{\mathcal{L}}_{\mathsf{Update}}\}$ -semantically secure against adaptive attacks $\mathsf{DSSE}$ scheme Π is $\mathtt{WBP}$ iff ${\mathcal{L}}_{\mathsf{Setup}}\mathrm{,}{\mathcal{L}}_{\mathsf{Search}}\mathrm{,}{\mathcal{L}}_{\mathsf{Update}}$ can be written as:

$$\begin{array}{ll}\hfill & {\mathcal{L}}_{\mathsf{Setup}}\mathrm{(}\mathrm{)}=\varnothing .{\mathcal{L}}_{\mathsf{Update}}\mathrm{(}\mathsf{op}\mathrm{,}\mathrm{(}\mathsf{ind}\mathrm{,}\mathit{w}\mathrm{)}\mathrm{)}⪯\{\mathsf{op}\mathrm{,}\mathit{w}\}.\\ \hfill & {\mathcal{L}}_{\mathsf{Search}}\mathrm{(}\mathit{w}\mathrm{)}⪯\{\mathsf{TimeDB}\mathrm{(}\mathit{w}\mathrm{)}\mathrm{,}\mathsf{DelHist}\mathrm{(}\mathit{w}\mathrm{)}\}.\end{array}$$

As is evident from the above definitions, the notion of backward privacy is more involved than that of forward privacy. Forward privacy can be formalized by ensuring that the update query doesn't leak the keyword corresponding to which the update has been made. Whereas it is more subtle in the case of backward privacy. One approach is to formulate a strong leakage profile for the security notion in hand that allows very limited information to be leaked by the constructions satisfying it. This approach was followed in formulating leakage profiles in definitions $\mathtt{BPIP}$ and $\mathtt{BPUP}$ . A possible shortcoming of this approach is that there could be candidate constructions that don't satisfy these strong requirements but may still satisfy the intuitive notion of backward privacy. The other extreme could be to let "as much information as one can think of" to be leaked that can be allowed by the security notion in hand. This seems to be the approach followed in $\mathtt{WBP}$ security notion. However, in this approach one must be careful that the additional leakage in the leakage profile does not end up violating the basic security notion of the corresponding task. We revisit the notion of $\mathtt{WBP}$ from this perspective.

${\mathcal{L}}_{\mathsf{Search}}$ in $\mathtt{BPIP}$ , $\mathtt{BPUP}$ and $\mathtt{WBP}$ should be augmented with leakage function $\mathsf{sp}\mathrm{(}\mathit{w}\mathrm{)}$ . Moreover, ${\mathcal{L}}_{\mathsf{Search}}$ in $\mathtt{WBP}$ should also be augmented with leakage function $\mathsf{Updates}\mathrm{(}\mathit{w}\mathrm{)}$ . The rationale behind the same is described in Section 3.4.

In this section, we scrutinize the notion of weak backward privacy. Let us consider the following entries in query list ${\mathbf{\text{Q}}}_1$ corresponding to w: $\mathrm{(}1\mathrm{,}\mathsf{add}\mathrm{,}\mathrm{(}\mathsf{ind}\mathrm{,}\mathit{w}\mathrm{)}\mathrm{)}$ , $\mathrm{(}3\mathrm{,}\mathit{w}\mathrm{)}$ , $\mathrm{(}5\mathrm{,}\mathsf{del}\mathrm{,}\mathrm{(}\mathsf{ind}\mathrm{,}\mathit{w}\mathrm{)}\mathrm{)}$ , $\mathrm{(}6\mathrm{,}\mathit{w}\mathrm{)}$ , $\mathrm{(}12\mathrm{,}\mathsf{add}\mathrm{,}\mathrm{(}\mathsf{ind}\mathrm{,}\mathit{w}\mathrm{)}\mathrm{)}$ , $\mathrm{(}14\mathrm{,}\mathsf{del}\mathrm{,}\mathrm{(}\mathsf{ind}\mathrm{,}\mathit{w}\mathrm{)}\mathrm{)}$ , $\mathrm{(}18\mathrm{,}\mathit{w}\mathrm{)}$ . Let us denote the search queries on w at timestamps 3, 6 and 18 by ${\mathsf{q}}_1$ , ${\mathsf{q}}_2$ and ${\mathsf{q}}_3$ respectively.

Leakage of the search query ${\mathsf{q}}_1$ :

$$\begin{array}{l}\hfill \mathsf{TimeDB}\mathrm{(}\mathit{w}\mathrm{)}=\{\mathrm{(}1\mathrm{,}\mathsf{ind}\mathrm{)}\}.\mathsf{DelHist}\mathrm{(}\mathit{w}\mathrm{)}=\varnothing .\end{array}$$

Leakage of the search query ${\mathsf{q}}_2$ :

$$\begin{array}{l}\hfill \mathsf{TimeDB}\mathrm{(}\mathit{w}\mathrm{)}=\varnothing .\mathsf{DelHist}\mathrm{(}\mathit{w}\mathrm{)}=\{\mathrm{(}1\mathrm{,}5\mathrm{)}\}.\end{array}$$

Note that, $\mathsf{DelHist}\mathrm{(}\mathit{w}\mathrm{)}$ leaks that the $\mathsf{add}$ operation at timestamp 1 is canceled by the $\mathsf{del}$ operation at timestamp 5. Through the content of $\mathsf{DB}\mathrm{(}\mathit{w}\mathrm{)}$ after queries ${\mathit{q}}_1$ and ${\mathit{q}}_2$ the adversary can infer that the $\mathsf{del}$ operation at timestamp 5 corresponds to document $\mathsf{ind}$ . Therefore, it adheres to the notion of backward privacy described at the beginning of this section.

Now, let us consider the search query ${\mathsf{q}}_3$ . After the search query ${\mathsf{q}}_2$ , $\mathrm{(}\mathsf{ind}\mathrm{,}\mathit{w}\mathrm{)}$ was added at timestamp 12 and later deleted at timestamp 14. Through the same intuitive notion of backward privacy, based on the state of $\mathsf{DB}\mathrm{(}\mathit{w}\mathrm{)}$ after queries ${\mathit{q}}_2$ and ${\mathit{q}}_3$ , the adversary should not infer which document does the update queries at timestamp 12 and 14 correspond to. However, the leakage of the search query ${\mathsf{q}}_3$ is:

$$\begin{array}{l}\hfill \mathsf{TimeDB}\mathrm{(}\mathit{w}\mathrm{)}=\varnothing .\mathsf{DelHist}\mathrm{(}\mathit{w}\mathrm{)}=\{\mathrm{(}1\mathrm{,}5\mathrm{)}\mathrm{,}\mathrm{(}1\mathrm{,}14\mathrm{)}\mathrm{,}\mathrm{(}12\mathrm{,}5\mathrm{)}\mathrm{,}\mathrm{(}12\mathrm{,}14\mathrm{)}\}.\end{array}$$

Hence, through the leakage profile the adversary can infer that updates at timestamp 12 and 14 correspond to document $\mathsf{ind}$ as it has already inferred which document the update queries at timestamp 1 and 5 correspond to. Clearly, this goes against the intuitive notion of backward privacy.

The following restriction is imposed on the constructions ${\mathsf{Diana}}_{\mathsf{del}}$ and $\mathsf{Janus}$ that are proven to be weak backward private in [[6]]: "reinsertion of a document-keyword pair is not allowed after the deletion of the corresponding document-keyword pair". The reinsertion restriction allows one to avoid scenarios such as above that violate the intuitive notion of backward privacy. Hence, $\mathtt{WBP}$ can be considered to argue backward privacy in reinsertion restriction setting only. However, $\mathtt{WBP}$ -constructions proposed in subsequent works [[21], [41]] do not explicitly mention that the reinsertion of document-keyword pair is not allowed. Therefore, in order to avoid any ambiguity, we feel it needs to be explicitly mentioned that $\mathtt{WBP}$ is applicable in such restricted scenarios only.

The case of reinsertion of document-keyword pair, may not be a concern in certain use-cases of $\mathsf{SSE}$ schemes where a new document identifier can be assigned to the updated document, thereby, ensuring that the newly inserted document-keyword pairs cannot be related to older ones. But this trick may not always be applicable especially when the contents of file can change dynamically over time. Here, one needs to handle reinsertion of keyword in existing documents, i.e., the document identifier can't be changed. Therefore, in such scenarios one needs to support reinsertion of document-keyword pairs. As an example, consider the case of a hospital database where the patients' records are documents and the disease they are suspected to suffer from are keywords. One cannot rule out a scenario in which based on newer symptoms a patient is re-suspected to suffer from a disease, say malignant brain tumor, which was ruled out earlier.

Here, we point out some subtle issues in Definitions 3.2, 3.3 and 3.4 and suggest modifications to address them. We first argue that $\mathsf{sp}\mathrm{(}\mathit{w}\mathrm{)}$ should be a part of ${\mathcal{L}}_{\mathsf{Search}}\mathrm{(}\mathit{w}\mathrm{)}$ in definitions of $\mathtt{BPIP}$ , $\mathtt{BPUP}$ and $\mathtt{WBP}$ [[6]]. $\mathtt{BPUP}$ -secure $\mathsf{Fides}$ [[6]] as well as $\mathtt{WBP}$ -secure $\mathsf{Janus}$ [[6]] and $\mathsf{Janus}++$ [[41]] leak $\mathsf{sp}\mathrm{(}\mathit{w}\mathrm{)}$ in $\mathsf{Search}$ protocol. Since, $\mathsf{sp}\mathrm{(}\mathit{w}\mathrm{)}$ is not mentioned explicitly to be part of the leakage profile in the definitions, one may conclude that $\mathsf{sp}\mathrm{(}\mathit{w}\mathrm{)}$ can always be derived from the other leakage functions in the respective definitions. However, consider the border-line scenario where no updates corresponding to w has occurred so far and two search queries on w are executed at timestamps 5 and 8 respectively. For search query at timestamp 8, $\mathsf{sp}\mathrm{(}\mathit{w}\mathrm{)}=\{5\}$ . However, the state of other leakage functions at timestamp 8 are: $\mathsf{TimeDB}\mathrm{(}\mathit{w}\mathrm{)}=\varnothing$ , $\mathsf{Updates}\mathrm{(}\mathit{w}\mathrm{)}=\varnothing$ and $\mathsf{DelHist}\mathrm{(}\mathit{w}\mathrm{)}=\varnothing$ . As can be observed, $\mathsf{sp}\mathrm{(}\mathit{w}\mathrm{)}$ cannot be derived from other leakage functions. Hence, $\mathsf{sp}\mathrm{(}\mathit{w}\mathrm{)}$ should be included in ${\mathcal{L}}_{\mathsf{Search}}\mathrm{(}\mathit{w}\mathrm{)}$ of $\mathtt{BPIP}$ , $\mathtt{BPUP}$ and $\mathtt{WBP}$ .

Next, we argue that ${\mathcal{L}}_{\mathsf{Search}}$ in $\mathtt{WBP}$ should also be augmented with leakage function $\mathsf{Updates}\mathrm{(}\mathit{w}\mathrm{)}$ . Recall that the informal notion of $\mathtt{WBP}$ in [[6]] states that a search query on w should at most leak the documents currently matching w, when they were inserted, when all the updates on w happened and the total number of updates on w. While formalizing the leakage profile of $\mathtt{WBP}$ [[6], Definition 4.2], the leakage in $\mathsf{Search}$ protocol is described as: ${\mathcal{L}}_{\mathsf{Search}}\mathrm{(}\mathit{w}\mathrm{)}⪯\mathrm{(}\mathsf{TimeDB}\mathrm{(}\mathit{w}\mathrm{)}\mathrm{,}\mathsf{DelHist}\mathrm{(}\mathit{w}\mathrm{)}\mathrm{)}$ . Note that, $\mathsf{Updates}\mathrm{(}\mathit{w}\mathrm{)}$ isn't explicitly a part of ${\mathcal{L}}_{\mathsf{Search}}\mathrm{(}\mathit{w}\mathrm{)}$ . This gives the impression that, given $\mathsf{TimeDB}\mathrm{(}\mathit{w}\mathrm{)}$ and $\mathsf{DelHist}\mathrm{(}\mathit{w}\mathrm{)}$ one can construct $\mathsf{Updates}\mathrm{(}\mathit{w}\mathrm{)}$ . Now, consider the following entries in query list ${\mathbf{\text{Q}}}_1$ corresponding to w: $\mathrm{(}1\mathrm{,}\mathsf{add}\mathrm{,}\mathrm{(}1\mathrm{,}\mathit{w}\mathrm{)}\mathrm{)}$ , $\mathrm{(}2\mathrm{,}\mathsf{del}\mathrm{,}\mathrm{(}2\mathrm{,}\mathit{w}\mathrm{)}\mathrm{)}$ , $\mathrm{(}4\mathrm{,}\mathsf{add}\mathrm{,}\mathrm{(}3\mathrm{,}\mathit{w}\mathrm{)}\mathrm{)}$ , $\mathrm{(}6\mathrm{,}\mathsf{del}\mathrm{,}\mathrm{(}1\mathrm{,}\mathit{w}\mathrm{)}\mathrm{)}$ , $\mathrm{(}8\mathrm{,}\mathit{w}\mathrm{)}$ . Let us denote the search query on w at timestamps 8 by ${\mathsf{q}}_1$ .

Leakage functions at search query ${\mathsf{q}}_1$ :

$$\begin{array}{ll}\hfill & \mathsf{TimeDB}\mathrm{(}\mathit{w}\mathrm{)}=\{\mathrm{(}4\mathrm{,}3\mathrm{)}\}.\mathsf{DelHist}\mathrm{(}\mathit{w}\mathrm{)}=\{\mathrm{(}1\mathrm{,}6\mathrm{)}\}.\\ \hfill & \mathsf{Updates}\mathrm{(}\mathit{w}\mathrm{)}=\{1\mathrm{,}2\mathrm{,}4\mathrm{,}6\}.\end{array}$$

Note that, $\mathsf{TimeDB}\mathrm{(}\mathit{w}\mathrm{)}$ and $\mathsf{DelHist}\mathrm{(}\mathit{w}\mathrm{)}$ collectively do not capture any information about the update operation at timestamp 2. As a result, $\mathsf{Updates}\mathrm{(}\mathit{w}\mathrm{)}$ cannot be constructed given the leakage functions $\mathsf{TimeDB}\mathrm{(}\mathit{w}\mathrm{)}$ and $\mathsf{DelHist}\mathrm{(}\mathit{w}\mathrm{)}$ . Hence, $\mathsf{Updates}\mathrm{(}\mathit{w}\mathrm{)}$ should be a part of ${\mathcal{L}}_{\mathsf{Search}}\mathrm{(}\mathit{w}\mathrm{)}$ of $\mathtt{WBP}$ . Further, the construction $\mathsf{Janus}$ also leaks $\mathsf{Updates}\mathrm{(}\mathit{w}\mathrm{)}$ in $\mathsf{Search}$ protocol. Hence, $\mathsf{Updates}\mathrm{(}\mathit{w}\mathrm{)}$ needs to be included in the leakage profile of $\mathsf{Janus}$ construction.

Thus, we suggest that the respective information leakage definitions in the context of search should be:

$$\begin{array}{ll}\hfill & {\mathcal{L}}_{\mathtt{BPIP}\mathrm{,}\mathsf{Search}}:\{\mathsf{sp}\mathrm{(}\mathit{w}\mathrm{)}\mathrm{,}\mathsf{TimeDB}\mathrm{(}\mathit{w}\mathrm{)}\mathrm{,}{\mathit{o}}_{\mathit{w}}\}.\\ \hfill & {\mathcal{L}}_{\mathtt{BPUP}\mathrm{,}\mathsf{Search}}:\{\mathsf{sp}\mathrm{(}\mathit{w}\mathrm{)}\mathrm{,}\mathsf{TimeDB}\mathrm{(}\mathit{w}\mathrm{)}\mathrm{,}\mathsf{Updates}\mathrm{(}\mathit{w}\mathrm{)}\}.\\ \hfill & {\mathcal{L}}_{\mathtt{WBP}\mathrm{,}\mathsf{Search}}:\{\mathsf{sp}\mathrm{(}\mathit{w}\mathrm{)}\mathrm{,}\mathsf{TimeDB}\mathrm{(}\mathit{w}\mathrm{)}\mathrm{,}\mathsf{Updates}\mathrm{(}\mathit{w}\mathrm{)}\mathrm{,}\mathsf{DelHist}\mathrm{(}\mathit{w}\mathrm{)}\}.\end{array}$$

Constructing backward private $\mathsf{DSSE}$ schemes with optimal communication complexity is an interesting question to explore. To achieve this goal it seems necessary for $\mathsf{S}$ to be able to identify which insertion entry is canceled by a particular delete entry. However, the stronger leakage profile definitions of $\mathtt{BPIP}$ and $\mathtt{BPUP}$ do not allow such information to be leaked to $\mathsf{S}$ . Therefore, like $\mathtt{WBP}$ , one may need to allow some non-trivial relation among the update queries to be leaked. But unlike $\mathtt{WBP}$ it should be able to capture the notion of backward privacy in the general setting. We observe that there can be several alternative formulations of such information leakage. Here we describe one such candidate definition, i.e., Backward Privacy with Link Pattern $\mathtt{BPLP}$ and later in Section 4.2 propose a natural construction whose leakage profile is tightly captured by $\mathtt{BPLP}$ .

In order to describe the leakage profile of $\mathtt{BPLP}$ , we introduce some new leakage functions. Let ${\mathsf{DB}}_{\mathit{x}}\mathrm{(}\mathit{w}\mathrm{)}$ and ${\mathsf{DB}}_{\mathit{x}+1}\mathrm{(}\mathit{w}\mathrm{)}$ denote the set of documents matching w at two successive searches x and $\mathit{x}+1$ respectively and let $\mathsf{LDB}\mathrm{(}\mathit{w}\mathrm{)}$ denote the list of documents matching w in $\mathit{x}+1$ th search, in order of their insertion. An element in $\mathsf{LDB}\mathrm{(}\mathit{w}\mathrm{)}$ is of the form $\mathrm{(}\mathit{i}\mathrm{,}\mathsf{ind}\mathrm{)}$ , where i denotes the index and $\mathsf{ind}$ denotes the document identifier. Let the timestamp of the xth and $\mathit{x}+1$ th search be denoted as ${\mathit{u}}_{\mathit{x}}$ and ${\mathit{u}}_{\mathit{x}+1}$ respectively. We define leakage functions Link Pattern I ( $\mathsf{LP}\text{-}\mathsf{I}$ ), Link Pattern II ( $\mathsf{LP}\text{-}\mathsf{II}$ ) and Link Pattern III ( $\mathsf{LP}\text{-}\mathsf{III}$ ):

$$\begin{array}{ll}\hfill \mathsf{LP}\text{-}\mathsf{I}\mathrm{(}\mathit{w}\mathrm{)}=& \{\mathrm{(}\mathsf{ind}\mathrm{,}\mathit{u}\mathrm{)}|\mathsf{ind}\in {\mathsf{DB}}_{\mathit{x}}\mathrm{(}\mathit{w}\mathrm{)}\text{ and }\mathrm{(}\mathit{u}\mathrm{,}\mathsf{op}\mathrm{,}\mathrm{(}\mathsf{ind}\mathrm{,}\mathit{w}\mathrm{)}\mathrm{)}\in \mathbf{\text{Q}}\\ \hfill & \text{ and }{\mathit{u}}_{\mathit{x}}\mathrm{<}\mathit{u}\mathrm{<}{\mathit{u}}_{\mathit{x}+1}\}.\\ \hfill \mathsf{LP}\text{-}\mathsf{II}\mathrm{(}\mathit{w}\mathrm{)}=& \{\mathrm{(}\mathsf{ind}\mathrm{,}\mathit{u}\mathrm{)}|\mathsf{ind}\in {\mathsf{DB}}_{\mathit{x}+1}\mathrm{(}\mathit{w}\mathrm{)}\text{ and }\mathrm{(}\mathit{u}\mathrm{,}\mathsf{op}\mathrm{,}\mathrm{(}\mathsf{ind}\mathrm{,}\mathit{w}\mathrm{)}\mathrm{)}\in \mathbf{\text{Q}}\\ \hfill & \text{ and }{\mathit{u}}_{\mathit{x}}\mathrm{<}\mathit{u}\mathrm{<}{\mathit{u}}_{\mathit{x}+1}\}.\\ \hfill \mathsf{LP}\text{-}\mathsf{III}\mathrm{(}\mathit{w}\mathrm{)}=& \{\mathrm{(}{\mathit{u}}_1\mathrm{,}{\mathit{u}}_2\mathrm{)}|\mathrm{(}{\mathit{u}}_1\mathrm{,}\mathsf{op}\mathrm{,}\mathrm{(}\mathsf{ind}\mathrm{,}\mathit{w}\mathrm{)}\mathrm{)}\in \mathbf{\text{Q}}\text{ and }\\ \hfill & \mathrm{(}{\mathit{u}}_2\mathrm{,}\mathsf{op}\mathrm{,}\mathrm{(}\mathsf{ind}\mathrm{,}\mathit{w}\mathrm{)}\mathrm{)}\in \mathbf{\text{Q}}\text{ and }{\mathit{u}}_{\mathit{x}}\mathrm{<}{\mathit{u}}_1\mathrm{<}{\mathit{u}}_2\mathrm{<}{\mathit{u}}_{\mathit{x}+1}\}.\end{array}$$

$\mathsf{LP}\text{-}\mathsf{I}\mathrm{(}\mathit{w}\mathrm{)}$ captures the relation between the identifiers obtained as a result in the xth search on w and the updates that happen between searches x and $\mathit{x}+1$ on w. $\mathsf{LP}\text{-}\mathsf{II}\mathrm{(}\mathit{w}\mathrm{)}$ captures the relation between the identifiers obtained as a result in the $\mathit{x}+1$ th search on w and the updates that happen between searches x and $\mathit{x}+1$ on w. $\mathsf{LP}\text{-}\mathsf{III}\mathrm{(}\mathit{w}\mathrm{)}$ captures the relation among the updates corresponding to same $\mathsf{ind}$ , that happen between x and $\mathit{x}+1$ search on w.

For example, let ( $\mathit{x}+1$ th) search query on w be at timestamp 16. Let the timestamp of the previous search query (x) on w be 4. Let ${\mathsf{DB}}_{\mathit{x}}\mathrm{(}\mathit{w}\mathrm{)}$ and ${\mathsf{DB}}_{\mathit{x}+1}\mathrm{(}\mathit{w}\mathrm{)}$ be $\{1\mathrm{,}2\}$ and $\{1\mathrm{,}3\}$ respectively. Let $\mathrm{(}5\mathrm{,}\mathsf{del}\mathrm{,}\mathrm{(}1\mathrm{,}\mathit{w}\mathrm{)}\mathrm{)}$ , $\mathrm{(}7\mathrm{,}\mathsf{del}\mathrm{,}\mathrm{(}2\mathrm{,}\mathit{w}\mathrm{)}\mathrm{)}$ , $\mathrm{(}12\mathrm{,}\mathsf{add}\mathrm{,}\mathrm{(}1\mathrm{,}\mathit{w}\mathrm{)}\mathrm{)}$ and $\mathrm{(}15\mathrm{,}\mathsf{add}\mathrm{,}\mathrm{(}3\mathrm{,}\mathit{w}\mathrm{)}\mathrm{)}$ be the update queries on w that occur between these two searches. The respective leakage functions will be:

$$\begin{array}{ll}\hfill & \mathsf{LP}\text{-}\mathsf{I}\mathrm{(}\mathit{w}\mathrm{)}=\{\mathrm{(}1\mathrm{,}5\mathrm{)}\mathrm{,}\mathrm{(}2\mathrm{,}7\mathrm{)}\mathrm{,}\mathrm{(}1\mathrm{,}12\mathrm{)}\}.\mathsf{LP}\text{-}\mathsf{III}\mathrm{(}\mathit{w}\mathrm{)}=\{\mathrm{(}5\mathrm{,}12\mathrm{)}\}.\\ \hfill & \mathsf{LP}\text{-}\mathsf{II}\mathrm{(}\mathit{w}\mathrm{)}=\{\mathrm{(}1\mathrm{,}5\mathrm{)}\mathrm{,}\mathrm{(}1\mathrm{,}12\mathrm{)}\mathrm{,}\mathrm{(}3\mathrm{,}15\mathrm{)}\}.\end{array}$$

Though the leakage functions defined above may appear a bit complex, they are useful abstractions through which $\mathtt{BPLP}$ captures the notion of backward privacy as shown below. In $\mathsf{Search}$ protocol, along with $\mathsf{sp}\mathrm{(}\mathit{w}\mathrm{)}$ and ${\mathsf{Updates}}^{\mathsf{op}}\mathrm{(}\mathit{w}\mathrm{)}$ , leakage functions $\mathsf{LP}\text{-}\mathsf{I}\mathrm{(}\mathit{w}\mathrm{)}$ , $\mathsf{LP}\text{-}\mathsf{II}\mathrm{(}\mathit{w}\mathrm{)}$ , $\mathsf{LP}\text{-}\mathsf{III}\mathrm{(}\mathit{w}\mathrm{)}$ and $\mathsf{LDB}\mathrm{(}\mathit{w}\mathrm{)}$ can be leaked to $\mathsf{S}$ . Let ${\text{I}}_{\mathsf{BP}}$ denote the set of document identifiers corresponding to which the entries have been already deleted. Note that, $\forall \mathsf{ind}\in {\text{I}}_{\mathsf{BP}}$ , as $\mathsf{ind}\notin {\mathsf{DB}}_{\mathit{x}}\mathrm{(}\mathit{w}\mathrm{)}$ and as the last update operation on $\mathrm{(}\mathsf{ind}\mathrm{,}\mathit{w}\mathrm{)}$ is $\mathsf{del}$ operation, it follows that $\mathsf{ind}\notin {\mathsf{DB}}_{\mathit{x}+1}\mathrm{(}\mathit{w}\mathrm{)}$ . Hence, no information about the $\mathsf{ind}$ s in ${\text{I}}_{\mathsf{BP}}$ can be revealed through leakage functions $\mathsf{LP}\text{-}\mathsf{I}\mathrm{(}\mathit{w}\mathrm{)}$ , $\mathsf{LP}\text{-}\mathsf{II}\mathrm{(}\mathit{w}\mathrm{)}$ and $\mathsf{LDB}\mathrm{(}\mathit{w}\mathrm{)}$ . As the other leakage functions viz., $\mathsf{sp}\mathrm{(}\mathit{w}\mathrm{)}$ and $\mathsf{LP}\text{-}\mathsf{III}\mathrm{(}\mathit{w}\mathrm{)}$ , do not leak $\mathsf{ind}$ corresponding to an update, no information about identifiers in ${\text{I}}_{\mathsf{BP}}$ gets revealed.

An $\mathcal{L}=\{{\mathcal{L}}_{\mathsf{Setup}}\mathrm{,}{\mathcal{L}}_{\mathsf{Search}}\mathrm{,}{\mathcal{L}}_{\mathsf{Update}}\}$ -semantically secure against adaptive attacks scheme Π is $\mathtt{BPLP}$ iff ${\mathcal{L}}_{\mathsf{Setup}}\mathrm{,}{\mathcal{L}}_{\mathsf{Search}}\mathrm{,}{\mathcal{L}}_{\mathsf{Update}}$ can be written as:

$$\begin{array}{ll}\hfill & {\mathcal{L}}_{\mathsf{Setup}}\mathrm{(}\mathrm{)}=\varnothing .{\mathcal{L}}_{\mathsf{Update}}\mathrm{(}\mathsf{op}\mathrm{,}\mathrm{(}\mathsf{ind}\mathrm{,}\mathit{w}\mathrm{)}\mathrm{)}=\varnothing .\\ \hfill & {\mathcal{L}}_{\mathsf{Search}}\mathrm{(}\mathit{w}\mathrm{)}⪯\{\mathsf{sp}\mathrm{(}\mathit{w}\mathrm{)}\mathrm{,}{\mathsf{Updates}}^{\mathsf{op}}\mathrm{(}\mathit{w}\mathrm{)}\mathrm{,}\mathsf{LP}\text{-}\mathsf{I}\mathrm{(}\mathit{w}\mathrm{)}\mathrm{,}\mathsf{LP}\text{-}\mathsf{II}\mathrm{(}\mathit{w}\mathrm{)}\mathrm{,}\\ \hfill & \phantom{{\mathcal{L}}_{\mathsf{Search}}\mathrm{(}\mathit{w}\mathrm{)}⪯}\mathsf{LP}\text{-}\mathsf{III}\mathrm{(}\mathit{w}\mathrm{)}\mathrm{,}\mathsf{LDB}\mathrm{(}\mathit{w}\mathrm{)}\}\end{array}$$

Note that Definition 3.5 ( $\mathtt{BPLP}$ ) captures the notion of forward privacy as well. Therefore, constructions that are $\mathtt{BPLP}$ secure are naturally forward private.

Next, we give a comparison among the leakage incurred in $\mathsf{Search}$ protocol of $\mathtt{BPUP}$ and $\mathtt{BPIP}$ with $\mathtt{BPLP}$ (Definition 3.5). As remarked earlier, the notion of $\mathtt{WBP}$ is only suitable to argue backward privacy in a restricted setting. Hence, it would not be meaningful to compare the definitions of backward privacy which apply to the general setting with $\mathtt{WBP}$ .

From the search leakage in $\mathtt{BPUP}$ (Definition 3.3) and $\mathtt{BPLP}$ (Definition 3.5), one can conclude that all the leakage functions in ${\mathcal{L}}_{\mathtt{BPUP}\mathrm{,}\mathsf{Search}}$ can be derived from the leakage functions in ${\mathcal{L}}_{\mathtt{BPLP}\mathrm{,}\mathsf{Search}}$ , as $\mathsf{TimeDB}\mathrm{(}\mathit{w}\mathrm{)}$ can be derived from $\mathsf{LP}\text{-}\mathsf{II}\mathrm{(}\mathit{w}\mathrm{)}$ , ${\mathsf{Updates}}^{\mathsf{op}}\mathrm{(}\mathit{w}\mathrm{)}$ and $\mathsf{DB}\mathrm{(}\mathit{w}\mathrm{)}$ (in particular $\mathsf{LDB}\mathrm{(}\mathit{w}\mathrm{)}$ ) of the successive searches on w. Note that, $\mathsf{TimeDB}\mathrm{(}\mathit{w}\mathrm{)}$ comprises of information regarding the timestamp of the $\mathsf{add}$ updates corresponding to document identifiers in $\mathsf{DB}\mathrm{(}\mathit{w}\mathrm{)}$ that are not followed by their respective $\mathsf{del}$ update. This can be easily determined by keeping track of all the $\mathsf{add}$ updates corresponding to document identifiers in $\mathsf{DB}\mathrm{(}\mathit{w}\mathrm{)}$ that are not followed by the respective $\mathsf{del}$ update through $\mathsf{LP}\text{-}\mathsf{II}\mathrm{(}\mathit{w}\mathrm{)}$ over all searches on w and ${\mathsf{Updates}}^{\mathsf{op}}\mathrm{(}\mathit{w}\mathrm{)}$ . Further, some leakage functions in ${\mathcal{L}}_{\mathtt{BPLP}\mathrm{,}\mathsf{Search}}$ such as $\mathsf{LP}\text{-}\mathsf{III}\mathrm{(}\mathit{w}\mathrm{)}$ , cannot be derived from ${\mathcal{L}}_{\mathtt{BPUP}\mathrm{,}\mathsf{Search}}$ (see below example). Hence, ${\mathcal{L}}_{\mathtt{BPUP}\mathrm{,}\mathsf{Search}}\prec {\mathcal{L}}_{\mathtt{BPLP}\mathrm{,}\mathsf{Search}}$ . Figure 5 summarizes the relation among definitions of backward privacy.

Graph: Fig. 5. Relations among definitions of backward privacy.

Consider the entries corresponding to w in query lists ${\mathbf{\text{Q}}}_1$ and ${\mathbf{\text{Q}}}_2$ as described below. Corresponding to w, $\mathrm{(}1\mathrm{,}\mathsf{add}\mathrm{,}\mathrm{(}1\mathrm{,}\mathit{w}\mathrm{)}\mathrm{)}$ , $\mathrm{(}2\mathrm{,}\mathsf{add}\mathrm{,}\mathrm{(}2\mathrm{,}\mathit{w}\mathrm{)}\mathrm{)}$ , $\mathrm{(}3\mathrm{,}\mathsf{del}\mathrm{,}\mathrm{(}1\mathrm{,}\mathit{w}\mathrm{)}\mathrm{)}$ , $\mathrm{(}4\mathrm{,}\mathsf{del}\mathrm{,}\mathrm{(}2\mathrm{,}\mathit{w}\mathrm{)}\mathrm{)}$ , $\mathrm{(}5\mathrm{,}\mathsf{add}\mathrm{,}\mathrm{(}3\mathrm{,}\mathit{w}\mathrm{)}\mathrm{)}$ and $\mathrm{(}6\mathrm{,}\mathit{w}\mathrm{)}$ are present in ${\mathbf{\text{Q}}}_1$ . Corresponding to w, $\mathrm{(}1\mathrm{,}\mathsf{add}\mathrm{,}\mathrm{(}1\mathrm{,}\mathit{w}\mathrm{)}\mathrm{)}$ , $\mathrm{(}2\mathrm{,}\mathsf{add}\mathrm{,}\mathrm{(}2\mathrm{,}\mathit{w}\mathrm{)}\mathrm{)}$ , $\mathrm{(}3\mathrm{,}\mathsf{del}\mathrm{,}\mathrm{(}2\mathrm{,}\mathit{w}\mathrm{)}\mathrm{)}$ , $\mathrm{(}4\mathrm{,}\mathsf{del}\mathrm{,}\mathrm{(}1\mathrm{,}\mathit{w}\mathrm{)}\mathrm{)}$ , $\mathrm{(}5\mathrm{,}\mathsf{add}\mathrm{,}\mathrm{(}3\mathrm{,}\mathit{w}\mathrm{)}\mathrm{)}$ and $\mathrm{(}6\mathrm{,}\mathit{w}\mathrm{)}$ are present in ${\mathbf{\text{Q}}}_2$ .

Following is the description of various leakage functions at timestamp 6 in ${\mathbf{\text{Q}}}_1$ :

$$\begin{array}{ll}\hfill & \mathsf{sp}\mathrm{(}\mathit{w}\mathrm{)}=\{6\}.\mathsf{Updates}\mathrm{(}\mathit{w}\mathrm{)}=\{1\mathrm{,}2\mathrm{,}3\mathrm{,}4\mathrm{,}5\}.\\ \hfill & \mathsf{TimeDB}\mathrm{(}\mathit{w}\mathrm{)}=\{\mathrm{(}5\mathrm{,}3\mathrm{)}\}.\mathsf{LP}\text{-}\mathsf{III}\mathrm{(}\mathit{w}\mathrm{)}=\{\mathrm{(}1\mathrm{,}3\mathrm{)}\mathrm{,}\mathrm{(}2\mathrm{,}4\mathrm{)}\}.\end{array}$$

Similarly, the leakage functions at timestamp 6 in ${\mathbf{\text{Q}}}_2$ are described as:

$$\begin{array}{ll}\hfill & \mathsf{sp}\mathrm{(}\mathit{w}\mathrm{)}=\{6\}.\mathsf{Updates}\mathrm{(}\mathit{w}\mathrm{)}=\{1\mathrm{,}2\mathrm{,}3\mathrm{,}4\mathrm{,}5\}.\\ \hfill & \mathsf{TimeDB}\mathrm{(}\mathit{w}\mathrm{)}=\{\mathrm{(}5\mathrm{,}3\mathrm{)}\}.\mathsf{LP}\text{-}\mathsf{III}\mathrm{(}\mathit{w}\mathrm{)}=\{\mathrm{(}1\mathrm{,}4\mathrm{)}\mathrm{,}\mathrm{(}2\mathrm{,}3\mathrm{)}\}.\end{array}$$

As can be observed the leakage functions in ${\mathcal{L}}_{\mathtt{BPUP}\mathrm{,}\mathsf{Search}}$ , i.e., $\mathsf{sp}\mathrm{(}\mathit{w}\mathrm{)}$ , $\mathsf{Updates}\mathrm{(}\mathit{w}\mathrm{)}$ and $\mathsf{TimeDB}\mathrm{(}\mathit{w}\mathrm{)}$ are the same for query lists ${\mathbf{\text{Q}}}_1$ and ${\mathbf{\text{Q}}}_2$ . However, $\mathsf{LP}\text{-}\mathsf{III}\mathrm{(}\mathit{w}\mathrm{)}$ is different for query lists ${\mathbf{\text{Q}}}_1$ and ${\mathbf{\text{Q}}}_2$ . Clearly, $\mathsf{LP}\text{-}\mathsf{III}\mathrm{(}\mathit{w}\mathrm{)}$ cannot be uniquely determined from the leakage functions in ${\mathcal{L}}_{\mathtt{BPUP}\mathrm{,}\mathsf{Search}}$ .

With the newly introduced $\mathtt{BPLP}$ , we now have four different formulations of information leakage in the context of backward privacy. An interesting question would be to analyze the real-world consequences of the leakages incurred by constructions satisfying these different notions, viz., $\mathtt{BPIP}$ , $\mathtt{BPUP}$ , $\mathtt{BPLP}$ or even $\mathtt{WBP}$ (in restricted setting).

Inverse backward privacy. We propose a new desirable property for a $\mathsf{DSSE}$ scheme called inverse backward privacy which captures the complementary situation of backward privacy. Analogous to backward privacy, a $\mathsf{DSSE}$ scheme is inverse backward private if whenever a document-keyword pair $\mathrm{(}\mathsf{ind}\mathrm{,}\mathit{w}\mathrm{)}$ is deleted and later added, subsequent search queries on w won't reveal the fact that $\mathrm{(}\mathsf{ind}\mathrm{,}\mathit{w}\mathrm{)}$ was deleted unless it can be inferred by the search and access pattern of the search query. For example, let $\mathsf{DB}\mathrm{(}\mathit{w}\mathrm{)}=\{1\mathrm{,}2\}$ for search query $\mathsf{q}$ at timestamp 5. Let the update operations on w after query $\mathsf{q}$ and before the next search query be $\mathrm{(}6\mathrm{,}\mathsf{del}\mathrm{,}\mathrm{(}1\mathrm{,}\mathit{w}\mathrm{)}\mathrm{)}$ , $\mathrm{(}12\mathrm{,}\mathsf{add}\mathrm{,}\mathrm{(}1\mathrm{,}\mathit{w}\mathrm{)}\mathrm{)}$ , then no information about the identifier 1 in update queries at timestamp 6 and 12 should be revealed to $\mathsf{S}$ in the next search query on w.

Inverse Backward Privacy property could be of relevance in various use-cases. For instance, consider the employee database where the employee records correspond to document and project teams she works in correspond to keywords. An employee ${\mathsf{E}}_1$ maybe dropped and reincluded in a project team. We would like to hide the fact that employee ${\mathsf{E}}_1$ was dropped briefly, if no search on that project team had been performed during that period.

In this section we propose two backward private schemes ${\mathrm{\Pi }}_{\mathsf{BP}}$ and ${\mathrm{\Pi }}_{\mathsf{WBP}}$ that are respectively $\mathtt{BPLP}$ and $\mathtt{WBP}$ secure. Our starting point is a forward private $\mathsf{DSSE}$ scheme ${\mathrm{\Pi }}_{\mathsf{FP}}$ which is a modified version of the scheme proposed in [[16]].

Graph: Fig. 6. Scheme ΠFP.

The central idea in ${\mathrm{\Pi }}_{\mathsf{FP}}$ (Fig. 6) is to make updates using fresh keys. Hence, the keys disclosed in previous searches do not reveal anything about these new updates. ${\mathrm{\Pi }}_{\mathsf{FP}}$ is described in Fig. 6. The construction makes use of $\mathsf{PRF}$ s ${\mathsf{F}}_{\mathit{t}}$ , ${\mathsf{F}}_{\mathit{d}}$ : ${\{0\mathrm{,}1\}}^{\mathit{\lambda }}\times {\{0\mathrm{,}1\}}^{\ast }\to {\{0\mathrm{,}1\}}^{\mathit{\lambda }}$ and hash functions ${\mathsf{H}}_1$ : ${\{0\mathrm{,}1\}}^{\mathit{\lambda }}\times {\{0\mathrm{,}1\}}^{\ast }\to {\{0\mathrm{,}1\}}^{2\mathit{\lambda }}$ and ${\mathsf{H}}_2$ : ${\{0\mathrm{,}1\}}^{\mathit{\lambda }}\times {\{0\mathrm{,}1\}}^{\ast }\to {\{0\mathrm{,}1\}}^{\mathit{\mu }}$ , where $\mathit{\mu }=\mathit{\lambda }+1$ and λ is the security parameter.

The $\mathsf{Setup}$ algorithm generates secret keys ${\mathsf{k}}_{\mathit{t}}$ and ${\mathsf{k}}_{\mathit{d}}$ . $\mathsf{C}$ initiates three maps: T, D and W. The maps T and D are stored at $\mathsf{S}$ 's end. Corresponding to w, D stores the pointer to ${\mathsf{PSet}}_{\mathit{w}}$ , the set of document identifiers in plaintext that were obtained as a result of the latest search operation on w and T stores encrypted entries inserted after the latest search operation on w. The map W is stored at $\mathsf{C}$ 's end. In W, corresponding to w, $\mathsf{C}$ stores the version ${\mathsf{ver}}_{\mathit{w}}$ (initialized to 0) and counter ${\mathsf{c}}_{\mathit{w}}$ (initialized to −1). ${\mathsf{ver}}_{\mathit{w}}$ ensures that the key ${\mathsf{k}}_{\mathit{w}}$ used in the $\mathsf{Update}$ protocol is unknown to $\mathsf{S}$ , ${\mathsf{c}}_{\mathit{w}}$ stores information about the number of entries added to T corresponding to w after the latest search operation.

$\underset{\_}{\mathsf{Update}}$ : When $\mathsf{C}$ wants to $\mathsf{add}\mathrm{/}\mathsf{del}$ a document-keyword pair ( $\mathsf{ind}\mathrm{,}\mathit{w}$ ), it computes key ${\mathsf{k}}_{\mathit{w}}$ using keyword w and ${\mathsf{ver}}_{\mathit{w}}$ (see line 5) and increments ${\mathsf{c}}_{\mathit{w}}$ . Based on ${\mathsf{k}}_{\mathit{w}}$ and ${\mathsf{c}}_{\mathit{w}}$ , $\mathsf{C}$ computes the hash digests $\mathsf{label}$ and $\mathsf{pad}$ and sends $\mathrm{(}\mathsf{label}\mathrm{,}\mathsf{e}=\mathsf{pad}\oplus \mathrm{(}\mathsf{b}||\mathsf{ind}\mathrm{)}\mathrm{)}$ to $\mathsf{S}$ . $\mathsf{S}$ then adds $\mathrm{(}\mathsf{label}\mathrm{,}\mathsf{e}\mathrm{)}$ to T. For $\mathsf{add}$ (resp. $\mathsf{del}$ ) operation, $\mathsf{b}=0$ (resp. $\mathsf{b}=1$ ).

Note that, ${\mathsf{k}}_{\mathit{w}}$ used in processing update queries is computed using updated ${\mathsf{ver}}_{\mathit{w}}$ . Since, ${\mathsf{k}}_{\mathit{w}}$ is output of $\mathsf{PRF}$ ${\mathsf{F}}_{\mathit{t}}$ at $\mathit{w}\Vert {\mathsf{ver}}_{\mathit{w}}$ , it is indistinguishable from random for $\mathsf{S}$ . As $\mathsf{label}$ (resp. $\mathsf{pad}$ ) is computed as ${\mathsf{H}}_1\mathrm{(}{\mathsf{k}}_{\mathit{w}}\Vert {\mathsf{c}}_{\mathit{w}}\mathrm{)}$ (resp. ${\mathsf{H}}_2\mathrm{(}{\mathsf{k}}_{\mathit{w}}\Vert {\mathsf{c}}_{\mathit{w}}\mathrm{)}$ ) for an update query, both are indistinguishable from random for $\mathsf{S}$ as ${\mathsf{H}}_1$ (resp. ${\mathsf{H}}_2$ ) is modeled as a random oracle. Hence, in the security proof, update queries can be simulated by generating random $\mathrm{(}\mathsf{label}\mathrm{,}\mathsf{e}\mathrm{)}$ pair.

$\underset{\_}{\mathsf{Search}}$ : When $\mathsf{C}$ wants to perform a search query on w, it computes ${\mathsf{label}}_{\mathit{w}}$ (see line 5) and the key ${\mathsf{k}}_{\mathit{w}}$ is computed (see line 7) only if new entries are inserted in map T. $\mathsf{C}$ sends ${\mathsf{label}}_{\mathit{w}}$ , ${\mathsf{k}}_{\mathit{w}}$ and ${\mathsf{c}}_{\mathit{w}}$ to $\mathsf{S}$ . ${\mathsf{k}}_{\mathit{w}}$ gets revealed to $\mathsf{S}$ only if a new entry was inserted to T after the previous search on w. Hence, $\mathsf{C}$ updates the version ${\mathsf{ver}}_{\mathit{w}}$ (see line 8). ${\mathsf{ver}}_{\mathit{w}}$ is not updated in a search query on w for which corresponding to w, no updates on map T were made after the previous search on w. Based on the information received from $\mathsf{C}$ , $\mathsf{S}$ computes the result set and updates D with the newly computed result set.

In ${\mathrm{\Pi }}_{\mathsf{FP}}$ , ${\mathsf{ver}}_{\mathit{w}}$ ensures that $\mathsf{S}$ cannot relate later updates with previous search queries and ${\mathsf{c}}_{\mathit{w}}$ ensures that $\mathsf{S}$ cannot correlate the update queries on w done after the previous search operation on w.

Essentially, ${\mathrm{\Pi }}_{\mathsf{FP}}$ is same as the construction in [[16]] except the following: 1) The search counter corresponding to w (denoted as ${\mathsf{ver}}_{\mathit{w}}$ ) is updated differently than in [[16]] to avoid unnecessary increments to the search counter. 2) After a search operation on w, the revealed document identifiers are stored together ( $\mathsf{DB}\mathrm{(}\mathit{w}\mathrm{)}$ ) in plaintext (as suggested in [[6]]) to provide reasonable locality without incurring any additional leakage.

Consider the following list of update queries: $\mathrm{(}\mathsf{add}\mathrm{,}\mathrm{(}1\mathrm{,}{\mathit{w}}_1\mathrm{)}\mathrm{)}$ , $\mathrm{(}\mathsf{add}\mathrm{,}\mathrm{(}1\mathrm{,}{\mathit{w}}_2\mathrm{)}\mathrm{)}$ , $\mathrm{(}\mathsf{add}\mathrm{,}\mathrm{(}2\mathrm{,}{\mathit{w}}_1\mathrm{)}\mathrm{)}$ , $\mathrm{(}\mathsf{add}\mathrm{,}\mathrm{(}3\mathrm{,}{\mathit{w}}_1\mathrm{)}\mathrm{)}$ , $\mathrm{(}\mathsf{add}\mathrm{,}\mathrm{(}3\mathrm{,}{\mathit{w}}_2\mathrm{)}\mathrm{)}$ , $\mathrm{(}\mathsf{del}\mathrm{,}\mathrm{(}1\mathrm{,}{\mathit{w}}_1\mathrm{)}\mathrm{)}$ . Figure 7(a) shows the state of indexes at $\mathsf{C}$ and $\mathsf{S}$ after these updates are processed. Figure 7(b) shows the state of indexes at $\mathsf{C}$ and $\mathsf{S}$ after search on ${\mathit{w}}_1$ .

Graph: Fig. 7.Example 1: indexes at C and S before and after search on w1 in construction ΠFP. W = client index, D = index that stores search results of previous search query at S and T = index that stores updates after the last search on w at S.

Correctness. The scheme is correct as long as there are no repeated labels in maps T and D. Since, ${\mathsf{F}}_{\mathit{d}}$ is a $\mathsf{PRF}$ , only with negligible probability ${\mathsf{label}}_{\mathit{w}}$ in D is same for two distinct keywords. The input to ${\mathsf{H}}_1$ is repeated only with negligible probability as ${\mathsf{F}}_{\mathit{t}}$ is a $\mathsf{PRF}$ . If we consider ${\mathsf{H}}_1$ to be a collision resistant hash function, only with negligible probability $\mathsf{label}$ in T is repeated.

In Appendix, we provide complete proofs of correctness and $\mathtt{FP}\text{-}\mathtt{I}$ -security (see Definition 3.1) of ${\mathrm{\Pi }}_{\mathsf{FP}}$ .

Bost et al. [[6]], proposed a generic way to obtain a two-roundtrip backward-private scheme from a forward private DSSE scheme. Applying this generic transformation on ${\mathrm{\Pi }}_{\mathsf{FP}}$ one gets a backward private scheme which is essentially the same as ${\mathsf{Mitra}}^{\ast }$ [[21]]. This backward private scheme is very efficient as it makes use of light-weight symmetric primitives only. However, the communication complexity of $\mathsf{Search}$ protocol in such a backward private scheme is $\mathit{O}\mathrm{(}{\mathit{o}}_{\mathit{w}}^{\prime }\mathrm{)}$ which is not optimal i.e., $\mathit{O}\mathrm{(}{\mathit{n}}_{\mathit{w}}\mathrm{)}$ . Further, as $\mathsf{C}$ has to process each ciphertext it receives from $\mathsf{S}$ , the computation complexity at $\mathsf{C}$ 's end also becomes $\mathit{O}\mathrm{(}{\mathit{o}}_{\mathit{w}}^{\prime }\mathrm{)}$ due to the above communication overhead. In order to obtain optimal communication complexity, $\mathsf{S}$ should send entries corresponding to only the set of documents currently matching w ( $\mathsf{DB}\mathrm{(}\mathit{w}\mathrm{)}$ ) to $\mathsf{C}$ . One approach to satisfy the above requirement is to associate a tag corresponding to each update entry. Using these tags, $\mathsf{S}$ , while performing a search on w will be able to correlate the update queries on w corresponding to the same $\mathsf{ind}$ . As in ${\mathsf{Diana}}_{\mathsf{del}}$ and $\mathsf{Janus}$ , if the tags are generated deterministically using just $\mathsf{ind}$ and w, it leaks $\mathsf{DelHist}\mathrm{(}\mathit{w}\mathrm{)}$ and hence, will not satisfy the notion of backward privacy in the general setting. Here, we leverage the version ${\mathsf{ver}}_{\mathit{w}}$ to generate the tags in a simple yet non-trivial manner to ensure that the leakage is bounded by $\mathtt{BPLP}$ (see Definition 3.5). This results in the first backward private scheme in the general setting achieving optimal communication complexity using light-weight symmetric primitives only.

Graph: Fig. 8. Scheme ΠBP.

Graph: Fig. 9. Example 2: indexes at C and S before and after search on w1 in ΠBP. W = client index, D = index that stores tags of search results of previous search query at S and T = index that stores updates after the last search on w at S.

Scheme ${\mathrm{\Pi }}_{\mathsf{BP}}$ is described in Fig. 8. For a keyword w, D stores the pointer to ${\mathsf{PSet}}_{\mathit{w}}$ , the set of tags corresponding to document identifiers that were obtained as a result of the latest search operation on w. The construction makes use of $\mathsf{PRF}$ s ${\mathsf{F}}_{\mathit{t}}$ , ${\mathsf{F}}_{\mathit{d}}$ : ${\{0\mathrm{,}1\}}^{\mathit{\lambda }}\times {\{0\mathrm{,}1\}}^{\ast }\to {\{0\mathrm{,}1\}}^{\mathit{\lambda }}$ , $\mathsf{PRP}$ ${\mathsf{G}}_{\mathsf{tag}}$ : ${\{0\mathrm{,}1\}}^{\mathit{\lambda }}\times {\{0\mathrm{,}1\}}^{2\mathit{\lambda }}\to {\{0\mathrm{,}1\}}^{2\mathit{\lambda }}$ and hash functions ${\mathsf{H}}_1$ : ${\{0\mathrm{,}1\}}^{\mathit{\lambda }}\times {\{0\mathrm{,}1\}}^{\ast }\to {\{0\mathrm{,}1\}}^{2\mathit{\lambda }}$ and ${\mathsf{H}}_2$ : ${\{0\mathrm{,}1\}}^{\mathit{\lambda }}\times {\{0\mathrm{,}1\}}^{\ast }\to {\{0\mathrm{,}1\}}^{\mathit{\mu }}$ , where $\mathit{\mu }=\mathit{\lambda }+1$ .

For an update query $\mathrm{(}\mathsf{op}\mathrm{,}\mathrm{(}\mathsf{ind}\mathrm{,}\mathit{w}\mathrm{)}\mathrm{)}$ , a $\mathsf{tag}$ corresponding to $\mathrm{(}\mathsf{ind}\mathrm{,}\mathit{w}\mathrm{)}$ is generated using the current version ${\mathsf{ver}}_{\mathit{w}}$ . Then, $\mathsf{b}\Vert \mathsf{tag}$ is stored in T at $\mathsf{S}$ in $\mathsf{Update}$ protocol (see line 10). For $\mathsf{add}$ (resp. $\mathsf{del}$ ) operation, $\mathsf{b}=0$ (resp. $\mathsf{b}=1$ ).