# Substring Position Search over Encrypted Cloud Data Supporting Efficient Multi-User Setup +
## 3 Background and Building Blocks
### Preliminaries and Notations  
Let \(D=\{D_{1},D_{2},\ldots,D_{l}\}\) be an original set of documents, and let \(C=\{C_{1},C_{2},\ldots,C_{l}\}\) be an encrypted collection of documents from \(D\). If \(D_{i}\) and \(D_{j}\) are two documents, we denote text \(t\) as their concatenation by \(D_{i}||D_{j}\). If \(A\) is an algorithm, then \(a\gets A(\ldots)\) represents the result of applying the algorithm \(A\).  
In addition to the notations above, we also make use of cryptographic notations. We begin with definitions of Pseudorandom Functions (PRF) and Pseudorandom Permutations (PRP), which are polynomial-time computable functions that cannot be distinguished from random functions by any probabilistic polynomial-time (PPT) adversary, and random oracles to which all parties have black box access.  
Figure 1: Cloud data hosting architecture.  
**Definition 1**.: _(Pseudorandom Function (PRF))._ A function \(f\): \(\{0,1\}^{k}\times\{0,1\}^{n}\rightarrow\{0,1\}^{l}\) is a \((t,\epsilon,q)\)-pseudorandom function if:  
* Given a key \(K\in\{0,1\}^{k}\) and an input \(X\in\{0,1\}^{n}\), there is an algorithm to compute \(F_{K}(X)=F(X,K)\).
* For any \(t\)-time oracle algorithm \(A\), we have: \[|Pr_{K\leftarrow\{0,1\}^{k}}[A^{f_{K}}]-Pr_{f\in\mathrm{F}}[A^{f}]|<\epsilon\] (1) where \(\mathrm{F}=\{f:\{0,1\}^{n}\rightarrow\{0,1\}^{l}\}\) and \(A\) makes at most \(q\) queries to the oracle.  
**Definition 2**.: _(Pseudorandom Permutation (PRP))._ If pseudorandom function \(f\) in Definition 1 is bijective, then it is a pseudorandom permutation as follows: \(\{0,1\}^{k}\times\{0,1\}^{n}\rightarrow\{0,1\}^{n}\).  
**Definition 3**.: _(Symmetric Key Encryption (SKE))._ A symmetric key encryption scheme consists of the following PPT algorithms:  
* \(Gen(1^{k}):\) a key generation algorithm that inputs a security parameter \(k\) and outputs a secret key \(K\).
* \(Enc(K,m):\) a probabilistic algorithm that inputs a secret key \(K\) and message \(m\), and outputs a ciphertext \(c\).
* \(Dec(K,c):\) a deterministic algorithm that inputs a secret key \(K\) and ciphertext \(c\), and outputs a message \(m\) or special symbol \(\bot\) (if decryption failed).  
**Definition 4**.: _(SKE correctness)._ Given the symmetric encryption scheme SKE that consists of three algorithms (Gen, Enc, Dec), for all \(k\) and all \(m\), such that \(K\leftarrow Gen(1^{k})\), we require:  
\[Dec(K,Enc(K,m))=m. \tag{2}\]  
We also require SKE to be secure against Pseudorandom Chosen-Plaintext Attacks (PCPA). We now give the definition of the PCPA security of the SKE scheme.  
**Definition 5**.: _(PCPA-security)._ Let SKE = (Gen, Enc, Dec) be a symmetric encryption scheme, \(A\) be an adversary, and there is a probabilistic experiment \(PCPA_{SKE,A}(k)\) that is run as follows:  
* Use secret parameter \(k\) to output the secret key \(K\to Gen(1^{k})\).
* The adversary \(A\) is given oracle access to \(Enc_{K}()\).
* The adversary \(A\) outputs a message \(m\).
* Let \(c_{0}\leftarrow Enc_{K}(m)\) and \(c_{1}\xleftarrow{R}C\). \(C\) denotes the set of all possible ciphertexts. A bit \(b\) is chosen at random, and \(c_{b}\) is given to the adversary \(A\).
* The adversary \(A\) is again given to the oracle access to \(Enc_{K}()\), and \(A\) runs the number of polynomial queries to output a bit \(b^{\prime}\).
* The experiment outputs one if \(b=b^{\prime}\), otherwise zero.  
The symmetric encryption scheme SKE is PCPA-secure if for all polynomial-size adversaries \(A\),  
\[Pr[PCPA_{SKE,A}(k)=1]\leq\frac{1}{2}+negl(k), \tag{3}\]  
where the probability is over the choice of bit \(b\) and the coins of Gen and Enc.