In the article Searchable Symmetric Encryption: Improved Definitions and Efficient Constructions, Curtmola et al. propose adaptive and non-adaptive (indistinguishability and simulator-based) security definitions for searchable encryption schemes, conventionally called IND-CKA1 and IND-CKA2.

My question is: Do the IND-CKA1/2 security definitions guarantee that the search pattern is not leaked (i.e., that an attacker can not distinguish whether two issued trapdoors are generated with the same keywords)?

In their article, they mention that

[...] the security notion achieved for SSE is that nothing is leaked beyond the access pattern and the search pattern [...]

Further, in their article, Bösch et al. state that

Curtmola et al. review existing security definitions for searchable encryption and propose new indistinguishability and simulation-based definitions that address the shortcomings of the existing definitions. At the same time they loosen the character of SSE by allowing the leakage of a user's search pattern.

So it seems pretty obvious that the definition should not guarantee search pattern hiding. Nevertheless, taking a look at the IND-CKA2 definition:

$\mathbf{\mathrm{Ind}}^{*}_{\mathrm{SSE},\mathcal{A}}(k) \\ \;K\leftarrow \mathrm{Gen}(1^k)\\ \;b\overset{\$}{\leftarrow}\{0,1\}\\ \;(\mathrm{st}_{\mathcal{A}},\mathbf{D}_{0},\mathbf{D}_{1})\leftarrow\mathcal{A}_{0}(1^k)\\ \;(I_{b},\mathbf{c}_{b})\leftarrow\mathrm{Enc}_{K}(\mathbf{D}_{b})\\ \;(\mathrm{st}_{\mathcal{A}},w_{0,1},w_{1,1})\leftarrow\mathcal{A}_{1}(\mathrm{st}_\mathcal{A},I_{b})\\ \;t_{b,1}\leftarrow\mathrm{Trpdr}_{K}(w_{b,1})\\ \;\mbox{for }2\le i\le q,\\ \quad(\mathrm{st}_{\mathcal{A}},w_{0,i},w_{1,i})\leftarrow\mathcal{A}_{i}(\mathrm{st}_{\mathcal{A}},I_{b},c_{b},t_{b,1},\ldots,t_{b,i-1})\\ \quad t_{b,i}\leftarrow\mathrm{Trpdr}_{K}(w_{b,i})\\ \;\mbox{let }\mathbf{t}_{b}=(t_{b,1},\ldots,t_{b,q})\\ \;b'\leftarrow \mathcal{A}_{q+1}(\mathrm{st}_{\mathcal{A}},I_{b},\mathbf{c}_{b},\mathbf{t}_{b})\\ \;\mbox{if }b'=b\mbox{, output }1\\ \;\mbox{otherwise output }0$

one sees that any algorithm able to distinguish whether two trapdoors encode the same words or not directly breaks IND-CKA2, which would mean that IND-CKA2 protects against search pattern leakage.

For instance, and very informally, in the first trapdoor query $\mathcal{A}$ can set $w_{0,1}=w_{1,1}=w_{1}$ for some fixed $w_{1}$ and receive $t_{b,1}=\mathrm{Trpdr}_{K}(w_{1})$. In the second query, it can issue $w_{0,2}=w_{1}$ and $w_{1,2}\neq w_{1}$. Then $t_{b,2}$ either encodes $w_{1}$ or some other word, and $\mathcal{A}$ can guess $b$ by guessing whether $t_{b,1}$ and $t_{b,2}$ encode the same word ($b=0$) or not ($b=1$). Continuing in this fashion, since $\mathcal{A}$ breaks the "search pattern challenge", $\mathcal{A}$ has a non-negligible advantage in distinguishing $b$.


1 Answer 1


The condition $\tau(\mathbf{D}_{0}, w_{0,1},\ldots,w_{0,q})=\tau(\mathbf{D}_{1}, w_{1,1},\ldots,w_{1,q})$ rules out the possibility that $\mathcal{A}$ issues the keywords as I pointed in the question, since the output of $\tau$ includes the search pattern matrix defined in page 9. This has the effect of weakening the definition to allow search pattern leakage.

As a note, the stronger definition in Shen et al.'s 1 does not include a restriction of this type, and so it captures the search pattern protection property.

1 Shen, Emily, Elaine Shi, and Brent Waters. “Predicate Privacy in Encryption Systems.” In Theory of Cryptography, edited by Omer Reingold, 5444:457–73. Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2009.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.