Abstract:
We study the setting in which a user stores encrypted documents (e.g.
e-mails) on an untrusted server. In order to retrieve documents satisfying
a certain search criterion, the user gives the server a capability
that allows the server to identify exactly those documents. Work in
this area has largely focused on search criteria consisting of a single
keyword. If the user is actually interested in documents containing each
of several keywords ( conjunctive keyword search) the user must
either give the server capabilities for each of the keywords individually
and rely on an intersection calculation (by either the server or the user)
to determine the correct set of documents, or alternatively, the user may
store additional information on the server to facilitate such searches.
Neither solution is desirable; the former enables the server to learn
which documents match each individual keyword of the conjunctive search
and the latter results in exponential storage if the user allows for
searches on every set of keywords.
We define a security model for conjunctive keyword search over encrypted data and present the first schemes for conducting such searches securely. We propose first a scheme for which the communication cost is linear in the number of documents, but that cost can be incurred "offline" before the conjunctive query is asked. The security of this scheme relies on the Decisional Diffie-Hellman (DDH) assumption. We propose a second scheme whose communication cost is on the order of the number of keyword fields and whose security relies on a new hardness assumption.