# A Searchable Encryption with Forward/Backward Security and Constant Storage
## 4 Our Proposed Algorithm
### Decryption
Game1: In this section, the system maintains a table of pseudo-random functions indexed by keywords \(KEY\), and for each keyword \(\omega\), the system records the \(KEY\) bound to it. When a keyword is queried for the first time, a pseudo-random sequence is generated for it and written to the table \(KEY\), which is returned when the keyword is queried again. We map the algorithm program to obtain \(\Pr[Real_{A}(\lambda)=1,\) and if the adversary \(\mathcal{B}_{1}\) can distinguish Game 1 from this algorithm, it can distinguish the pseudo-random function \(F\) from the true random function, represented as follows: \(\Pr[Real_{A}(\lambda)=1]-\Pr[Game_{1}=1]\leq Adv^{prf}_{\mathcal{B}_{1}}(\lambda)\). Game2: In this section, the system maintains three tables: \(H_{0}\), \(H_{1}\) and \(H_{2}\), which correspond to \(H_{0}{}^{\circ tr}(kt_{\omega}),\,\,H_{0}(T_{\omega}||0)\,,\) and \(H_{0}(T_{\omega}||1)\,,\) respectively. When a keyword is queried, the system traverses the hash table and returns the hash value directly if the hash value corresponding to the keyword exists. Otherwise, a hash value is generated for it by the hash function, and it is stored in the table to be answered in the next query. Since the add operation is currently considered, the leak function of the update is defined as follows: \(\mathcal{L}_{ADD}(DOC)=\sum_{\omega\in W}|DB(\omega)|\), which will leak only the number of keyword/documentpairs. The search trapdoor \(T_{\omega}\) is generated as a random string in the _Update_ algorithm. The hash functions \(h_{1},h_{2}\) are also replaced by random strings. Each time the hash function is called, we return the corresponding hash values through the tables \(H_{0},H_{1}\) and \(H_{2}\), respectively. If the adversary can distinguish between Game2 and Game1, then it will be able to distinguish between the hash function \(H\) and the true random function. To summarize, we define the adversary \(\mathcal{B}_{2}\) as follows: \(\Pr[Game_{1}]-\Pr[Game_{2}=1]\leq Adv_{H,B_{2}}^{hash}(\lambda)\). Game3: In this game, the system maintains the table _Update_ for generating search trapdoors, which is indexed by keywords. In the search algorithm, Game3 generates the search trapdoor \(T_{\omega}\) by running the \(ctr\) hash function several times. Instead of mapping the keywords to the table \(Update\) of values in \(DIC\), the algorithm uses the table _Update_ that maps to the update count. This leads to \(\Pr[Game_{2}=1]=\Pr[Game_{3}=1]\). Except in \(Ideal_{\mathcal{L}}\), Game3 is the same as the ideal environment, which leads to \(\Pr[Game_{3}=1]=\Pr[Ideal_{A}(\lambda)=1]\). Conclusion: Through the above game interaction, in which the attacker queries and the system feeds back, by stating that \(F()\) is a pseudo-random function and the hash function \(H()\) is a one-way function, there exist two adversaries, \(\mathcal{B}_{1}\), \(\mathcal{B}_{2}\), expressed through the following equations: \(\Pr[Real_{A}=1]-\Pr[Ideal_{A}(\lambda)=1]\leq Adv_{B_{1}}(\lambda)+Adv_{B_{2} }(\lambda)\). Then, the theorem is proved. ## 6 Performance Evaluation

In this section, the scheme is compared with similar recent schemes in terms of the computational and storage overhead required for each phase of the algorithmic scheme operation. We tested our scheme on a Windows 10 operating system (64-bit), Intel(r) Core(TM) i5-6200 CPU @ 3.10 GHz, and a local virtual machine, VMware (4 GB RAM), running the open source project OpenStack for performance testing, which can provide sufficient computing resources for computation. Basic cryptographic operations were implemented using the Python cryptographic package pycrypto. Table 2 shows the time required for different operations. ### Data Sets

The test uses a dataset from SNAP [24]: Amazon reviews, which consists of reviews from Amazon. Reviews include product and user information, ratings, and plain text reviews. In the above review dataset, 2,441,053 pieces of product information were extracted and used as search keywords.