Databases Reference
In-Depth Information
may pose a query to the server to retrieve a subset of documents. The query
itself is a set of keywords and the answer corresponds to the set of documents
that contain all the keywords in the query. More formally, the answer to a
query
q
is given by:
D
i
}
The goal is to design techniques to retrieve answers while not revealing any
information beyond the presence (or absence) of the keywords (of the query)
in each document.
A few different variations of the basic keyword-search problem have been
studied over the past years [8, 18, 44, 11, 19, 7, 46]. The authors in [44, 11]
study the basic problem where a private-key based encryption scheme is used
to design a matching technique on encrypted data that can search for any
word in the document. Authors in [8] provide a safe public-key based scheme
to carry out “non-interactive” search on data encrypted using user's public-
key for a select set of words. [18] proposes a document indexing approach
using bloom filters that speeds up the keyword search algorithm but could
result in some false-positive retrievals. The work in [19, 7] propose secure
schemes for conjunctive keyword search where the search term might contain
the conjunction of two or more keywords. The goal here again is to avoid
any leakage of information over and above the fact that the retrieved set of
documents contain all the words specified in the query.
In this section, we describe a private-key based approach which is moti-
vated by [44] and was amongst the first published solutions to the problem of
searching over encrypted text data. The approach described incurs significant
overhead, requiring
O
(
n
) cryptographic operations per document where
n
is
the number of words in the document.
Ans
(
q
)=
{
D
i
∈
D
|∀
k
j
∈
q, k
j
∈
Private-Key based Search Scheme on Encrypted Text Data
Consider a data owner Alice who wishes to store a collection of documents
with Bob (the service provider). Alice encrypts each document
D
prior to
storing it with Bob. In addition, Alice creates a secure index,
I
(
D
), which is
stored at the service provider that will help her perform keyword search. The
secure index is such that it reveals no information about its content to the
adversary. However, it allows the adversary to test for presence or absence of
keywords using a
trapdoor
associated with the keyword where a trapdoor is
generated with a secret key that resides with the owner. A user wishing to
search for documents containing word
w
, generates a trapdoor for
w
which
can then be used by the adversary to retrieve relevant documents.
The secure index is created over the keywords in
D
as follows. Let doc-
ument
D
consist of the sequence of words
w
1
,...,w
l
. The index is created
by computing the bitwise XOR (denoted by the symbol
⊕
) of the clear-text
with a sequence of pseudo-random bits that Alice generates using a stream
