Searchable symmetric encryption
[1][2][3] SSE can be used to outsource files to an untrusted cloud storage server without ever revealing the files in the clear but while preserving the server's ability to search over them.
The result of the search is the subset of encrypted documents that contain the keyword
that work as follows: A static SSE scheme is used by a client and an untrusted server as follows.
and returns the resulting encrypted documents back to the client.
A dynamic SSE scheme supports, in addition to search, the insertion and deletion of documents.
{\displaystyle {\mathsf {SSE=(Setup,Token,Search,InsertToken,Insert,DeleteToken,Delete)}}}
are as in the static case and the remaining algorithms work as follows: To add a new document
The problem of searching on encrypted data was considered by Song, Wagner and Perrig[1] though previous work on Oblivious RAM by Goldreich and Ostrovsky[4] could be used in theory to address the problem.
This work[1] proposed an SSE scheme with a search algorithm that runs in time
Goh[5] and Chang and Mitzenmacher[6] gave new SSE constructions with search algorithms that run in time
Curtmola, Garay, Kamara and Ostrovsky[2] later proposed two static constructions with
An optimal dynamic SSE construction was later proposed by Kamara, Papamanthou and Roeder.
[7] Goh[5] and Chang and Mitzenmacher[6] proposed security definitions for SSE.
These were strengthened and extended by Curtmola, Garay, Kamara and Ostrovsky[2] 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.
[8] Islam, Kuzu and Kantarcioglu described the first leakage attack.
[9] All the previously mentioned constructions support single keyword search.
Cash, Jarecki, Jutla, Krawczyk, Rosu and Steiner[10] 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[11] described a construction that supports conjunctive and all disjunctive and Boolean searches in sub-linear time.
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.
SSE constructions attempt to minimize leakage while achieving the best possible search efficiency.
SSE security can be analyzed in several adversarial models but the most common are: In the persistent model, there are SSE schemes that achieve a wide variety of leakage profiles.
The most common leakage profile for static schemes that achieve single keyword search in optimal time is
[2][13] It is known, however, how to construct schemes that leak considerably less at an additional cost in search time and storage.
[14][15] When considering dynamic SSE schemes, the state-of-the-art constructions with optimal time search have leakage profiles that guarantee forward privacy[16] which means that inserts cannot be correlated with past search queries.
In the snapshot model, efficient dynamic SSE schemes with no leakage beyond the number of documents and the size of the collection can be constructed.
[12] When using an SSE construction that is secure in the snapshot model one has to carefully consider how the scheme will be deployed because some systems might cache previous search queries.
Cryptanalysis is therefore used to better understand the real-world security of a leakage profile.
There is a wide variety of attacks working in different adversarial models, based on a variety of assumptions and attacking different leakage profiles.
