# Secure Remote Storage of Logs with Search Capabilities
## 4 Proposed Solution
### Indexing
Regarding the number operations required in search operations, our solution does not require any encryption operation, unlike the solutions of [PERSON], [PERSON], [PERSON], and [PERSON]. The first uses 2 asymmetric encryption operations per keyword \(K\), the second and the third use a single asymmetric encryption operation, and third uses 1 asymmetric encryption operation per keyword \(K\). Hash operations are used by [PERSON], Accorsi, and Zhao. The first uses 3 hashes per each keyword \(K\) and number \(N\) of matched log records, and the second and the third use \(K\) hash operations. Decryption operations exist on all solutions. Except Ohtaki, which requires \(2 ND_{s}\) operations per each \(K\), all solutions use a single decryption operation per \(N\) number of returned log records. [PERSON], [PERSON], and [PERSON] use symmetric encryption, while [PERSON] and Zhao use asymmetric encryption. The proposed solution requires 1 hash operation per each keyword \(K\), plus an hash and symmetric decryption operation per each number \(N\) of matches log records. \begin{table}
\begin{tabular}{l c c} \hline \hline
**Name** & **Indexing** & **Search** \\ \hline [PERSON] & \(E_{s}+2 KE_{a}\) & \(2 KE_{a}+ND_{s}\) \\ Ohtaki & \(E_{a}+(2K+1)E_{s}\) & \(E_{a}+K(2 ND_{s})\) \\ Sabbaghi & \(E_{s}+E_{a}+3 KH\) & \(E_{a}+3 KNH+ND_{s}\) \\ Accorsi & \(E_{s}+3H+KH\) & \(H+KH+ND_{s}\) \\ Savade & \(E_{a}+KE_{a}\) & \(KE_{a}+ND_{a}\) \\ Zhao & \(E_{a}+3 KH\) & \(KH+ND_{a}\) \\ \hline Our Solution & \(E_{s}+3H+KH\) & \(KH+NH+ND_{s}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Comparison of indexing and search operations. A projection of the time required to search and decrypt various numbers (\(N\)) of matching results was also done (see Figure 8). This projection uses the same time values for the different cryptographic operations as the ones used in the indexing projection. Additionally, a value \(K=1\) is assumed for the number of keywords comprised in the search query. Figure 8 uses a logarithmic scale. It shows that solutions with lesser computational cost, compared to the proposed solution, exist. Nonetheless, the performance of the proposed solution was deemed acceptable since the level of search enhancement achieved outweigh the differential computational cost of the search operation. We denote that the search operation is the least frequent one and that our solution still obtains an average performance on these operations. Figure 8: Comparison of searching times. Figure 7: Comparison of indexing times. A second comparison motivated by the analysis of the validation sections of the related work was also performed. This comparison is focused on the storage and time requirements for both index and search operations present on the validation sections of the related work. Nevertheless, not every author whose work supports search is referred to in this comparison due to the lack of information regarding that type of testing on their solutions. The solution proposed by [PERSON] [79] presents some information regarding the storage space requirements. The author states that a 100 MB storage is capable of storing 800,000 public keys that correspond to 800,000 keywords. The space needed to store the encrypted log records is not addressed. Our solution requires, for the maximum key sizes (256 bits for AES, 512 bits for SHA-3), a storage space of 23 MB for the inverted index. Regarding the indexing elapsed times, [PERSON] states that, for each keyword, his solution requires 180 ms to compute its trapdoor, if that trapdoor is not already in a cache. If it is present on a cache, this operation takes 5 ms. If we consider the 30,000 sample log records used on the performance tests and that only one keyword exists per log record, [PERSON] solution would require roughly 25 min to index the keywords, considering a 5 ms time per keyword. Our solution was capable of indexing the 30,000 sample log records, which contained more that one keyword per log record, in under 15 min.