an updated encrypted data collection To add a new document the client runs on and to generate an insert token which it sends to the server. The server runs with and and stores the updated encrypted document collection. To delete a document with identifier , the client runs the algorithm with and to generate a delete token which it sends to the server. The server runs with and and stores the updated encrypted document collection. An SSE scheme that does not support and is called semi-dynamic. History of Searchable Symmetric Encryption The problem of searching on encrypted data was considered by Song, Wagner and Perrig though previous work on Oblivious RAM by Goldreich and Ostrovsky could be used in theory to address the problem. This work proposed an SSE scheme with a search algorithm that runs in time , where . Goh and Chang and Mitzenmacher gave new SSE constructions with search algorithms that run in time , where is the number of documents. Curtmola, Garay, Kamara and Ostrovsky later proposed two static constructions with search time, where is the number of documents that contain , which is optimal. This work also proposed a semi-dynamic construction with search time, where is the number of updates. An optimal dynamic SSE construction was later proposed by Kamara, Papamanthou and Roeder. Goh and Chang and Mitzenmacher proposed security definitions for SSE. These were strengthened and extended by Curtmola, Garay, Kamara and Ostrovsky who proposed the notion of adaptive security for SSE. This work also was the first to observe leakage in SSE and to formally capture it as part of the security definition. Leakage was further formalized and generalized by Chase and Kamara. Islam, Kuzu and Kantarcioglu described the first leakage attack. All the previously mentioned constructions support single keyword search. Cash, Jarecki, Jutla, Krawczyk, Rosu and Steiner proposed an SSE scheme that supports conjunctive search in sub-linear time in . The construction can also be extended to support disjunctive and Boolean searches that can be expressed in searchable normal form (SNF) in sub-linear time. At the same time, Pappas, Krell, Vo, Kolesnikov, Malkin, Choi, George, Keromytis and Bellovin described a construction that supports conjunctive and all disjunctive and Boolean searches in sub-linear time. Security SSE schemes are designed to guarantee that the untrusted server cannot learn any partial information about the documents or the search queries beyond some well-defined and reasonable leakage.