# Substring Position Search over Encrypted Cloud Data Supporting Efficient Multi-User Setup +
## 1 Introduction  
Owing to the wide adoption of cloud computing services, public, as well as private organizations now outsource their data to remote servers. Cloud computing services provide efficient and cost-effective solutions for data storage. Nevertheless, outsourced data may contain sensitive information that needs to be protected. Traditional encryption techniques protect the data from unauthorized access; however, they introduce new challenges to data utilization. Specifically, allowing users to efficiently search over encrypted data is one of the most pressing issues in cloud computing. In order to enable search over encrypted data, many Searchable Encryption (SE) schemes have been proposed in recent years [1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19; 20]. (Note, we use the term searchable encryption somewhat loosely to include schemes, such as private information retrieval, as well.) Generally, SE solutions involve building an encrypted searchable index that hides the sensitive information from the remote server, yet they allow a search on the encrypted data. SE solutions differ in the level of efficiency and security guarantees that they offer; however, most of them support only exact keyword search. As a result, there is no tolerance of format inconsistencies that are part of typical cloud user behavior; andthey happen frequently. It is quite common that the search queries do not exactly match the pre-set keywords due to lack of exact knowledge about the data. For example, a financial company stores its employees' income tax documents in encrypted form in the cloud. A tax accountant may issue a search query of \"form1040\", which describes multiple keywords, such as \"form1040\", \"form1040A\", \"form1040-ez\", \"form1040 es\", and she wants to find a position of the first occurrence of the query in each encrypted document that contains the string of characters. The significant drawback of existing schemes underlines an important need for new techniques that support search flexibility over encrypted documents. In this work, we consider the problem of efficient substring position search over encrypted data. The users can query the remote untrusted server for a set of encrypted documents that contain a substring of characters. The cloud server retrieves the set of matching documents together with positions where the queried string begins. An important application of this work is in the area of searching a genome sequence against genomic databases. Such a search can be used in the analysis of genetic diseases, genetic fingerprinting or genetic genealogy and requires a set of results that do not simply match the genome, but rather the position of the genome sequence within the genome database. The major contribution of our work is to initiate the study of a very important problem, namely substring position search over encryption data. Our solution should not be considered as a complete approach for the subject, which has very strong future directions of research. Nonetheless, our solution provides the preliminary foundation for the study of the subject, including formal definitions, building blocks, basic construction, as well as security proofs. In this work, we continue exploring the line of recent searchable encryption solutions, but from a slightly different standpoint. We now give an overview of our contributions:  
1. We present a Substring Position Searchable Symmetric Encryption (SSP-SSE) scheme that allows a substring search over an encrypted document collection. The scheme is based on a position heap tree data structure recently proposed by [PERSON] et al. (2016). 2. We formally define two leakage functions and security against the adaptive chosen-query attack of a tree-based SSP-SSE scheme. Apart from the traditional access and search patterns, we include the definition of the path pattern in the leakage functions of a tree-based searchable encryption. We show that SSP-SSE enjoys the strong notion of semantic security ([PERSON] et al., 2016). 3.