# Substring Position Search over Encrypted Cloud Data Supporting Efficient Multi-User Setup +
## 5 Substring Position Searchable Symmetric Encryption
### SSP-SSE Construction
#### Setup Phase
2. for each \(i=[1,\,n]\): set an array \(Y[P_{K_{3}}(i)]=SKE.Enc_{K_{Y}}(V(v[i]))\). Encrypt document collection:  
1. for each document \(D_{i}\) where \(i\in[1,l]\), let \(C_{i}\gets SKE.Enc_{K_{1}}(D_{i})\). 2. output \(C=(C_{1},\,C_{2},\,\ldots,\,C_{l})\). Output: index \(I=(\bar{\Lambda},\,X,\,Y)\) and encrypted document collection \(C=(C_{1},\,C_{2},\,\ldots,\,C_{l})\). Figure 3: An example of the position heap tree. (**a**) Constructed from the text “ab5 aaa5 bb”extracted from documents \((D_{1},\,D_{2},\,D_{3})\); **(b**) constructed from the text “abaaababbaabaa”. The data owner constructs the searchable index that is based on the position heap tree data structure. To present the details, we use an example of the position heap tree \(\Lambda\) shown in Figure 3b. The figure depicts constructed position heap tree \(\Lambda\) from text \(t=\)\"abaaababbabaabaaba\" and text array \(X\) (shown at the top of the figure), where each array element has a single character of text \(t\) indexed from right-to-left. The data owner begins by extracting position information from \(\Lambda\) as follows: index each node in tree \(\Lambda\), and create a position array \(Y\), such that each index in \(Y\) corresponds to the node value of \(\Lambda\). Figure 4a shows an example of the left-side branch of position heap tree \(\Lambda\) and constructed position array \(Y\). In this example, nodes in \(\Lambda\) are marked with the red color index, and their corresponding values (positions) are stored as elements in \(Y\). (In Figure 4a we show an example of the position array \(Y\) for nine nodes of \(\Lambda\) for demonstration purposes only. The actual algorithm is executed on all nodes in \(\Lambda\).) With this, the data owner is ready to encrypt the position heap tree \(\Lambda\), text array \(X\) and position array \(Y\) data structures. First, to encrypt the position heap tree \(\Lambda\), the data owner uses a pseudorandom function \(F:\{0,1\}^{k}\times\{0,1\}^{*}\rightarrow\{0,1\}^{k}\) and PCPA-secure symmetric-key encryption scheme SKE = (Gen, Enc, Dec). For each node \(i\) in \(\Lambda\), the data owner applies PRF \(F\) with key \(K_{Q}\) on the concatenation of the path label of node \(i\), depth of the node \(i\), the encrypted path label of the \(i^{\prime}\)-th parent node and the secret key \(K_{L}\). Figure 4b shows an example of the path label encryption. For instance, the label of Node 4 is \(L_{4}=F_{K_{Q}}(a||3||L_{3}||K_{L})\), where \(L_{3}=F_{K_{Q}}(a||2||L_{2}||K_{L})\). The root path label is a special case, and its label is \(L_{1}=K_{K_{Q}}(a||0||\mathcal{O}||K_{L})\). In this way, the data owner encrypts all path labels in the tree. This hides the plaintext path labels of the same character at different levels of the tree \(\Lambda\). Moreover, this makes the ciphertext unique for all path labels in the tree. To hide the index information of each node in \(\Lambda\), the data owner uses SKE encryption with key \(K_{V}\) on the index of the node, i.e., \(V_{i}=SKE.Enc_{K_{V}}(i)\), where \(i\in[1,n]\). For instance, the value of Node 8 is \(V_{8}=SKE.Enc_{K_{V}}(8)\). With no plaintext left in \(\Lambda\), the data owner outputs an encrypted position heap tree \(\bar{\Lambda}\). Second, the data owner utilizes a pseudorandom permutation \(P:\{0,1\}^{k}\times\{0,1\}^{n}\rightarrow\{0,1\}^{n}\) and PCPA-secure symmetric-key encryption SKE to hide plaintext elements of text array \(X\) and position array \(Y\). For each \(i\) (\(i\in[1,n]\)) in \(X\), the data owner applies PRP \(P\) with secret key \(K_{2}\) on each \(i\), i.e., \(P_{K_{2}}(i)\). For each corresponding character \(t_{i}\) at index \(i\) in \(X\), he applies SKE with secret key \(K_{X}\) on character \(t_{i}\), i.e., \(SKE.Enc_{K_{X}}(t_{i})\). The data owner sets the encrypted array \(X\) as \(X[P_{K_{2}}(i)]=SKE.Enc_{K_{X}}(t_{i})\).