# A Searchable Encryption with Forward/Backward Security and Constant Storage
## 4 Our Proposed Algorithm
### Decryption  
The decryption function algorithm is expressed by Algorithm 3. ```
Parse as \((C_{1},C_{2})\) \(F=C_{2}^{ski}=g_{3}^{s}\text{mod}N\); \(ind||op=C_{1}\oplus H_{3}(F)\); if\(op\
eq\)add,then \(DB(\omega)\gets DB(\omega)\backslash\{ind\}\); else \(DB(\omega)\gets DB(\omega)\cup\{ind\}\). ```  
**Algorithm 3** Decryption function  
```
\(\textbf{Parse as }(C_{1},C_{2})\) \(F=C_{2}^{ski}=g_{3}^{s}\text{mod}N\); \(ind||op=C_{1}\oplus H_{3}(F)\); if\(op\
eq\)add,then \(DB(\omega)\gets DB(\omega)\backslash\{ind\}\); else \(DB(\omega)\gets DB(\omega)\cup\{ind\}\). ```  
**Algorithm 4** Decryption function  
```
\(\textbf{Parse as }(C_{1},C_{2})\) \



## 5 Security Analysis

### Indistinguishable Identity Chosen Ciphertext Adversary (IND-ID-CCA)

In this section, we prove the security of the proposed scheme based on the IND-ID-CCA model using the following two theorems. In Theorem 1, we will show that an adversary with access to \(n\) private keys cannot obtain any information about the keys of p, z, q, and PKG. The security of this scheme relies on the difficulty of decomposing the RSA grand mode n. In other words, if an attacker manages to obtain p and q, then it can compute the private keys of all users. In Theorem 2, the security IND-ID-CCA model of the proposed scheme is proved. Let \(N=\widetilde{pq}=(pz+1)(2q+1)\) be an RSA module with unknown factorization, and \(G\) be a cyclic group of order \(zq\), and \(d_{i}={x_{i}}^{-1}\text{mod}zq\). Given the number of private keys (\(d_{i}\)) in the proposed scheme, it is infeasible to compute the decomposition of the mod \(N\) if the value of \(x_{i}\) is unknown, and for any two instances \(x_{i}\) and \(x_{j}\), the values of \(x_{i}-x_{j}\) and \(x_{i}\cdot x_{\text{j}}^{-1}\) are unknown to the adversary \(\mathcal{A}\). Proof. : Suppose there is an adversary \(\mathcal{A}\) that can obtain a number of instances of \(d_{i}\) satisfying the conditions of Theorem 1, and adversary \(\mathcal{A}\) can compute a private key \(d_{k}\) that does not satisfy the conditions of Theorem 1. Then prove that there exists an algorithm \(A\) that decomposes the computed modulus in approximately the same running time. The algorithm consists of the following three parts. Initialization: The algorithm \(A\) and \(N\) are given as the challenger \(\mathcal{C}\) generates \(N\) a random integer \(d_{i}\in_{R}Z_{zq}^{*}\) and sends it to adversary \(\mathcal{A}\). Note that the challenger \(\mathcal{C}\) does not know the factorization of \(N\), and there exists a unique element \(x_{i}={d_{i}}^{-1}\text{mod}zq\) that makes \(x_{i}=d_{i}^{-1}\text{mod}zq\). Challenge: The algorithm \(A\) requires the adversary \(\mathcal{A}\) to select one element in \(d_{i}\) and compute the private key \(d_{k}\) that does not satisfy the conditions of Theorem 1 associated with the challenge private key. Response: If adversary \(\mathcal{A}\) computes \(d_{k}\) and \(x_{i}-x_{k}\), then send them to algorithm \(A\), and algorithm \(A\) can decompose \(N\) as follows:

\[d_{k}d_{i}(x_{i}) =d_{k}\text{mod}zq\] \[d_{k}d_{i}(x_{k}) =d_{i}\text{mod}zq\] \[d_{k}d_{i}(x_{i}-x_{k}) =d_{k}-d_{i}\text{mod}zq\] \[d_{k}d_{i}(x_{i}-x_{k}) -d_{k}+d_{i}=0\text{mod}zq\]

which is a multiple of \(zq\). If the adversary \(\mathcal{A}\) computes \(d_{k}\) and \(v=x_{k}\cdot{x_{i}}^{-1}\), then give them to algorithm \(A\), and \(N\) can be factored by algorithm \(A\) as follows:

\[d_{i}(x_{i})=1\text{mod}zq\]

\[d_{k}(x_{i}v)=1\text{mod}zq\]

\[d_{i}x_{i}-d_{k}x_{i}v=0\text{mod}zq\]

\[x_{i}=d_{i}-d_{k}v\text{mod}zq\]

\[d_{i}x_{i}=0\text{mod}zq\]Although the rule set of private keys is finite, it is difficult to compute another valid private key without knowing the factorization of the computational modes. Let \(N=\widetilde{pq}=(pz+1)(2q+1)\) be a module of the RSA algorithm and \(G\) be the group of \(\mathcal{Z}_{N}^{*}\). The proposed scheme is secure for the adversary of \(IND-ID-CCA\) if the \(\widetilde{n}-TDDH\) problem holds in \(G\).