Databases Reference
In-Depth Information
ficiently. Moreover, it is important to design for scalability to large data
sets and high query throughputs. We note that client
authentication
and
authorization
, two important but orthogonal security dimensions, are exten-
sively addressed in existing research, discussed in both this topic and else-
where [22, 27, 31, 33, 39, 68, 75, 79, 80, 88, 90, 102, 103, 105, 123]; therefore they
and are not the main focus here. The assurances discussed here naturally
complement these dimensions in providing increased end-to-end security.
2 Designing Secure Data Outsourcing Mechanisms.
2.1 Model
In our discourse, we will consider the following concise yet representative
interaction model. Sensitive data is placed by a client on a database server
managed by a
database service provider
. Later, the client or a third party
will access the outsourced data through an online query interface exposed by
the server. Network layer confidentiality is assured by mechanisms such as
SSL/IPSec.
We will represent both the server and the client as interactive polynomial-
time Turing Machines; we write Cli for the client and Serv for the server
machine. A client can interact with the server and issue a sequence of update
or processing queries (
Q
1
,...,Q
i
). We call such a sequence of queries a
trace
T
. After executing a query
Q
, the client Turing Machine either outputs
or
, indicating whether the client accepts or rejects the server's response
(denoted as
D
T ,Q
); in the first case, the client believes that the server replied
honestly. We write Cli(
⊥
to denote the output of the
client as a result of the server's execution of trace
T
,Q,D
T ,Q
)
∈{
,
⊥}
T
and query
Q
yielding the
result
D
T ,Q
.
A server's response
D
is said to be
consistent
with both
and
Q
,ifan
honest server, after starting with an empty database and executing trace
T
T
T
are called
honestly, would reply with
D
to the query
Q
. Two traces
T
and
T≈
Q
T
, if the query
Q
yields the same
similar
with respect to
Q
, written as
T
, i.e.,
D
T ,Q
=
D
T
,Q
.
The data server is considered to be un-trusted, potentially malicious, com-
promised or simply faulty. Given the possibility to get away undetected, it
will attempt to compromise data confidentiality, infer data access patterns
and return incorrect query results. In certain cases we will assume reason-
able computational limits such as the inability to factor large numbers or find
cryptographic hash collisions. We will not make any limiting assumptions on
the DBMS. In particular we will accommodate both multi-processor and dis-
tributed query processing DBMS. We will collaborate with other researches
to investigate how to accommodate non-relational data integration [17] but
mention that this does not constitute the subject of this work.
answer when queried after a trace
T
or
