# SPEKS: Forward Private SGX-Based Public Key Encryption with Keyword Search
## 5 Analysis
### Performance Analysis  
In this section, we analyze the performance of our scheme and provide a comparative analysis with previous forward secure public key encryption with keyword search (FS-PEKS) schemes such as [PERSON] at al. 's [5] and [PERSON] et al. 's [12] schemes. Our experiment is run on a system equipped with Intel(R) Core(TM) i7-9700K CPU at 3.60 GHz, 16G DDR4 RAM. 64-bit Ubuntu 18.04.4 LTS with enabled SGX is used as an operating system. Our scheme is implemented based on Intel's Software Guard Extension (SGX) Software Development Kit (SDK). When considering the multi-user environment, it is important to evaluate the initial costs for key setup and key management. In order for general symmetric searchable encryption (SSE) schemes to support a multi-user environment, they need to set up the key multiple times in proportion to the number of users. For instance, if we define \(u\) as the number of data senders and \(|DH|\) as the initial cost of Diffie-Hellman key exchange protocol between a data sender and a data receiver, then the initial cost for the key setup is  
\[(initial\quad key\quad setup\quad cost)=u\cdot|DH|.\]  
However, the proposed scheme does not require key exchange protocol for each data sender, thus the key setup cost remains constant. Furthermore, since the data receiver also needs to manage each key corresponding to each data sender, storage overhead for storing the key is also increased in proportion to the number of data senders in the previous schemes. For the key management, SSE schemes require a data receiver to store all of the keys set up for data senders. If \(|K|\) refers to the size of a key, the overall storage overhead is  
\[(storage\quad cost)=u\cdot|K|.\]  
Whereas, our scheme does not require a data receiver to store multiple keys for each sender. Therefore, our scheme has constant storage overhead for key management regardless of the number of data senders, which shows high scalability of our scheme in the multi-sender environment. Computation overheadAs shown in Figure 2, the proposed scheme has lower computation cost compared to those of [PERSON] et al. 's and [PERSON] at al. 's schemes. Specifically, for \(PEKS\) algorithm, while [PERSON] at al. 's scheme takes 3.958 ms and [PERSON] at al. 's takes 8.123 ms, our scheme takes just 0.0919 ms, which is significantly less overhead. Next, for generating a search token using \(Trapdoor\) algorithm, our scheme takes 0.02 ms, which is constant independently of the search count. However, in [PERSON] et al. 's scheme [12], it takes 4.85 ms for a single search token, and the computational cost increases in proportion to the number of search counters. [PERSON] at al. 's scheme takes 12.11 ms for running \(Trapdoor\), which is orders of magnitude slower than ours. In addition, for the _Search_ algorithm, as shown in Table 1, it has the same complexity as our scheme in terms of the search time. However, when measuring the actual computation time in practice, the _Search_ algorithm of ours takes, in average, 0.0436 ms, while the computation cost of search process in [5] depends on a set of encoded time period. This causes unnecessary computational overhead for some cases. The search algorithm in [PERSON] et al. 's scheme takes 0.863 ms as shown in Figure 2.  
This reduction in computation cost is caused by the characteristic of the trusted execution environment, especially Intel SGX in our scheme. Previous PEKS schemes [5,12] are constructed based on the pairing based cryptographic operations which leads to high computation overhead. For instance, in \(Trapdoor\) algorithm, our proposed scheme uses AES-GCM that is included in the SGX SDK for encryption and decryption of search query. Compared to pairing-based operations, AES-GCM is much more efficient cryptographic primitive. In addition, For _Search_ algorithm, previous schemes utilize the pairing-based cryptography for searching over ciphertext.