# Substring Position Search over Encrypted Cloud Data Supporting Efficient Multi-User Setup +
## 5 Substring Position Searchable Symmetric Encryption
### Security Model Definitions  
The security goal of any searchable encryption scheme is to reveal as little information as possible to the adversary. Intuitively, in the SSP-SSE scheme, we want to provide the following security guarantees: given a searchable index \(I\) and a set of encrypted documents \(C=\{C_{1},\,\ldots,\,C_{l}\}\) to the adversary, no valuable information about the original documents \(D=\{D_{1},\,\ldots,\,D_{l}\}\) is leaked to the adversary; given a set of incoming search queries \(Q=\{Q_{1},\,\ldots,\,Q_{t}\}\), the adversary cannot learn any practical information about the content of the search query \(Q_{i}\) or the original document collection \(D\). However, these security guarantees are difficult to achieve, and most known searchable encryption schemes [3; 4; 6; 12; 13] reveal some information, namely the access pattern and the search pattern. In SSP-SSE, we follow a similar approach to [6] to weaken the security guarantees and allow some limited information to the adversary. **Definition 14**: _(Access pattern)._ Given the \(n\) encrypted documents \(C\), where \(C=\{C_{1},\,\ldots,\,C_{l}\}\), the search query vector \(Q\), where \(Q=\{Q_{1},\,\ldots,\,Q_{t}\}\) of size \(t\), the access pattern \(\kappa(C,Q)\) includes the set of document identifiers induced by a search query vector \(Q\). **Definition 15**: _(Search pattern)._ Given the \(n\) encrypted documents \(C\), where \(C=\{C_{1},\,\ldots,\,C_{l}\}\), the search query vector \(Q\), where \(Q=\{Q_{1},\,\ldots,\,Q_{t}\}\) of size \(t\), the search pattern \(\gamma(C,Q)\) is a \(n\times t\) binarymatrix, such that \(\forall i\in[1;n]\) and \(\forall j\in[1;t]\), the cell element of \(i\)-th row and \(j\)-th column is one, if a document identifier \(id_{i}\) is returned by a search query \(Q_{j}\). The search pattern reveals whether the same search was executed in the past or not. Since our solution is based on the position heap tree data structure, we would like to capture the path pattern security notion. The path pattern of the position heap tree reveals the path traversed from the root node to the matching node for a given search query. Definition 16: (Path pattern). : Given the \(n\) encrypted documents \(C\), where \(C=\{C_{1},\ldots,C_{l}\}\), and the searchable index \(I\) built from the document collection, the path pattern of \((C,I)\) induced by the search query vector \(Q\), where \(Q=\{Q_{1},\ldots,Q_{l}\}\) of size \(t\), is a tuple \(\delta(C,I,Q)\) that reveals the set of identifiers of nodes in the index \(I\) that are reached by query \(Q_{i\in[1;t]}\). Now, we define the leakage functions to capture all of the information leakage we have in this work:  
* Leakage \(\mathbb{L}_{1}(I,C)\). Given the encrypted collection \(C=\{C_{1},\ldots,C_{l}\}\) and the searchable index \(I\), the leakage consists of the following information: the number of encrypted documents, the size of encrypted documents and the identifier of each encrypted document. * Leakage \(\mathbb{L}_{2}(Q,I,C)\). Given the encrypted collection \(C=\{C_{1},\ldots,C_{l}\}\), the searchable index \(I\) and the search query \(Q\), the leakage function outputs the access pattern \(\kappa(C,Q)\), search pattern \(\gamma(C,Q)\) and path pattern \(\delta(C,I,Q)\). Definition 17: (Security against adaptive Chosen-Query Attack (CQA2)). : Let SSP-SSE be tree-based SSE scheme that consists of six algorithms as described in Definition 12. Let \(\mathbb{A}\) be a stateful adversary and \(\mathbb{S}\) be a stateful simulator. We consider two probabilistic experiments \(Real_{\mathbb{A}}\) and \(Ideal_{\mathbb{A},\mathbb{S}}\) that involve \(\mathbb{A}\), as well as \(\mathbb{S}\), with two stateful leakage algorithms \(\mathbb{L}_{1}\) and \(\mathbb{L}_{2}\) and security parameter \(k\):  
\(Real_{\mathbb{A}}(k)\): The challenger runs the \(KeyGen(1^{k})\) to output the key set \(K\).