# 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
**  
\([(Q)\leftarrow ConstructQuery(K,\chi)]\leftrightarrow[(L)\gets Search(I,Q)]\) is an interactive protocol between the cloud user and the cloud provider. The cloud user keeps the key set \(K=(K_{1},\)\(K_{X},\)\(K_{Y},\)\(K_{V},\)\(K_{Q},\)\(K_{L},\)\(K_{2},\)\(K_{3})\) and queries cloud provider for a substring \(\chi\). The cloud provider executes search on searchable index \(I=(\bar{\Lambda},\)\(X,\)\(Y)\) and returns results back to the cloud user. 1. cloud user: given the secret key \(K_{Q}\) and the string of interest \(\chi\), output the search query \(Q\) as follows: 1. for each character \(\chi_{i}\), \(i\in[1;m]\), where \(m=|\chi|\) 1. set \(Q_{i}=F_{K_{Q}}(\chi_{i}||i||Q_{i-1}||K_{L})\) (i.e., apply PRF \(F\) with key \(K_{Q}\) on the concatenation of character \(\chi_{i}\) of \(\chi\), \(i\), output of query \(Q_{i-1}\) and secret key \(K_{L}\).) 2. set \(Q=(Q_{1},Q_{2},\ldots,Q_{m})\). 2. send search query \(Q\) to the cloud provider. 2. cloud provider: index into \(\bar{\Lambda}\), start at the root node 1. for each \(Q_{i}\) and each node \(\overline{v}\) in \(\bar{\Lambda}\), match the encrypted label \(\overline{L}(\overline{v})\) to \(Q_{i}\). Continue until the longest node \(\overline{v[match]}\) is found. 2. If \(\overline{v[match]}\
eq\bot\), return \((\mathit{descendants}(\overline{v[match]},\)\(\mathit{ancestors}(\overline{v[match]})))\), otherwise return \(\bot\). 3. cloud user: let TMP-AN and TMP-DE be two arrays; let TMP-RES = TMP-AN + TMP-DE be an array that combines elements from TMP-AN and TMP-DE. 1. for each node \(\overline{v}\) in \(\mathit{ancestors}(\overline{v[match]})\): 1. if \(\mathit{SKE}.Dec_{K_{V}}(\overline{V}(\overline{v}))=\bot\), abort. Otherwise, output \(idx\), and add to TMP-AN. 2. for each node \(\overline{v}\) in \(\mathit{descendants}(\overline{v[match]})\): 1. if \(\mathit{SKE}.Dec_{K_{V}}(\overline{V}(\overline{v}))=\bot\), abort. Otherwise, output \(idx\), and add to TMP-DE. 3. set TMP-RES = TMP-AN + TMP-DE, for each \(idx\) in TMP-RES, set \(y_{idx}=P_{K_{3}}(idx)\). Send \((y_{1},\ldots,y_{num})\) to the cloud provider. 4. cloud provider: get \(Y_{i}=Y[y_{i}]\) (\(i\in[1,num]\)), output \((Y_{1},\ldots,Y_{num})\). 5. cloud user: let AN and DE be two arrays. 1. for \(i=[1,m]\), if \(\mathit{SKE}.Dec_{K_{V}}(Y_{i})=\bot\), abort; otherwise, add output to AN. 2. for \(i=[m+1,num]\), if \(\mathit{SKE}.Dec_{K_{V}}(Y_{i})=\bot\), abort; otherwise, add output to DE. 3. parse each element from AN as \(\mathit{pid}(D)||pos\). 4. for each \(pos\) in AN, for \(j=pos\), \(j>(j-m)\) (where \((j-m)>0\)), \(j--\), let \(x_{j}=P_{K_{2}}(j)\), send \((x_{1},\ldots,x_{h})\) to the cloud provider. 6. cloud provider: get \(X_{i}=X[x_{i}]\) (\(i\in[1,h]\)), output \((X_{1},\ldots,X_{h})\). 7. cloud user: let REAL-AN be an array. 1. for \(i=[1;h]\), if \(\mathit{SKE}.Dec_{K_{X}}(X_{i})=\bot\), abort. Otherwise, parse the output as \(t_{j}\). 2. for each \(pos\) in AN, compare characters \(\chi_{u}=t_{j}\), where \(u=0\), \(u<m\), \(u++\) and \(j=pos\), \(j>(j-l)\) (where \((j-l)\
ot<0\)), \(j--\). If all \(\chi_{u}=t_{j}\) match at given \(pos\), add \(pos\) to REAL-AN; otherwise, ignore \(pos\). 3. let RES = REAL-AN + DE. Parse each element of array \(RES\) as \(\mathit{id}(D_{h})||pos_{D_{h}}\), where \(pos_{D_{h}}\) is the position of substring \(\chi\) in document \(D_{h}\) (\(h\in[1,l]\)). \(\mathit{Decrypt}(K_{1},K_{2},C_{i}):\)  
1. retrieve set \(C=(C_{1},\ldots,\)\(C_{k})\) from the cloud provider. 2. \(D_{i}\gets\mathit{SKE}.Dec_{K_{1}}(C_{i})\), where \(i\in[1;k]\). 3. output \(((D_{1},pos_{D_{1}}),\ldots,(D_{k},pos_{D_{k}}))\).