Databases Reference
In-Depth Information
perform comparisons. While information hiding techniques work for relational
operators, they do not work for arithmetic operators such as aggregation. No-
tice that in the previous query there is an aggregation but that aggregation is
done at the client side after decryption. If aggregation is to be performed at
the server side, the information hiding approach has to be augmented with an
encryption approach that supports arithmetic operations on encrypted rep-
resentation. [27] illustrates how
privacy homomorphisms
(PH) [39, 16] can
be combined with the basic approach described above for this purpose. Ad-
ditional complexities arise since the information hiding technique does not
exactly identify the target group to be aggregated (i.e., the server side results
typically contain false positives). The paper develops algebraic manipulation
techniques to separate an aggregation group into two subsets a set that
cer-
tainly
qualifies the conditions specified in the query, and a set that
may or
may not
satisfy the selection predicates of the query (i.e., could contain false
positives). The first set can be directly aggregated at the server using PH
while the tuples belonging to the second category will need to be transmitted
to the client side to determine if they indeed satisfy the query conditions.
Query Optimization in DAS:
As in traditional relational query evaluation, in
DAS multiple equivalent realizations for a given query are possible. This nat-
urally raises the challenge of query optimization. In [24], query optimization
in DAS is formulated as a cost-based optimization problem by introducing
new query processing functions and defining new query transformation rules.
The intuition is to define transfer of tuples from server to the client and de-
cryption at the client as operators in the query tree. Given different hardware
constraints and software capabilities at the client and the server different cost
measures are applied to the client-side and server-side computations. A novel
query plan enumeration algorithm is developed that identifies the least cost
plan.
Now, having given a summary of the various techniques for handling en-
crypted relational data we move onto encryption of text data.
2.4 Keyword search on encrypted text data
In this section we discuss approaches proposed in the literature to support
keyword based retrieval of text documents. The majority of the techniques
proposed in literature are cryptographic in nature. Let Alice be the data owner
who has a collection of text documents
D
=
{
D
1
,...,D
n
}
. A document
D
i
is
W
D
1
,...,W
D
i
modelled as a set of keywords
D
i
=
,and
(
W
) is the set of all possible keywords. Alice stores her document collection
at a service provider. Since the service provider is not trusted, documents are
stored encrypted. Each document is encrypted at the word level as follows:
Each document is divided up into equal length “words”. Typically each such
word corresponds to an English language word where extra padding (with '0'
and '1' bits) are added to make all words equal in length. Periodically Alice
{
n
i
}
, each word
w
∈W
