Databases Reference
In-Depth Information
The example query given above illustrates usage of both classes of oper-
ators. For instance, to execute the query, the
mgr
field of each record in the
DEPARTMENT
table has to be compared with “Bob”. Furthermore, records
in the
DEPARTMENT
table whose
mgr
is “Bob” have to be matched with
records in
EMP
table based on the
did
attribute. Finally, the
salary
fields of
the corresponding record that match the query conditions have to be added
to result in the final answer.
The first challenge in supporting SQL queries over encrypted relational
representation is to develop mechanisms to support comparison and arithmetic
operations on encrypted data. The techniques developed in the literature can
be classified into the following two categories.
Approaches based on new encryption techniques:
These techniques
can support either arithmetic and/or comparison operators directly on en-
crypted representation. Encryption techniques that support limited compu-
tation without decryption have been explored in cryptographic literature in
the past. Amongst the first such technique is the
privacy homomorphism
(PH)
developed in [39, 16] that supports basic arithmetic operations. While PH can
be exploited to compute aggregation queries at the remote server (see [27] for
details), it does not allow comparison and, as such, cannot be used as basis for
designing techniques for relational query processing over encrypted data. In
[4], the authors developed a data transformation technique that preserves the
order in the original data. Such a transformation serves as an
order-preserving
encryption and can therefore support comparison operators. Techniques to im-
plement relational operators such as selection, joins, sorting, grouping can be
built on top of the order preserving encryption. The encryption mechanism,
however, cannot support aggregation at the server. While new cryptographic
approaches are interesting, one of the limitation of such approaches has been
that they are safe only under limited situations where the adversary's knowl-
edge is limited to the ciphertext representation of data. These techniques have
either been shown to break under more general attacks (e.g., PH is not secure
under chosen plaintext attack [6, 10]), or the security analysis under diverse
types of attacks has not been performed.
Information-hiding based Approaches:
Unlike in encryption based ap-
proaches, such techniques store additional auxiliary information along with
encrypted data to facilitate evaluation of comparison and/or arithmetic oper-
ations at the server. Such auxiliary information, stored in the form of indices
(which we refer to as
secure indices
) may reveal partial information about the
data to the server. Secure indices are designed carefully exploiting information
hiding mechanisms (developed in the context of statistical disclosure control)
[48, 47, 1] to limit the amount of information disclosure. The basic techniques
used for disclosure control are the following [47, 1]:
1.
Perturbation:
For a numeric attribute of a record, add a random value
(chosen from some distribution, like normal with mean 0 and standard
deviation
σ
) to the true value.
