# SPEKS: Forward Private SGX-Based Public Key Encryption with Keyword Search
## 5 Analysis
### Performance Analysis
RSA or Elliptic Curve Cryptography cannot be used in such software-only based schemes, because the comparison over ciphertexts for search is not possible. However, the trusted execution environment provided by SGX enables the search process over plaintext while still guaranteeing the data privacy. Communication overheadAs the previous revocation-based FS-PEKS scheme [4], most of the search counter-based schemes including [PERSON] et al. 's scheme [12] generate multiple search tokens. To be specific, since public and private keys are revoked for each search phase, revocation-based FS-PEKS scheme needs to create multiple search tokens for previous ciphertext, and the size of the token depends on the number of searches made beforehand. Such an overhead becomes devastating as a number of searches are made subsequently. For instance, after 1000 searches, data receiver needs to generate 1000 search tokens. Moreover, the revocation-based approach leads to sending re-encrypted data, incurring an additional communication overhead. Likewise, [PERSON] et al. 's scheme [12] generates a number of search tokens as the search counter increases, shown in Figure 3. Therefore, communication overhead related to the query size depends on the number of search counters. As shown in Table 1, the query size is \(O\left(1\right)\) in our scheme because it requires only a constant number of search tokens regardless of the search counter. However, in [PERSON] et al. 's scheme [12], the number of generated search tokens increases as the search counter increases. [PERSON] at al,'s scheme, on the other hand, does not adopt counter-based mechanism, but still creates multiple search tokens for the search operations. As shown in Table 1, communication overhead related to query size in [PERSON] et al. 's scheme depends on the encoded time period. However, unlike the other previous schemes, our scheme only generates a single token regardless of the number of search counters, thus the proposed scheme is more scalable in practice. Overall, the proposed scheme significantly outperforms previous FS-PEKS schemes and achieves better security by exploiting trusted execution environment, specifically Intel SGX in our scheme. \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Scheme** & **Search Time** & **Query Size** & **Index Size** \\ \hline [PERSON] et al. [5] & \(O\left(\left|T\right|\cdot n_{d}\right)\) & \(O\left(\left|T\right|\right)\) & \(O\left(n_{d}\right)\) \\ \hline [PERSON] et al. [12] & \(O\left(\left|sc\right|\cdot n_{d}\right)\) & \(O\left(\left|sc\right|\right)\) & \(O\left(n_{d}+\left|id\right|\right)\) \\ \hline Our scheme & \(O\left(\left|sc\right|\cdot n_{d}\right)\) & \(O\left(1\right)\) & \(O\left(n_{d}\right)\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Efficiency comparison of public key encryption with keyword search (PEKS) schemes. (\(\left|sc\right|\) refers to the value of search counter, \(n_{d}\) refers to the number of data, \(\left|id\right|\) refers to size of identifier, \(\left|S\right|\) denotes number of searches made, \(\left|T\right|\) denotes a set of encoded time period.) Figure 3: Communication cost of each scheme. Figure 2: Computational cost of each algorithm.