# A Searchable Encryption with Forward/Backward Security and Constant Storage
## 2 Preliminaries
### Double-Layer Structure  
To optimize the storage structure, our scheme uses a double-layer structure, as shown in Figure 1. This structure consists of two parts: a key index chain (KIC) at the upper level and a document index chain (DIC) at the lower level. In this structure, the space occupied by the state information is constant.  
\begin{table}
\begin{tabular}{l l} \hline \hline
**Notations** & **Meanings** \\ \hline \(x\stackrel{{\xi}}{{\xi}}X\) & randomly selected \(x\) from \(X\) \\ \(\lambda\) & security parameters \\ \(doc\) & the document \\ \(ind\) & identifier of document \\ \(W_{ind}\) & a collection of keywords containing the document identifier \(ind\) \\ \(DB\) & the document database \\ \(CLen\) & chain length \\ \(EDB\) & encrypted document database \\ \(n\) & number of documents in the database \\ \(R_{\omega}\) & the keyword identifier of \(\omega\) \\ \(T_{\omega}\) & trapdoors of keyword \(\omega\) \\ \(m\) & total number of keywords \\ \(op\) & data operators: add or delete \\ \(||\) & data concatenation operator \\ \(\oplus\) & bitwise exclusive OR(XOR) operator \\ \hline \hline \end{tabular}
\end{table}
Table 1: Parameter identifiers.  
Keyword index chain: the client is responsible for storing a global counter and a key. With this structure, users can generate search trapdoors for a keyword without knowing the keyword's current state. The scheme uses a keyword index chain design to achieve a constant client storage cost.  
Let \(H_{0}\)**(*)** be a cryptographic hash function, and the keyword index chain of the keyword \(\omega\) consists of \(CLen\) search trapdoors, \(H_{0}(T_{\omega}),{H_{0}}^{2}(T_{\omega}),\ldots,H_{0}{}^{CLen-1}(T_{\omega}),H _{0}{}^{CLen}(T_{\omega})\), where \(kt_{\omega}\) is the keyword identifier of the keyword \(\omega\) and \(H_{0}{}^{\prime}(T_{\omega})\bigg{\{}\begin{array}{ll}H_{0}(kt_{\omega})&j=1 \\ H_{0}({H_{0}}^{j-1}(kt_{\omega}))&j\geq 2\\ \end{array}\bigg{\}}\). With the search trapdoors of the keyword \(\omega\) and the global counter \(ctr(1\leq ctr\leq CLen)\), the server can calculate all the search trapdoors of the keyword index chain before the position of \(H_{0}{}^{ctr}(kt_{\omega})\) by iteratively calling the hash function \(H_{0}\)**(*)**, i.e., the server can obtain the search trapdoors of \(H_{0}(kt_{\omega})\) to \({H_{0}}^{ctr}(kt_{\omega})\). The basic structure of the operation is shown in Figure 2. The server cannot reverse the keyword index chain. Additional overhead is incurred for the \(CLen-ctr\) hash operations performed on the server side, but the operational overhead of this stage is acceptable in practice because the hash function operation overhead is very low.  
Figure 1: Double-layer structure.  
Figure 2: Server operation process.  
Document index chain: If a trapdoor corresponds to a set of keyword/document pairs, the global counter \(ctr\) is quickly consumed when the number of keywords is large. To solve this problem, we designed a lower-level structure. Each search trapdoor node in the keyword index chain corresponds to a document index chain node, and a set of keyword/document pairs can be encoded for a specific keyword in the update.