Searchable symmetric encryption

Content sourced from Wikipedia, licensed under CC BY-SA 3.0.

Searchable symmetric encryption (SSE) lets you search over encrypted documents without decrypting them. It’s useful for sending data to an untrusted cloud server while still letting you find documents that match a keyword.

How it works, in simple terms:
- Each document is treated as a set of keywords.
- With a secret key, you generate a search token for a keyword. The server uses the token to locate the encrypted documents that contain that keyword, without learning their contents.
- The server returns only the matching encrypted documents.

Static SSE
- Uses three steps: Setup, Token, and Search.
- The client encrypts the data and creates an encrypted index and an encrypted document collection, keeping the key secret.
- The client sends the encrypted data and index to the server.
- To search, the client creates a search token from the key and the keyword and sends it to the server, which returns the matching encrypted documents.

Dynamic SSE
- Adds the ability to add and remove documents.
- Uses insert tokens to add new documents and delete tokens to remove them, so the server updates the encrypted collection without learning the contents.
- If deletions aren’t supported, the scheme is called semi-dynamic.

Key ideas and trade-offs
- Early work showed it’s possible to search encrypted data, with various ideas about how fast searches can be (from scanning all documents to faster, sublinear methods).
- Security is about leakage: what the server can learn beyond the search results. This is described by a leakage profile, and different security models define how much information is allowed to leak.
- Some dynamic schemes aim to protect past searches from being linked to new data (forward privacy). In the best schemes, you can have no leakage beyond certain limited patterns, but this may affect speed or storage.
- Many SSE designs started with single-keyword searches; later work added conjunctive (AND) and disjunctive/Boolean searches, often in sublinear time.
- In practice, deploying SSE requires careful attention to how much leakage is acceptable, since real-world attacks can exploit leaked information.