# Substring Position Search over Encrypted Cloud Data Supporting Efficient Multi-User Setup +
## 7 Multi-User Substring Position Searchable Symmetric Encryption
### MSSP-SSE Construction  
Algorithm 5 shows the details of our multi-user scheme MSSP-SSE = (KeyGen, BuildTree, Encrypt, Join, GroupSetup, Remove, ConstructQuery, Search, Decrypt). Let SSP-SSE = (KeyGen, BuildTree, Encrypt, ConstructQuery, Search, Decrypt) be a single-user substring position searchable symmetric encryption scheme. Let BE-NIKE-WPRF = (Setup, Join, Enc, Dec) be a distributed broadcast encryption scheme. We require standard security notions for broadcast encryption, i.e., in addition to providing PCPA-security, it provides revocation-scheme security against a group of revoked users. Let \(\rho\) be a pseudorandom permutation, such that \(\rho\): \(\{0,1\}^{k}\times\{0,1\}^{t}\rightarrow\{0,1\}^{t}\) (\(\rho\) can be constructed as a pseudorandom permutation over domains of arbitrary size[37]), where \(t\) is the size of search query \(Q\) in the SSP-SSE scheme. We assume that the cloud server does not collude with revoked users; otherwise, our construction cannot prevent a revoked user from invoking the search. ```
\(KeyGen(1^{k})\) :
1. generate \(K\gets SSP\)-\(SSE\).\(KeyGen(1^{k})\). 2. generate \(\lambda\), \(g\gets BE\)-\(NIKE\)-\(WPRF\).\(Setup(1^{k})\). Output the key set \(K\), secret parameter \(\lambda\) and group \(g\). \(BuildTree(D)\) :

Given a document collection \(D=\{D_{1},\ldots,D_{l}\}\), output \(\Lambda\leftarrow SSP\)-\(SSE\).\(BuildTree(D)\). \(Encrypt(K,\Lambda,D)\) :

1. set \((I,C)\leftarrow SSP\)-\(SSE\).\(Encrypt(K,\Lambda,D)\). Output \((I,C)\). \(Join(\lambda,g)\) :

1. generate \((sk,(z,ek))\leftarrow BE\)-\(NIKE\)-\(WPRF\).\(Join(\lambda,g)\). Keep \(sk\) private; output \((z,ek)\) to the cloud server. \(GroupSetup(\{z_{i},ek\}_{i\in[h]},sk)\) :

1. pick \(h\subseteq g\) and get public values \(\{z_{i},ek_{i}\}_{i\in[h]}\) from the cloud server. 2. sample \(r\leftarrow\{0,1\}^{s}\) and compute \(c_{r}\gets BE\)-\(NIKE\)-\(WPRF\).\(Enc(\{z_{i},ek_{i}\}_{i\in[h]},sk,r)\). Output \(c_{r}\) to the cloud server. \(Remove(\{z_{i},ek_{i}\}_{i\in[h\setminus o]},sk)\)
```  
**Algorithm 5**MSSPSPSP construction:  
We now describe the scheme using the following hospital example. Consider a doctor (data owner) that performed a set of early cancer screening tests on a patient and wishes to share the resulting documents with a group of hospital nurses (data users). To remove the burden of key management, the doctor enables a distributed setup, where each nurse generates his or her own secret key and establishes a group of authorized participants that includes a head nurse and his or her subordinate nurses. First, the doctor samples the secret parameter \(k\) and generates the set of encryption keys \(K\), secret key \(\lambda\) and group \(g\) for the distributed broadcast encryption. Second, the doctor encrypts the resulted documents with PCPA-secure symmetric encryption scheme SKE and outputs the searchable index \(I\) to the cloud server. Next, each participating nurse invokes the Join algorithm with secret \(\lambda\), group \(g\) (both distributed by the doctor) to generate \((sk,(z,ek))\), where secret \(sk\) is kept private and \((z,ek)\) are published to the cloud server. Now, the head nurse (group owner) creates a group of authorized users that are allowed to invoke a search over encrypted documents in the cloud. The head nurse launches the GroupSetup algorithm,where she selects public values \(\{z_{i},ek_{i}\}_{i\in h}\) of authorized participants \(h\in g\), samples random secret parameter \(r\) and invokes the distributed broadcast encryption to output \(c_{r}\). In order to search for a substring \(\chi\), the authorized nurse first contacts the cloud provider to receive the latest ciphertext \(c_{r}\) and invokes distributed broadcast encryption with his or her own secret \(sk\), public values \(\{z_{i},ek_{i}\}_{i\in h}\) to recover secret \(r\). If \(r\) is successfully recovered, the nurse then constructs a single-user search query \(Q^{\prime}\), encrypts it with pseudorandom permutation \(\rho\) with \(r\) and outsources \(\rho_{r}(Q^{\prime})\) to the cloud provider.