Databases Reference
In-Depth Information
Now, we look at some of the approaches proposed in literature for querying
encrypted relational data.
2.2 Querying Encrypted Relational Data
Consider a user Alice who outsources the database consisting of the following
two relations:
EMP (eid, ename, salary, addr, did)
DEPARTMENT (did, dname, mgr)
The fields in the
EMP
table refer to the employee id, name of the employee,
salary, address and the id of the department the employee works for. The fields
in the
DEPARTMENT
table correspond to the department id, department
name, and name of the manager of the department. In the DAS model, the
above tables will be stored at the service provider. Since the service provider is
untrusted, the relations must be stored in an encrypted form. Unless specified
otherwise, we will assume that data is encrypted at the row level; that is, each
row of each table is encrypted as a single unit. Thus, an encrypted relational
representation consists of a set of encrypted records.
The client
3
may wish to execute SQL queries over the database. For in-
stance, Alice may wish to pose following query to evaluate ”total salary for
employees who work for Bob”. Such a query is expressed in SQL as follows:
SELECT SUM(E.salary) FROM EMP as E, DEPARTMENT as D
WHERE E.did = D.did AND D.mgr = "Bob"
An approach Alice could use to evaluate such a query might be to request
the server for the encrypted form of the
EMP
and
DEPARTMENT
tables.
The client could then decrypt the tables and execute the query. This however,
would defeat the purpose of database outsourcing, reducing it to essentially
a remote secure storage. Instead, the goal in DAS is to process the queries
directly at the server without the need to decrypt the data. Before we discuss
techniques proposed in the literature we note that processing such queries
requires mechanisms to support the following basic operators over encrypted
data:
•
Comparison operators
such as =
,
,>
These operators may
compare attribute values of a given record with constants (e.g.,
DEPART-
MENT.sal >
45000 as in selection queries) or with other attributes (e.g.,
EMP.did = DEPARTMENT.did
as in join conditions).
=
,<,
≤
,
=
,
≥
•
Arithmetic operators
such as addition, multiplication, division that
perform simple arithmetic operations on attribute values associated with
a set of records in one or more relations. Such operators are part of any
SQL query that involves aggregation.
3
Alice in this case since we have assumed that the client and the owner is the same
entity.
