Searchable symmetric encryption
A searchable symmetric encryption (SSE) scheme encrypts a document collection under a client’s secret key into an encrypted index and encrypted documents, and lets the client hand a server a token for a keyword with which the server finds the identifiers of the documents containing . The server learns nothing beyond a specified leakage of the collection and the queries: a simulator given only that leakage produces a view indistinguishable from the server’s — CGKO06, CK10.
Syntax
Fix a keyword dictionary . A document collection is , where each document has an identifier and a set of keywords from ; for , is the set of identifiers of the documents containing . An index-based SSE scheme is a tuple of efficient algorithms — CGKO06:
- , a randomized algorithm outputting a secret key .
- , a randomized algorithm outputting an encrypted index and encrypted documents .
- , an algorithm outputting a token, or trapdoor, for .
- , a deterministic algorithm, run by the server, outputting a set of identifiers.
- , a deterministic algorithm recovering a document.
The client keeps and sends to the server. To search for it sends , and the server returns the ciphertexts of the documents whose identifiers outputs.
Properties
Correctness
An SSE scheme is -correct if for all , all collections and all ,
over , and the randomness of . When , we say is perfectly correct.
Leakage
Security is stated relative to a leakage function : is what the encrypted index and documents may reveal, and is what the -th token may reveal given the earlier ones — CK10. For queries , the access pattern is , and the search pattern is the binary matrix whose entry is if and only if . The trace of CGKO06 is the leakage with and the access and search patterns of .
Adaptive security
The adversary chooses the collection, receives either the real encrypted index and documents or simulated ones, and then queries tokens adaptively: each keyword may depend on the index and on the earlier tokens. In world the tokens are real; in world a stateful simulator computes each one from the leakage of the queries so far.
\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{sse}}_{\Pi,\calA,\Sim,\calL}(\secpar)$}
\begin{algorithmic}
\State $b \getsr \bits$
\State $(\mathbf{D}, \stA) \gets \calA(1^\secpar)$
\State $K \gets \Gen(1^\secpar)$; $(I_0, \mathbf{c}_0) \gets \Enc(K, \mathbf{D})$
\State $(I_1, \mathbf{c}_1, \stS) \gets \Sim(1^\secpar, \calL_1(\mathbf{D}))$
\State $\calO_0(w) := \mathsf{Trpdr}(K, w)$
\State $\calO_1(w) := \Sim(\stS, \calL_2(\mathbf{D}, w_1, \ldots, w_i))$
\Comment{$w_1, \ldots, w_i$ are the queries so far, $w_i = w$; $\Sim$ updates $\stS$}
\State $b' \gets \calA^{\calO_b}(\stA, I_b, \mathbf{c}_b)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}
An SSE scheme is -adaptively secure if for all efficient there is an efficient such that
is negligible. CGKO06 introduce adaptive security with the simulator given their trace; CK10 state it for an arbitrary leakage function.
As an object, SSE denotes a -correct scheme with negligible that is -adaptively secure for the trace of CGKO06 defined in Leakage.
Non-adaptive security
The adversary fixes the collection and all its keywords before seeing any part of the encryption, and receives either the real index, documents and tokens or a simulation from their leakage — CGKO06.
\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{sse\text{-}na}}_{\Pi,\calA,\Sim,\calL}(\secpar)$}
\begin{algorithmic}
\State $b \getsr \bits$
\State $(\mathbf{D}, w_1, \ldots, w_q, \stA) \gets \calA(1^\secpar)$
\State $K \gets \Gen(1^\secpar)$; $(I, \mathbf{c}) \gets \Enc(K, \mathbf{D})$
\State $t_j \gets \mathsf{Trpdr}(K, w_j)$ for $j \in [q]$
\State $v_0 := (I, \mathbf{c}, t_1, \ldots, t_q)$
\State $v_1 \gets \Sim(1^\secpar, \calL_1(\mathbf{D}), \calL_2(\mathbf{D}, w_1, \ldots, w_q))$
\State $b' \gets \calA(\stA, v_b)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}
An SSE scheme is -non-adaptively secure if for all efficient there is an efficient such that
is negligible.
As an object, a non-adaptively secure SSE scheme denotes a -correct scheme with negligible that is -non-adaptively secure for the trace of CGKO06.
Variations
Dynamic SSE
A dynamic SSE scheme adds an update protocol with which the client adds documents to, and deletes documents from, the encrypted collection by sending update tokens; security adds a leakage function for updates, and the adversary interleaves searches and updates — KPR12. KPR12 construct a dynamic scheme, adaptively secure in the random-oracle model, whose search time is linear in — KPR12.
TODO: encode the dynamic SSE definition of KPR12 (search, add and delete tokens, correctness, and the adaptive real/ideal game with an update oracle, quantified over all efficient with an efficient for fixed setup, search, add and delete leakage functions), then register it as a variant.
Structured encryption
Structured encryption encrypts data organized in an arbitrary data structure, such as a matrix or a labeled graph, so that a server holding a token answers one type of query on it, with security relative to a leakage function as above; SSE is the case of a keyword index — CK10.
Other results
- The first SSE scheme encrypts every word of a document separately; the server tests each encrypted word against the token, so a search takes time linear in the total length of the collection — SWP00.
- SSE-1 is non-adaptively secure for the CGKO06 trace and searches in time linear in ; SSE-2 is adaptively secure for the CGKO06 trace; both use only symmetric-key primitives — CGKO06.
- An adversary that knows the indexed documents recovers queried keywords from the access pattern with the count attack, which matches the number of results of each query, and the number of documents two queries share, against counts computed from the documents — CGPR15.
- An adversary that adds documents of its choice to the collection learns the keyword of a later query from its access pattern after injecting documents, the -th containing the keywords whose index in has -th bit — ZKP16.