# SPEKS: Forward Private SGX-Based Public Key Encryption with Keyword Search
## 5 Analysis  
### Security Analysis  
We will prove the security of our scheme by defining the leakage functions related to access pattern. Then, we will explain how our SPEKS scheme guarantees the forward privacy. We define two leakage functions: \(\mathcal{L}_{PEKS}\left(sc\right)\) and \(\mathcal{L}_{hw}\left(sc,\mathcal{R}\right)\). \(\mathcal{L}_{PEKS}\left(sc\right)\) function outputs a record \(\mathcal{R}\) given the search counter \(sc\), which consists of encrypted data, indices, and searchable ciphertexts. Given \(sc\) and \(\mathcal{R}\), \(\mathcal{L}_{hw}\left(sc,\mathcal{R}\right)\) function outputs the access pattern \(\mathcal{P}\left(sc,\mathcal{R}\right)\). The access pattern \(\mathcal{P}\left(sc,\mathcal{R}\right)\) contains information of search counter \(sc\) and records \(\mathcal{R}\), which are stored in the untrusted memory region of the server. When the data receiver requests \(sc\), the server can see which value is being returned. \(\mathcal{R}\) also leaks which record is being sent to enclave or the data receiver. In our analysis, we further utilize values access pattern \(\Delta\left(sc,\mathcal{R}\right)\)[13], which, in our analysis, describes the pointers to the result values that specifically points the record with index \(ind\). **Theorem 1**: _(Security). The SPEKS construction is \(\left(\mathcal{L}_{PEKS},\mathcal{L}_{hw}\right)\)-secure._  
Proof: We consider a polynomial-time simulator \(\mathcal{S}\) for which probabilistic, polynomial-time adversary \(\mathcal{A}\) can distinguish between \(\textbf{Real}_{\mathcal{A}}(\lambda)\) and \(\textbf{Ideal}_{\mathcal{A}\mathcal{S}}(\lambda)\) with negligible probability. * _Setup_: \(\mathcal{S}\) creates a new random keys \(\left(\tilde{PK},\tilde{SK},\tilde{K}\right)=Setup(1^{\lambda},\lambda)\) and stores them. * _Simulating_\(\mathcal{R}\): \(\mathcal{S}\) gets \(\mathcal{L}_{PEKS}\) and receives search counter sc. Furthermore, \(\mathcal{S}\) creates \(\left|F\right|\) (the size of data set) encryption of keyword \(\text{C}=\left(\text{C}_{1}\text{,..., }\text{C}_{\left|F\right|}\right)\) using \(\textit{Enc}_{\textit{PKE}}\left(PK,\left(w,sc\right)\right)\). All encrypted value is given a distinct index value \(ind\). \(\mathcal{S}\) outputs \(\mathcal{R}=\left(ind_{i},\text{C}_{i}\right)\). Since the value of search counter and the size of the record are included in the leakage, the operations above are possible. The simulation of \(\mathcal{R}\) has the same size with the output of \(\textbf{Real}_{\mathcal{A}}(\lambda)\). In addition, the simulation result is indistinguishable from the output of \(\textbf{Real}_{\mathcal{A}}(\lambda)\) due to IND-CPA-security of public key encryption scheme. * _Simulating_\(t_{w}\): The simulator \(\mathcal{S}\) creates value \(\tau_{w}=\left(w,sc\right)\) and encryppts it as \(\textit{Enc}_{\textit{SKE}}(K_{u},\tau_{w})\). \(\mathcal{S}\) outputs search token \(t_{w}\). Since \(\textit{Enc}_{\textit{SKE}}\) is IND-CPA secure, the simulated \(t_{w}\) is indistinguishable from the output of \(\textbf{Real}_{\mathcal{A}}(\lambda)\). * _Simulating secure hardware_: At a given time \(t\), \(\mathcal{S}\) receives search token and \(\mathcal{L}_{hw}\). \(\mathcal{S}\) uses \(\mathcal{P}\left(sc,\mathcal{R},t\right)\) to simulate the access pattern. \(\mathcal{S}\) begins with the first record of \(\mathcal{P}\) and follows the indices given by \(\mathcal{R}\). The leakage \(\Delta\) determines the specific point of the record with index \(ind\). The adversary \(\mathcal{A}\) cannot distinguish access of \(\textbf{Real}_{\mathcal{A}}(\lambda)\) from simulated access due to the delivering of deterministic results. The results are consistent for each different requests made for the same keyword. Since \(\Delta\left(sc,\mathcal{R}\right)\) is explicit, the number of result pointers matches and the pointers are also consistent. The pointed values are indistinguishable, because those values are encrypted IND-CCA secure. **Forward Privacy**.