# A Searchable Encryption with Forward/Backward Security and Constant Storage
## 4 Our Proposed Algorithm
### Decryption
Assuming that the adversary \(\mathcal{A}\) solves the proposed solution with the advantage \(\epsilon\), there exists an algorithm \(B\) that solves the problem \(\widetilde{n}-TDDH\) with the advantage \(\frac{\epsilon}{\epsilon(n+1)}\). The goal of algorithm \(B\) is to distinguish two tuples \((g,g^{x}modN,g^{r}modN,g^{rx}modN)\) and \((g,g^{x}modN,g^{r}modN,T)\), where \(T\) is a random integer. In the next game, algorithm \(B\) interacts with adversary \(\mathcal{A}\). Initialization: In this phase, adversary \(\mathcal{A}\) is given an instance of \(\widetilde{n}-TDDH\) as input, where \(\left\{h_{i_{1}}=y_{i_{1}}+k_{i_{1}}zq,h_{i_{2}}=y_{i_{2}}+k_{i_{2}}zq,d_{i} =(y_{i_{1}}s_{1}+y_{i_{2}}s_{2})^{-1}\text{mod}zq\right\}_{i=1}^{n}\) and \(h_{c_{1}}=y_{c_{1}}p+zqk_{c_{2}}\). The hash functions \(H_{1}(\cdot)\) and \(H_{2}(\cdot)\) are used to simulate the random oracle \(O_{1}(\cdot)\) and \(O_{2}(\cdot)\); hash function \(H_{3}(\cdot)\) is used to simulate the random oracle \(O_{3}(\cdot)\), which is controlled by the challenger \(\mathcal{C}\) and \(\mathcal{C}\) can get the hash value by requesting it from random oracle. The random oracle function \(O_{1}(ID_{i})\): Challenger \(\mathcal{C}\) maintains the list \(List_{1}\), assigns the user's identity \(ID_{i}\) to \(O_{1}(\cdot)\) as input, and returns the hash value. When the adversary \(\mathcal{A}\) requests \(ID_{i}\), the challenger \(\mathcal{C}\) queries \(List_{1}\) and if it finds a tuple corresponding to the user's \(ID_{i}\) identity, it returns that tuple to adversary \(\mathcal{A}\). Otherwise, challenger \(\mathcal{C}\) chooses a random bit \(b_{i}\)\(\in\)[0,1], and sends \(h_{c_{1}}\) and \(h_{c_{2}}\) to the adversary if \(b_{i}=0\); otherwise, it chooses a random integer \(j\in\{1,\ldots,n\}\), and returns \(h_{j_{1}}\) and \(h_{j_{2}}\) to adversary \(\mathcal{A}\). Finally, it saves \(h_{j_{1}}\), \(h_{j_{2}}\), \(b_{i}\), as well as the identity \(ID_{i}\), to the list \(List_{1}\). \(O_{2}(\cdot)\) and \(O_{3}(\cdot)\) are similar to \(O_{1}(\cdot)\). Phase 1: The adversary \(\mathcal{A}\) is allowed to make up to \(n\) queries, each of which is a key generation query (\(ID_{i}\)) or a decryption query (\(CT\), \(ID_{i}\)), where the \(ID_{i}\) and \(CT\) are specified by \(\mathcal{A}\). The algorithm \(B\) sends a private key \(d_{i}\) corresponding to plaintext \(m\) or the specified \(ID_{i}\) and returns it to \(\mathcal{A}\). Key generation query (\(ID_{i}\), \(params\)): The challenger \(\mathcal{C}\) searches its database to find the corresponding tuple; if \(b_{i}=1\), it returns the private key \(d_{i}\), which is equal to \((y_{i_{1}}s_{1}+y_{i_{2}}s_{2})^{-1}\text{mod}zq\), to adversary \(\mathcal{A}\). Otherwise, it rejects the query and ends the game. Decrypt the query (\(CT\), \(ID_{i}\), \(params\)): The challenger \(\mathcal{C}\) will search the database \(O_{1}(\cdot)\) to find the tuple containing \(ID_{i}\). If \(b_{i}=1\), it extracts the \(d_{i}\) value from the tuple, computes \(O_{2}(C_{2}{}^{d_{i}})\oplus C_{1}\), and sends it to adversary \(\mathcal{A}\). Otherwise, challenger \(\mathcal{C}\) will reject the query. Challenge: First, adversary \(\mathcal{A}\) chooses two equal-length messages \(m_{0}\), \(m_{1}\in Z_{N}^{*}\), and an arbitrarily \(ID^{*}\), and sends them to algorithm \(B\). Second, algorithm \(B\) searches the database \(O_{1}(\cdot)\) for the corresponding tuple. If \(b^{*}=0\), it generates a random bit \(\gamma\in\{0,1\}\) and calculates \(CT^{*}=(O_{2}(g_{3}{}^{r})\oplus M_{\gamma},T)\), then sends it to the adversary. Otherwise, it rejects the query and ends the game. Assuming that adversary \(\mathcal{A}\) has the ability to decrypt \(CT^{*}\), then \(\gamma\) is available by \(T=g_{3}{}^{r(y_{i_{1}}s_{1}+y_{i_{2}}s_{2})}\text{mod}N\), but if \(T\) is a random element in \(G\), then adversary \(\mathcal{A}\) cannot obtain \(\gamma\).