Secure conjunctive keyword search over encrypted data
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.