# Substring Position Search over Encrypted Cloud Data Supporting Efficient Multi-User Setup +
## 5 Substring Position Searchable Symmetric Encryption
### SSP-SSE Construction
#### 5.3.2 Search Phase  
The search phase (Algorithm 3) includes both the ConstructQuery and the Search interactive algorithms that are executed between the cloud user and the cloud provider. The cloud user keeps the set of secret keys \(K=(K_{1},K_{X},K_{Y},K_{V},K_{Q},K_{L},K_{2},K_{3})\) received from the data owner. In order to search a substring \(\chi\) of length \(m\), the cloud user begins with creating a search query \(Q\): for each character \(\chi_{i}\) in \(\chi\); he applies PRF \(F\) with secret key \(K_{Q}\) on the concatenation of \(\chi_{i}\), \(i\), the output of previous query \(Q_{i-1}\) and the secret parameter \(K_{L}\). The cloud user forms a query \(Q=(Q_{1},\ldots,Q_{l})\) and sends \(Q\) to the cloud provider. For instance, for a substring \"aba\", the cloud user creates \(Q_{1}=F_{K_{Q}}(a|1|L_{root}|K_{L})\) (\(L_{root}\) is shared by the data owner to the cloud user), \(Q_{2}=F_{K_{Q}}(b|2|Q_{1}|K_{L})\), \(Q_{3}=F_{K_{Q}}(a|3|Q_{2}|K_{L})\) and sends \(Q=(Q_{1},Q_{2},Q_{3})\) to the cloud provider. The cloud server indexes into the encrypted position heap tree \(\bar{\Lambda}\), and for each given \(Q_{i}\), it matches encrypted label \(\overline{L}\) of each node in \(\bar{\Lambda}\) to \(Q_{i}\) and continues until the longest matching node \(\overline{\
u_{match}}\) in \(\bar{\Lambda}\) is found. The cloud server returns the set of ancestor and descendant nodes of \(\overline{\
u_{match}}\) to the cloud user. Using the example in Figure 4b and search query \(Q=(Q_{1},Q_{2},Q_{3})\), the cloud provider returns the set of encrypted ancestor nodes (\(SKE.Enc_{K_{V}}(1)\), \(SKE.Enc_{K_{V}}(2)\), \(SKE.Enc_{K_{V}}(6)\)) and the set of encrypted descendant nodes (\(SKE.Enc_{K_{V}}(7)\), \(SKE.Enc_{K_{V}}(8)\)). Now, the cloud user applies the SKE scheme with secret key \(K_{V}\) to decrypt the ancestor and descendant nodes, i.e., \((1,2,6)\) ancestor nodes and \((7,8)\) descendant nodes. Next, he uses PRP \(P\) with secret key \(K_{3}\) on each decrypted node, i.e., \(y_{idx}=P_{K_{3}}(idx)\), where \(idx\) is \((1,2,6,7,8)\), and sends the resulting query \(y\) to the cloud provider. The cloud provider uses array \(Y\) to fetch the elements at index \(y_{i}\) (\(i\in[1;5]\)) as \(Y[y_{i}]\) and sends back the results. Once received, the cloud user applies SKE with secret key \(K_{Y}\) to decrypt the positions in the ancestor and descendant nodes, i.e., \((1,3,6)\) positions in ancestor nodes and \((11,15)\) positions in descendant nodes. According to Definition 11, descendant nodes \((11,15)\) are the positions of query \"aba\" in the text, and ancestor nodes \((1,3,6)\) require an inspection, since some of them can point at \"aba\" in the text. Note, since the substring \"aba\" has a length of three, the substring may exist at positions \((6,5,4)\) and \((3,2,1)\) in the text. Therefore, to launch the inspection, the cloud user applies PRP \(P\) with secret key \(K_{X}\) at each position \((6,5,4,3,2,1)\) as \(x_{idx}=P_{K_{2}}(idx)\) and sends query \(x\) to the cloud provider. Now, the cloud provider uses array \(X\) and sends back the elements of the array at index \(X[x_{i}]\) (\(i\in[1;6]\)). The cloud user uses SKE.Enc with secret key \(K_{X}\) to decrypt the characters \(t_{j}\) at positions \((6,5,4,3,2,1)\) (i.e., received characters are \((a,b,a,a,b,a)\)). Using this information, the cloud user verifies if substring characters \(\chi_{i}\) match received characters \(t_{j}\) at each ancestor position. The inspection of ancestors shows that only \((6,3)\) are the positions. Thus, the cloud user concludes that substring query \"aba\" is at position \((3,6,11,15)\) in the text. Note, if multiple documents are involved in the original text construction, ancestor and descendant nodes contain the document identifiers, which can be later used by the cloud user to download the matching encrypted documents and decrypt them locally using PCPA-secure symmetric-key encryption SKE with secret key \(K_{1}\). **SEARCH PHASE.