# SPEKS: Forward Private SGX-Based Public Key Encryption with Keyword Search
## 3 SPEKS Overview and Definitions
### Algorithms and Security Definitions  
SPEKS consists of four polynomial-time algorithms: \(SPEKS=(Setup(1^{\lambda},\lambda)\), \(PEKS(PK_{u},w,u,F)\), \(Trapdoor(K_{u},w,sc[u])\), \(Search(SK_{u},\mathcal{R},t_{w}))\). **Definition 1**. : _(SPEKS). A secure SPEKS is a tuple of four polynomial-time algorithms (Setup, PEKS, Trapdoor, Search) as follows:_  
* \((PK_{u},SK_{u},K)\leftarrow Setup(1^{\lambda},\lambda)\)_: It takes the security parameter_ \(1^{\lambda}\) _as input for generating a key pair for private key_ \(SK_{u}\) _and public key_ \(PK_{u}\)_, and takes_ \(\lambda\) _as input for generating symmetric key_ \(K_{u}\)_._
* \(t_{w}\leftarrow Trapdoor(K_{u},w,sc[u])\)_: It takes the symmetric key_ \(K_{u}\)_, keyword_ \(w\)_, and search counter_ \(sc[u]\) _as input. It then outputs encrypted search token_ \(t_{w}\)_._
* \(\mathcal{R}\leftarrow PEKS(PK_{u},w,u,F)\)_: It takes the public key_ \(PK_{u}\)_, keyword_ \(w\)_, user index_ \(u\)_, and a set of data_ \(F\) _as input. It then outputs a record_ \(\mathcal{R}\)_._
* \((F\ /\ \bot)\leftarrow Search(SK_{u},\mathcal{R},t_{w})\)_: It takes the private key_ \(SK_{u}\)_, record_ \(\mathcal{R}\)_, and search token_ \(t_{w}\) _as input. It then outputs_ \(F\) _if there is a match; otherwise,_ \(\bot\)_._  
Figure 1: High level design overview. **Definition 2**. : _(Correctness) Let \(\mathcal{D}\) denote a SPEKS-scheme consisting of the four algorithms described in Definition 1. For any correctly generated public key pair \((PK,SK)\) and symmetric \(K\) of the data receiver, and for any keyword \(w\), \(\text{Search}(SK_{u},\mathcal{R},t_{w})=1\) holds with probability \(1\), where ciphertext \(\mathcal{R}\gets PEKS(PK_{u},w,u,F)\) and \(t_{w}\gets Trapoor(K_{u},w,sc[u])\)._  
We define our security model based on the three steps framework introduced in [16]. For the first step, we need to formulate a leakage which means an upper bound of the information that an adversary may gather from the protocol. Second step is defining the \(\mathbf{Real}_{\mathcal{A}}(\lambda)\) and \(\mathbf{Ideal}_{\mathcal{A},\mathcal{S}}(\lambda)\) games for an adaptive adversary \(\mathcal{A}\) and a polynomial-time simulator \(\mathcal{S}\). \(\mathbf{Real}_{\mathcal{A}}(\lambda)\) is the actual protocol and \(\mathbf{Ideal}_{\mathcal{A},\mathcal{S}}(\lambda)\) is the simulated protocol for the real game by utilizing \(\mathcal{S}\) using only the formulated leakage. Information learned in the previously executed protocols can be used by an adaptive adversary for its subsequent queries. Third step is proving that a scheme is CKA2-secure by showing that \(\mathcal{A}\) can distinguish the outputs of the games with probability close to \(0\). When the probability is negligibly close to \(0\), \(\mathcal{A}\) does not learn anything more than just the leakage stated in the first step. Similar to the scheme introduced by [PERSON] et al. [13], our scheme has an additional transaction between the cloud server and the trusted hardware, SGX. This additional transaction can be monitored by the adversary; therefore, we extended the original security model to hardware-security model. \(\mathcal{L}_{hw}\) denotes the leakage on the CKA2-HW-security. **Definition 3**. : _(CKA2-HW-security). Let \(\mathcal{D}\) denote a SPEKS scheme consisting of the four algorithms described in Definition 1. \(\mathcal{A}\) is a stateful passive adversary, and \(\mathcal{S}\) is a stateful simulator that gets the leakage functions \(\mathcal{L}_{PEKS}\) and \(\mathcal{L}_{hw}\). Two probabilistic experiments \(\mathbf{Real}_{\mathcal{A}}(\lambda)\) and \(\mathbf{Ideal}_{\mathcal{A},\mathcal{S}}(\lambda)\) are described as a follow._  
* \(\mathbf{Real}_{\mathcal{A}}(\lambda)\)_: The data receiver runs Setup_ \(\left(1^{\lambda},\lambda\right)\) _and generates a key pair_ \((PK,SK)\) _and symmetric key_ \(\mathcal{A}\) _outputs a search counter of user,_ \(sc[u]\)_. The data sender calculates_ \(\mathcal{R}\gets PEKS(PK_{u},w,u,F)\) _and passes_ \(\mathcal{R}\) _to_ \(\mathcal{A}\)_.