Searchable symmetric encryption

Short description: System allowing searching of encrypted documents

Keyword search using an SSE scheme

Searchable symmetric encryption (SSE) is a form of encryption that allows efficient searching over a collection of encrypted documents or files without requiring decryption. SSE can be used to outsource files to an untrusted cloud storage server without revealing the files in plaintext, while preserving the server's ability to perform searches over them.

Description

A searchable symmetric encryption scheme is a symmetric-key encryption scheme that encrypts a collection of documents $\mathbf{𝐃}=({\mathrm{D}}_{\mathrm{1}},\dots ,{\mathrm{D}}_{\mathrm{n}})$, where each document ${\mathrm{D}}_{\mathrm{i}}\subseteq \mathbb{𝕎}$ is viewed as a set of keywords from a keyword space $\mathbb{𝕎}$. Given the encryption key $K$ and a keyword $w\in \mathbb{𝕎}$, one can generate a search token $tk$ with which the encrypted data collection can be searched for $w$. The result of the search is the subset of encrypted documents that contain the keyword $w$.

Static SSE

A static SSE scheme consists of three algorithms $\mathsf{S}\mathsf{S}\mathsf{E}\mathsf{=}\mathsf{(}\mathsf{S}\mathsf{e}\mathsf{t}\mathsf{u}\mathsf{p},\mathsf{T}\mathsf{o}\mathsf{k}\mathsf{e}\mathsf{n},\mathsf{S}\mathsf{e}\mathsf{a}\mathsf{r}\mathsf{c}\mathsf{h}\mathsf{)}$ that work as follows:

• $\mathsf{S}\mathsf{e}\mathsf{t}\mathsf{u}\mathsf{p}$ takes as input a security parameter $k$ and a document collection $\mathbf{𝐃}$ and outputs a symmetric key $K$, an encrypted index $\mathbf{𝐈}$, and an encrypted document collection $\mathbf{𝐄}\mathbf{𝐃}$
• $\mathsf{T}\mathsf{o}\mathsf{k}\mathsf{e}\mathsf{n}$ takes as input the secret key $K$ and a keyword $w$ and outputs a search token $tk$
• $\mathsf{S}\mathsf{e}\mathsf{a}\mathsf{r}\mathsf{c}\mathsf{h}$ takes as input the encrypted index $\mathbf{𝐈}$, the encrypted document collection $\mathbf{𝐄}\mathbf{𝐃}$ and a search token $tk$ and outputs a set of encrypted documents $\mathbf{𝐑}\subseteq \mathbf{𝐄}\mathbf{𝐃}$

A static SSE scheme is used by a client and an untrusted server as follows: the client encrypts its data collection using the $\mathsf{S}\mathsf{e}\mathsf{t}\mathsf{u}\mathsf{p}$ algorithm which returns a secret key $K$, an encrypted index $\mathbf{𝐈}$, and an encrypted document collection $\mathbf{𝐄}\mathbf{𝐃}$. The client keeps $K$ secret and sends $\mathbf{𝐄}\mathbf{𝐃}$ and $\mathbf{𝐈}$ to the untrusted server. To search for a keyword $w$, the client runs the $\mathsf{T}\mathsf{o}\mathsf{k}\mathsf{e}\mathsf{n}$ algorithm on $K$ and $w$ to generate a search token $tk$ which it sends to the server. The server runs Search with $\mathbf{𝐄}\mathbf{𝐃}$, $\mathbf{𝐈}$, and $tk$ and returns the resulting encrypted documents back to the client.

Dynamic SSE

A dynamic SSE scheme supports, in addition to search, the insertion and deletion of documents. A dynamic SSE scheme consists of seven algorithms $\mathsf{S}\mathsf{S}\mathsf{E}\mathsf{=}\mathsf{(}\mathsf{S}\mathsf{e}\mathsf{t}\mathsf{u}\mathsf{p},\mathsf{T}\mathsf{o}\mathsf{k}\mathsf{e}\mathsf{n},\mathsf{S}\mathsf{e}\mathsf{a}\mathsf{r}\mathsf{c}\mathsf{h},\mathsf{I}\mathsf{n}\mathsf{s}\mathsf{e}\mathsf{r}\mathsf{t}\mathsf{T}\mathsf{o}\mathsf{k}\mathsf{e}\mathsf{n},\mathsf{I}\mathsf{n}\mathsf{s}\mathsf{e}\mathsf{r}\mathsf{t},\mathsf{D}\mathsf{e}\mathsf{l}\mathsf{e}\mathsf{t}\mathsf{e}\mathsf{T}\mathsf{o}\mathsf{k}\mathsf{e}\mathsf{n},\mathsf{D}\mathsf{e}\mathsf{l}\mathsf{e}\mathsf{t}\mathsf{e}\mathsf{)}$ where $\mathsf{S}\mathsf{e}\mathsf{t}\mathsf{u}\mathsf{p}$, $\mathsf{T}\mathsf{o}\mathsf{k}\mathsf{e}\mathsf{n}$, and $\mathsf{S}\mathsf{e}\mathsf{a}\mathsf{r}\mathsf{c}\mathsf{h}$ are as in the static case and the remaining algorithms work as follows:

• $\mathsf{I}\mathsf{n}\mathsf{s}\mathsf{e}\mathsf{r}\mathsf{t}\mathsf{T}\mathsf{o}\mathsf{k}\mathsf{e}\mathsf{n}$ takes as input the secret key $K$ and a new document ${\mathrm{D}}_{\mathrm{n}\mathrm{+}\mathrm{1}}$ and outputs an insert token $itk$
• $\mathsf{I}\mathsf{n}\mathsf{s}\mathsf{e}\mathsf{r}\mathsf{t}$ takes as input the encrypted document collection $\mathbf{𝐄}\mathbf{𝐃}$ and an insert token $itk$ and outputs an updated encrypted document collection $\mathbf{𝐄}{\mathbf{𝐃}}^{\prime }$
• $\mathsf{D}\mathsf{e}\mathsf{l}\mathsf{e}\mathsf{t}\mathsf{e}\mathsf{T}\mathsf{o}\mathsf{k}\mathsf{e}\mathsf{n}$ takes as input the secret key $K$ and a document identifier $id$ and outputs a delete token $dtk$
• $\mathsf{D}\mathsf{e}\mathsf{l}\mathsf{e}\mathsf{t}\mathsf{e}$ takes as input the encrypted data collection $\mathbf{𝐄}\mathbf{𝐃}$ and a delete token $dtk$ and outputs an updated encrypted data collection $\mathbf{𝐄}{\mathbf{𝐃}}^{\prime }$

To add a new document ${\mathrm{D}}_{\mathrm{n}\mathrm{+}\mathrm{1}}$ the client runs $\mathsf{I}\mathsf{n}\mathsf{s}\mathsf{e}\mathsf{r}\mathsf{t}\mathsf{T}\mathsf{o}\mathsf{k}\mathsf{e}\mathsf{n}$ on $K$ and ${\mathrm{D}}_{\mathrm{n}\mathrm{+}\mathrm{1}}$to generate an insert token $itk$ which it sends to the server. The server runs $\mathsf{I}\mathsf{n}\mathsf{s}\mathsf{e}\mathsf{r}\mathsf{t}$ with $\mathbf{𝐄}\mathbf{𝐃}$ and $itk$ and stores the updated encrypted document collection. To delete a document with identifier $id$, the client runs the $\mathsf{D}\mathsf{e}\mathsf{l}\mathsf{e}\mathsf{t}\mathsf{e}\mathsf{T}\mathsf{o}\mathsf{k}\mathsf{e}\mathsf{n}$ algorithm with $K$ and $id$ to generate a delete token $dtk$ which it sends to the server. The server runs $\mathsf{D}\mathsf{e}\mathsf{l}\mathsf{e}\mathsf{t}\mathsf{e}$ with $\mathbf{𝐄}\mathbf{𝐃}$ and $dtk$ and stores the updated encrypted document collection.

An SSE scheme that does not support $\mathsf{D}\mathsf{e}\mathsf{l}\mathsf{e}\mathsf{t}\mathsf{e}\mathsf{T}\mathsf{o}\mathsf{k}\mathsf{e}\mathsf{n}$ and $\mathsf{D}\mathsf{e}\mathsf{l}\mathsf{e}\mathsf{t}\mathsf{e}$ is called semi-dynamic.

History of Searchable Symmetric Encryption

The problem of searching on encrypted data was considered by Song, Wagner and Perrig, although earlier work on Oblivious RAM by Goldreich and Ostrovsky could, in theory, be used to address the problem. This work proposed an SSE scheme with a search algorithm that runs in time $O(s)$, where $s=|\mathbf{𝐃}|$. Goh and Chang and Mitzenmacher proposed new SSE constructions with search algorithms that run in time $O(n)$, where $n$ is the number of documents. Curtmola, Garay, Kamara and Ostrovsky later proposed two static constructions with $O(\mathrm{o}\mathrm{p}\mathrm{t})$ search time, where $\mathrm{o}\mathrm{p}\mathrm{t}$ is the number of documents that contain $w$, which is optimal. This work also proposed a semi-dynamic construction with $O(\mathrm{o}\mathrm{p}\mathrm{t}\cdot \log (u))$ search time, where $u$ 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 later strengthened and extended by Curtmola, Garay, Kamara and Ostrovsky, who introduced the notion of adaptive security for SSE. This work was also 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, Roşu and Steiner proposed an SSE scheme that supports conjunctive search in sub-linear time in $n$. 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 ensure that an untrusted server cannot learn any partial information about the documents or search queries beyond a well-defined and reasonable leakage. The leakage of a scheme is formally described using a leakage profile, which itself can consist of several leakage patterns. 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:

• the persistent model, in which an adversary is given the encrypted data collection and a transcript of all operations executed on the collection;
• the snapshot model, in which an adversary is given only the encrypted data collection (possibly after each operation).

Security in the Persistent Model

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 ${\mathrm{\Lambda }}_{\mathrm{o}\mathrm{p}\mathrm{t}}$ 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. It is also possibly to construct schemes that leak considerably less, at the cost of increased search time and storage.

For dynamic SSE schemes, state-of-the-art constructions with optimal-time search have leakage profiles that guarantee forward privacy, meaning that inserts cannot be correlated with past search queries.

Security in the Snapshot Model

In the snapshot model, efficient dynamic SSE schemes can be constructed with no leakage beyond the number of documents and the size of the collection. When using an SSE construction that is secure in the snapshot model, careful consideration must be given to deployment, as some systems might cache previous search queries.

Cryptanalysis

A leakage profile describes only the leakage of an SSE scheme and does not indicate whether that leakage can be exploited. Cryptanalysis is therefore used to better understand the real-world security implications of a leakage profile. A wide range of attacks exist, operating under different adversarial models, based on a variety of assumptions, and targeting different leakage profiles.

Systems Supporting Searchable Symmetric Encryption

Company	Product / Feature	SSE Notes
MongoDB	Queryable Encryption	Client-side field-level encryption indexes enabling equality search; SSE-style
Cossack Labs	Acra (searchable encryption / blind indexes)	Field-level encryption with blind index-based searchable encryption (exact, prefix, suffix); SSE-style
Baffle	Read Queryable Encryption (Baffle Data Protection)	Symmetric, proxy-based encryption that supports queries over protected data; SSE-like construction
AWS	AWS Database Encryption SDK – Searchable Encryption	Client-side encryption with HMAC-based beacons for equality search; related to SSE but explicitly noted by AWS as differing from academic SSE

See also

• Homomorphic encryption
• Oblivious RAM
• Structured encryption
• Deterministic encryption