# Substring Position Search over Encrypted Cloud Data Supporting Efficient Multi-User Setup +
## 5 Substring Position Searchable Symmetric Encryption
### SSP-SSE Construction
#### Setup Phase  
The setup phase (Algorithm 2) includes the KeyGen, the BuildTree and the Encrypt algorithms. Let \(k\) be a security parameter, and let SKE = (Gen, Enc, Dec) be a PCPA-secure symmetric-key encryption scheme. The data owner begins with the KeyGen algorithm that inputs a secret parameter \(k\) and outputs a set of keys \(K_{1}\), \(K_{X}\), \(K_{Y}\), \(K_{V}\) and set of random keys \(K_{Q}\), \(K_{L}\), \(K_{2}\),\(K_{3}\leftarrow\{0,1\}^{k}\). He will use these keys to encrypt the document collection \(D=(D_{1},\ldots,D_{l})\) and construct searchable index \(l\). First, the data owner constructs a position heap tree \(\Lambda\) using the BuildTree algorithm outlined in Definition 10. The BuildTree algorithm inputs the text \(t\), where \(t\) is constructed from the document collection \(D=D_{1}||\$\ldots\$\ ||D_{l}\) padded with the unique terminator string \(\$\) and outputs the single position heap tree \(\Lambda\). In order to handle multiple documents in the collection, the data owner adds auxiliary information to each node that contains the document identifier \(D_{i}\) and the position of the letter in \(D_{i}\). For example, if the character \"a\" appears in the document \(D_{1}\) at Position 1, the node in \(\Lambda\) will have extra information of \(pid(D_{1})=id(D_{1})||1\). Formally, we concatenate the identifier of \(D_{j}\) (\(j\in[1;l]\)) with position \(i\) of character \(t_{i}\) in the document \(D_{j}\), i.e., \(pid(D_{j})=id(D_{j})||pos_{D_{j}}\), and add this information in each node in the position heap tree. Figure 2(a) shows an example of position heap tree \(\Lambda\) of the text \"ab$aaa$bb\" constructed from three concatenated documents \((D_{1},D_{2},D_{3})\), where \(D_{1}\) has text \"bb\", \(D_{2}\) has text \"aaa\" and \(D_{3}\) has text \"ab\". Note, a search of \"ab\" in the position heap tree returns a set of nodes \((9,4,1)\) where only 9 is the matching node, and it describes the document position of \(D_{3}||2\). Thus, the search query \"ab\" appears only in the document \(D_{3}\) at Position 2. Let \(SKE=(Gen,\,Enc,\,Dec)\) be a PCPA-secure symmetric-key encryption scheme; let \(F:\{0,1\}^{k}\)\(\times\)\(\{0,1\}^{*}\)\(\rightarrow\)\(\{0,1\}^{k}\) be a PRF; and let \(P:\{0,1\}^{k}\times\)\(\{0,1\}^{n}\)\(\rightarrow\)\(\{0,1\}^{n}\) be a PRP. **SETUP PHASE. **  
\(KeyGen(1^{k}):\) given the security parameter \(k\), generate \(K_{1},\,K_{X},\,K_{Y},\,K_{V}\gets SKE.Gen(1^{k})\) and \(K_{Q}\), \(K_{L},\,K_{2},K_{3}\)\(\stackrel{{ R}}{{=}}\)\(\{0,1\}^{k}\). Output the key set \(K=(K_{1},\,K_{X},\,K_{Y},\,K_{Q},\,K_{L},\,K_{2},K_{3})\). \(BuildTree(D):\) given the document collection \(D=(D_{1},\,\ldots,\,D_{l})\):  
1. construct text \(t=t_{1}t_{2}\ldots t_{n}\) from document collection \(D\), and and input \(t\) of size \(n\) to build the position heap tree \(\Lambda\). 2. index into \(\Lambda\), for each node \(v[i]\) (\(i\in[1,\,n]\)): 1. set \(V(v[i])=pid(D_{j})||V(v[i])\), where \(D_{j}\) (\(j\in[1,l]\)) is the document in collection \(D\). 3. output the position heap tree \(\Lambda\)  
\(Encrypt(K,\Lambda,D):\) given the secret key set \(K\), position heap tree \(\Lambda\) and the set of documents \(\overline{D=(D_{1},\,\ldots,\,D_{l})}\). Build encrypted tree:  
1. index into \(\Lambda\), traverse from the root node:
2. for each node \(v[i]\) (\(i\in[1,\,n]\)): 1. set \(\overline{L(\overline{v[i]})}=F_{K_{Q}}(L(v[i])||depth(v[i])||\overline{L_{ parent}(\overline{v[i]})}||K_{L})\) (i.e., apply PRF \(F\) with key \(K_{Q}\) on the concatenation of the path label \(L\) of \(v[i]\), depth of the node \(v[i]\), encrypted parent label \(\overline{L_{parent}}\) of \(v[i]\) and the secret key \(K_{L}\). 2. set \(\overline{V(\overline{v[i]})}=SKE.Enc_{K_{V}}(i)\). 3. output encrypted \(\bar{\Lambda}\). Build encrypted arrays:  
1. for each character \(t_{i}\) of \(t\) indexed from right-to-left (i.e., \(t_{n}t_{n-1}\ldots t_{1}\)), set an array \(X[P_{K_{2}}(i)]=SKE.Enc_{K_{X}}(t_{i})\).