Searchable symmetric encryption

A static SSE scheme consists of three algorithms ${\displaystyle {\mathsf {SSE=(Setup,Token,Search)}}}$ that work as follows:

• ${\displaystyle {\mathsf {Setup}}}$ takes as input a security parameter ${\displaystyle k}$ and a document collection ${\displaystyle \mathbf {D} }$ and outputs a symmetric key ${\displaystyle K}$, an encrypted index ${\displaystyle \mathbf {I} }$, and an encrypted document collection ${\displaystyle \mathbf {ED} }$
• ${\displaystyle {\mathsf {Token}}}$ takes as input the secret key ${\displaystyle K}$ and a keyword ${\displaystyle w}$ and outputs a search token ${\displaystyle tk}$
• ${\displaystyle {\mathsf {Search}}}$ takes as input the encrypted index ${\displaystyle \mathbf {I} }$, the encrypted document collection ${\displaystyle \mathbf {ED} }$ and a search token ${\displaystyle tk}$ and outputs a set of encrypted documents ${\displaystyle \mathbf {R} \subseteq \mathbf {ED} }$

A static SSE scheme is used by a client and an untrusted server as follows. The client encrypts its data collection using the ${\displaystyle {\mathsf {Setup}}}$ algorithm which returns a secret key ${\displaystyle K}$ and an encrypted document collection ${\displaystyle \mathbf {ED} }$. The client keeps ${\displaystyle K}$ secret and sends ${\displaystyle \mathbf {ED} }$ and ${\displaystyle \mathbf {I} }$ to the untrusted server. To search for a keyword ${\displaystyle w}$, the client runs the ${\displaystyle {\mathsf {Token}}}$ algorithm on ${\displaystyle K}$ and ${\displaystyle w}$ to generate a search token ${\displaystyle tk}$ which it sends to the server. The server runs Search with ${\displaystyle \mathbf {ED} }$, ${\displaystyle \mathbf {I} }$, and ${\displaystyle tk}$ 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. A dynamic SSE scheme consists of seven algorithms ${\displaystyle {\mathsf {SSE=(Setup,Token,Search,InsertToken,Insert,DeleteToken,Delete)}}}$ where ${\displaystyle {\mathsf {Setup}}}$, ${\displaystyle {\mathsf {Token}}}$ and ${\displaystyle {\mathsf {Search}}}$ are as in the static case and the remaining algorithms work as follows:

• ${\displaystyle {\mathsf {InsertToken}}}$ takes as input the secret key ${\displaystyle K}$ and a new document ${\displaystyle \mathrm {D_{n+1}} }$ and outputs an insert token ${\displaystyle itk}$
• ${\displaystyle {\mathsf {Insert}}}$ takes as input the encrypted document collection EDC and an insert token ${\displaystyle itk}$ and outputs an updated encrypted document collection ${\displaystyle \mathbf {ED'} }$
• ${\displaystyle {\mathsf {DeleteToken}}}$ takes as input the secret key ${\displaystyle K}$ and a document identifier ${\displaystyle id}$ and outputs a delete token ${\displaystyle dtk}$
• ${\displaystyle {\mathsf {Delete}}}$ takes as input the encrypted data collection ${\displaystyle \mathrm {EDC} }$ and a delete token ${\displaystyle dtk}$ and outputs an updated encrypted data collection ${\displaystyle \mathbf {ED'} }$

To add a new document ${\displaystyle \mathrm {D_{n+1}} }$ the client runs ${\displaystyle {\mathsf {InsertToken}}}$ on ${\displaystyle K}$ and ${\displaystyle \mathrm {D_{n+1}} }$to generate an insert token ${\displaystyle itk}$ which it sends to the server. The server runs ${\displaystyle {\mathsf {Insert}}}$ with ${\displaystyle \mathbf {ED} }$ and ${\displaystyle itk}$ and stores the updated encrypted document collection. To delete a document with identifier ${\displaystyle id}$, the client runs the ${\displaystyle {\mathsf {DeleteToken}}}$ algorithm with ${\displaystyle K}$ and ${\displaystyle id}$ to generate a delete token ${\displaystyle dtk}$ which it sends to the server. The server runs ${\displaystyle {\mathsf {Delete}}}$ with ${\displaystyle \mathbf {ED} }$ and ${\displaystyle dtk}$ and stores the updated encrypted document collection.

An SSE scheme that does not support ${\displaystyle {\mathsf {DeleteToken}}}$ and ${\displaystyle {\mathsf {Delete}}}$ is called semi-dynamic.

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 ${\displaystyle \Lambda _{\mathrm {opt} }}$ which reveals the number of documents in the collection, the size of each document in the collection, if and when a query was repeated and which encrypted documents match the search query.[2][12] It is known, however, how to construct schemes that leak considerably less at an additional cost in search time and storage.[13][14]

When considering dynamic SSE schemes, the state-of-the-art constructions with optimal time search have leakage profiles that guarantee forward privacy[15] 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.[11] 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.[16]

A leakage profile only describes the leakage of an SSE scheme but it says nothing about whether that leakage can be exploited or not. 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.[17][18]