# Substring Position Search over Encrypted Cloud Data Supporting Efficient Multi-User Setup +
## 2 Related Work  
Efficient searchable encryption methods are extensively studied in the literature. Traditional searchable encryption schemes focus on the problem of searching for a keyword in the document collection. In this setting, each document is assumed to consist of a sequence of keywords. The cloud server must be able to determine which encrypted documents contain a particular queried keyword, which is also encrypted. [PERSON] et al. [2] presented the first searchable symmetric encryption scheme. Their scheme has provable security properties, linear-time search complexity in the length of the document collection. [PERSON] et al. [3] introduced formal security definitions of searchable symmetric encryption and proposed a scheme that is based on the Bloom filters [22]. The scheme requires a linear search time and provides some false positive results. Many other schemes have been proposed to improve the efficiency of keyword search by implementing an inverted searchable index [4; 6; 13; 23]. [PERSON] et al. [13] showed an index construction that enables keyword search without false positive results. [PERSON] et al. [6] gave the first solution that enables sublinear search time for the entire document collection. Here, the searchable index consists of a keyword trapdoor and encrypted document identifiers whose corresponding data files contain the keyword. Recently, [PERSON] et al. [10] proposed the multi-keyword ranked search scheme. The solution ranks encrypted documents based on a similarity score. The score is calculated between the search query (that contains multiple keywords) and the set of encrypted documents. [PERSON] et al. [4] developed the Boolean Symmetric Searchable Encryption (BSSE) scheme. The scheme is based on the orthogonalization of the keywords according to the Gram-Schmidt process. Later, [PERSON] et al. [24] proposed the Conjunctive Symmetric Searchable Encryption scheme that allows conjunctive keyword search on encrypted documents with different privacy assurances. [PERSON]'s solution [5] proposed the privacy-preserving multi-keyword search method that utilizes minhash functions. In the public-key setting, [PERSON] et al. [8] were the first to propose a searchable encryption using asymmetric cryptography. The authors developed the construction where anyone with the public key can write to the data stored on the remote server, but only authorized users with the private key can search. The other asymmetric solution was provided by [PERSON] et al. in [25], where the authors designed a public-key encryption scheme with keyword search based on a variant of the quadratic residuosity problem. To support more complex queries, conjunctive keyword search, subset query and range query over encrypted data have also been proposed in [7; 9; 14; 26; 27]. All of the schemes above support only exact keyword search, i.e., there is no tolerance of format inconsistencies in the search. [PERSON] et al. [17] were the first to propose a fuzzy keyword search scheme over encrypted data. The authors developed the solution that constructs fuzzy keyword sets based on document collection and later uses the edit distance to measure the similarity between keyword query and the sets. [PERSON] et al. [18] improved previous work and proposed a scheme that achieves constant search time complexity. Later, [PERSON] et al. [19] gave an efficient fuzzy-searchable encryption (EFSE) scheme to locate the similar records. The main drawback of fuzzy keyword search solutions is that they require a large ciphertext and computation overhead and, thus, may not be suitable for the real-world cloud storage systems. The SSE solution proposed by [PERSON] et al. [6] can be adopted to allow the substring search over encrypted data. To do this, we would have to generate all possible substrings of each keyword extracted from the document collection and consider these substrings as keywords.