# SPEKS: Forward Private SGX-Based Public Key Encryption with Keyword Search
## 4 Construction
### Algorithms  
The proposed forward secure searchable encryption scheme with keyword search (SPEKS) consists of the following four algorithms: (Setup, PEKS, Trapdoor, Search).  
Algorithm 1 gives a formal description of Setup of our SPEKS scheme. In \((PK_{u},SK_{u},K)\gets Setup(1^{\lambda},\lambda)\) algorithm, a data receiver (DR) generates \(PK_{u}\), \(SK_{u}\), and \(K_{u}\). Next, the DR provisions the \(SK_{u}\) and \(K_{u}\) to the enclave within the cloud server, \(Enclave_{CS}\), through a secure channel. The secure channel can be established by the attestation feature provided by Intel SGX as explained in Section 4.2.  
Next, Algorithm 2 provides a formal description of PEKS. In \(\mathcal{R}\gets PEKS(PK_{u},w,u,F)\), where F denotes a set of data, a data sender (DS) first requests search counter \(sc[u]\) from the cloud server (CS). Using the retrieved \(sc[u]\), the DS runs \(Enc_{PKE}(PK_{u},(w,sc[u]))\) and generates searchable ciphertext \(ct\). A record \(\mathcal{R}\) consists of three components \((d,ind,ct)\), where \(d\) refers to the data, \(ind\) refers to the index, and \(ct\) refers to the searchable ciphertext. The generated record \(\mathcal{R}\) is sent to the CS.  
Algorithm 3 describes the Trapdoor algorithm of our scheme. In the algorithm, the DR creates a search token with the keyword. Specifically, in the execution of \(t_{w}\gets Trapdoor(K_{u},w,sc[u])\), the DR uses the search counter \(sc[u]\) and keyword, and generates the search token. Then, using symmetric key encryption (SKE), the DS encrypts the search token with symmetric key \(K\). The encrypted search token \(t_{w}\) is now transferred to Enclave\({}_{CS}\). After transferring the search token, the DR increments his or her own search counter by 1.  
Algorithm 4 describes the Search algorithm of our scheme. In Algorithm 4, Enclave\({}_{CS}\) checks whether search token \(t_{w}\) matches \(\mathcal{R}\). Enclave\({}_{CS}\) runs \(Dec_{SKE}\left(K_{u},t_{w}\right)\) and retrieves keyword \(w^{\prime}\) and search counter \(sc^{\prime}\). Next, using the key \(SK\), keyword \(w\) and search counter \(sc\) are retrieved from the ciphertext \(ct_{i}\). The \(ind_{i}\) from \(\mathcal{R}\) is returned. \(sc[u]\) is then incremented by one, and \(F\) with returned \(ind_{i}\) is returned to the DR, when matched; else, \(\bot\) is returned.  
```
DR: \((PK_{u},SK_{u})\gets Setup(\lambda)\)  Symmetric key \(K_{u}\gets Setup(1^{\lambda})\)  Provision Private Key \(SK_{u}\) and Symmetric \(K_{u}\) to \(Enclave_{CS}\)
```  
**Algorithm 1**\((PK_{u},SK_{u},K)\gets Setup(1^{\lambda},\lambda)\)  
```
DS:  Request the search counter of \(u\) from the CS CS:  Return \(sc[u]\) to DS DS: for\(i=1\) to \(|F|\)do \(ct_{i}\leftarrow\text{Enc}_{PKE}(PK_{u}(w,sc[u]))\) \(\mathcal{R}\leftarrow\mathcal{R}\cup\{(d_{i},ind_{i},ct_{i})\}\) endfor  Transfer \(\mathcal{R}\) to CS CS: for\(i=1\) to \(|\mathcal{R}|\)do \(ED\gets ED\cup\{(d_{i},ind_{i},ct_{i})\}\) endfor
```  
**Algorithm 2**\(\mathcal{R}\gets PEKS(PK_{u},w,u,F)\)  
```
DS:  Request the search counter of \(u\) from the CS CS CS:  Return \(sc[u]\) to DS DS: for\(i=1\) to \(|F|\)do \(ct_{i}\leftarrow\text{Enc}_{PKE}(PK_{u}(w,sc[u]))\) \(\mathcal{R}\leftarrow\mathcal{R}\cup\{(d_{i},ind_{i},ct_{i})\}\) endfor  Transfer \(\mathcal{R}\) to CS CS CS: for\(i=1\) to \(|\mathcal{R}|\)do \(ED\gets ED\cup\{(d_{i},ind_{i},ct_{i})\}\) endfor
```  
**Algorithm 3**\(t_{w}\gets Trapdoor(K_{u},w,sc[u])\)  
```
DS: \(\tau_{w}\leftarrow(w,sc[u])\) \(t_{w}\gets Enc_{SKE}(K_{u},\tau_{w})\)  Transfer \(t_{w}\) to \(Enclave_{CS}\) \(sc[u]\gets sc[u]+1\)
```  
**Algorithm 4**\((F/\perp)\gets Search(SK_{u},\mathcal{R},t_{w})\)  
```
CS: \(\text{Enclave}_{CS}:\) \((w^{\prime},sc^{\prime})\gets Dec_{SKE}\left(K_{u},t_{w}\right)\) for i=1 to sc'do \((w,sc)\gets Dec_{PKE}\left(SK_{u},ct_{i}\right)\) if\((w=w^{\prime})\)and\((i=sc)\)then return\(ind_{i}\) endif endfor \(sc[u]\gets sc[u]+1\)  Return \(F\) to DR if match; else, \(\perp\)
```  
**Algorithm 5**\((F/\perp)\gets Search(SK_{u},\mathcal{R},t_{w})\)