# Substring Position Search over Encrypted Cloud Data Supporting Efficient Multi-User Setup +
## 7 Multi-User Substring Position Searchable Symmetric Encryption
### Preliminaries  
In this section, we present several definitions used in our work. We begin with the definition of the Witness Pseudo-Random Function (WPRF). Informally, a witness PRF for an \(NP\) language \(L\) is a PRF \(F\), such that anyone with a valid witness that \(x\in L\) can compute \(F(x)\) without the secret key, but for all \(x\
ot\in L\), \(F(x)\) is computationally hidden without knowledge of the secret key. Formally, a witness PRF is defined as follows. **Definition 20**: **(Witness Pseudo-Random Function (WPRF) [36]). ** A triple of algorithms \((Gen,F,Eval)\) is a witness PRF if:  
Figure 5: Experimental results. (**a**) The construction of the position heap tree; (**b**) the searchable index storage. * _Gen_: a probabilistic algorithm that inputs a security parameter \(\lambda\) and a circuit \(R:\mathbb{X}\times\mathbb{W}\rightarrow\{0,1\}\), and outputs a secret function key \(fk\) and a public evaluation key \(ek\). * \(F\): a deterministic algorithm that inputs the function key \(fk\) and an input \(x\in\mathbb{X}\) and outputs some output \(y\in\mathbb{Y}\) for some set \(\mathbb{Y}\). * _Eval_: a deterministic algorithm that inputs the evaluation key \(ek\), an input \(x\in\mathbb{X}\) and a witness \(w\in\mathbb{W}\) and that produces an output \(y\in\mathbb{Y}\) or \(\bot\). A witness PRF is correct if the following holds:  
\[Eval(ek,x,w)= \begin{cases}F(fk,x)&\text{if }R(x,w)=1\\ \bot&\text{if }R(x,w)=0\end{cases} \text{for all }x\in\mathbb{X},w\in\mathbb{W}. \tag{6}\]  
A multiparty key exchange protocol allows a group of \(g\) users to simultaneously post a message to a public bulletin board, retaining some user-independent secrets. After reading off the contents of the bulletin board, all users establish the same shared secret key. The multiparty key exchange protocol consists of the following algorithms. Definition 21: **(Non-Interactive Multiparty Key Exchange protocol (NIKE-WPRF) [36]). ** Let \(G:\mathbb{S}\rightarrow\mathbb{Z}\) be a pseudo-random generator with \(|S|/|Z|\leq negl\). Let \(WPRF=(Gen,F,Eval)\) be a witness PRF. Let \(R_{g}:\mathbb{Z}^{g}\times(\mathbb{S}\times[g])\rightarrow\{0,1\}\) be a relation that outputs one on input \(((z_{1},\ldots,z_{g}),(s,i))\) if and only if \(z_{i}=G(s)\). The non-interactive key exchange protocol consists of:  
* _Publish_(\(\lambda,g\)): a probabilistic algorithm to output public and secret keys. The algorithm inputs the security parameter \(\lambda\) and the group order \(g\). It computes \((fk,ek)\stackrel{{ R}}{{\leftarrow}}Gen(\lambda,R_{g})\). Next, it picks a random seed \(sk\stackrel{{ R}}{{\leftarrow}}\mathbb{S}\) and computes \(z\gets G(sk)\). It outputs a secret key \(sk\) and public values \((z,ek)\), where \(sk\) is kept secret and \((z,ek)\) are published to the bulletin board. * \(KeyGen(\{z_{i},ek_{i}\}_{i\in[g]},sk)\): a deterministic algorithm that inputs group \(g\) and user's secret \(sk\). It outputs a group key \(k=Eval(ek_{i},(z_{1},\ldots,z_{g}),(sk,i))\). Broadcast encryption [35] allows an encryptor (data owner) to broadcast a message to a subset of recipients (data users). The system is said to be collusion resistant if non-data users can learn information about the plaintext. The most recent work by [PERSON] et al. [36] proposes a distributed broadcast encryption scheme that removes the burden of key management from the encryptor and lets group establishment run by participating recipients. Each user is allowed to pick the desired participants and to establish a shared key. The distributed broadcast encryption scheme is defined as follows. Definition 22: **(Distributed Broadcast Encryption over NIKE (BE-NIKE-WPRF) [36]). ** The distributed broadcast encryption scheme over multi-party non-interactive key exchange protocol consists of the four following algorithms:  
1. _Setup_: a probabilistic algorithm to setup the BE-NIKE-WPRF scheme. The algorithm outputs a secret parameter \(\lambda\) and group order \(g\). 2.