# Substring Position Search over Encrypted Cloud Data Supporting Efficient Multi-User Setup +
## 7 Multi-User Substring Position Searchable Symmetric Encryption
### Algorithm Definitions  
**Definition 23**. : _(Multi-User Substring Position Searchable Symmetric Encryption (MSSP-SSE))._ A tree-based MSSP-SSE scheme over a set of documents \(D\) is a tuple of nine polynomial-time algorithms (KeyGen, BuildTree, Encrypt, Join, GroupSetup, Remove, ConstructQuery, Search, Decrypt), as follows:  
1. \((K,\lambda,g)\gets KeyGen(1^{k})\): a probabilistic key generation algorithm to setup the SSP-SSE scheme. The algorithm takes a secret parameter \(k\) and outputs a set of secret keys \(K\), secret parameter \(\lambda\) and group \(g\). 2. \((\Lambda)\gets BuildTree(D)\): a deterministic algorithm to build a position heap tree \(\Lambda\). The algorithm takes a document collection \(D=\{D_{1},\ldots,D_{l}\}\) and constructs a position heap tree \(\Lambda\). 3. \((I,C)\gets Encrypt(K,\Lambda,D)\): a probabilistic algorithm to encrypt a position heap tree and document corpus. The algorithm inputs a set of secret keys \(K\), a position heap tree \(\Lambda\) and a documents corpus \(D\). The output of algorithm is a searchable index \(I\) and encrypted collection \(C=\{C_{1},\ldots,C_{l}\}\). 4. \((sk,(z,ek))\gets Join(\lambda,g)\): a probabilistic algorithm run by each data user to participate in the scheme. The algorithm invokes _BE-NIKE-WPRF.Join_ with an input of secret parameter \(\lambda\) and group order \(g\). It outputs a pair \((sk,(z,ek))\). 5. \(c_{r}\gets GroupSetup(\{z_{i},ek_{i}\}_{i\in[h]},sk)\): a probabilistic algorithm run by the group owner to establish the group \(h\subseteq g\) of authorized data users. The algorithm runs _BE-NIKE-WPRF.Enc_ with an input of public values \(\{z_{i},ek_{i}\}_{i\in[h]}\), group owner's secret key \(sk\) and a sampled secret \(r\). The output is encrypted ciphertext \(c_{r}\). 6. \(c_{r}\gets Remove(\{z_{i},ek_{i}\}_{i\in[h\setminus o]},sk)\): a probabilistic algorithm run by the group owner to remove a user \(o\) from the set of authorized users. The algorithm invokes _BE-NIKE-WPRF.Enc_ that inputs the set of public values \(\{z_{i},ek_{i}\}_{i\in[h\setminus o]}\), group owner's secret key \(sk\) and a new secret \(r\). The output is encrypted ciphertext \(c_{r}\). 7. \([(Q)\gets ConstructQuery(K,\chi,c_{r})]\leftrightarrow[(L)\gets Search (I,Q,c_{r})]\): two deterministic algorithms that are executed interactively between the authorized cloud user and the cloud provider. The algorithm inputs a set of secret keys \(K\), ciphertext \(c_{r}\) and a substring \(\chi\), and it outputs a search query \(Q\). The algorithm uses a query \(Q\), searchable index \(I\) and ciphertext \(c_{r}\). It outputs a sequence of identifiers \(L\in C\). 8. \((D_{i},pos_{D_{i}})\gets Decrypt(K,C_{i})\): a deterministic algorithm that takes a set of secret keys \(K\) and a ciphertext \(C_{i}\) as input, and it outputs an original document \(D_{i}\), \(\forall i\in[1;n]\), and a set of \(\chi\)'s positions \(pos_{D_{i}}\) in \(D_{i}\). We now present the security model for a Multi-user Substring Position Searchable Symmetric Encryption (MSSP-SSE) scheme. Intuitively, our security model requires the security of a single-user SSP-SSE scheme and the security of a distributed broadcast encryption scheme. We formalize the security requirements of MSSP-SSE scheme as follows:  
* Given searchable index \(I\) and the set of encrypted documents \(C=\{C_{1},\ldots,C_{l}\}\), the adversary should learn nothing about the original document collection \(D=\{D_{1},\ldots,D_{l}\}\). * Given the set of incoming search queries \(Q=\{Q_{1},\ldots,Q_{m}\}\), access pattern, search pattern and path pattern, the adversary should learn nothing about the content of each search query \(Q_{i}\) or the content of resulted documents. * Once a user is removed from the set of authorized cloud users, he/she is no longer allowed to invoke a search over encrypted documents in the cloud. Thus, we require the revocation of the cloud users. In MSSP-SSE, we use the adaptive semantic security notion of a single-user SSP-SSE scheme.