Databases Reference
In-Depth Information
will pursue designs that use such hardware only as a trusted-aide, while con-
sidering its limited I/O and computation throughput. For example, we be-
lieve ecient solutions can be achieved by balancing a storage-computation
trade-off when main un-secured storage capacity is significantly cheaper than
the purchase of additional secure computation elements. In such a model,
additional secure metadata structures are constructed over the outsourced
data, by both clients and SCPUs. These enable the unsecured main CPU to
perform computation-intensive portions of secure queries without requiring
trusted hardware support. The cost of constructing these additional
helper
data structures will be amortized over multiple query instances.
We use the term
encryption
to denote any semantically secure (IND-CPA)
encryption mechanism [65], unless specified otherwise. We note that the mech-
anisms introduced here do not depend on any specific encryption mechanism.
A
one-way cryptographic hash
H
() is a function with two important properties
of interest: (i) it is computationally infeasible, for a given value
V
to find a
V
such that
H
(
V
)=
V
(one-wayness), and (ii) changing even one bit of the hash
input causes random changes to the output bits (i.e., roughly half of them
change even if one bit of the input is flipped). Examples of potential candi-
dates are the MD5 (fast) or the SHA class of hashes (more secure).
Bloom
filters
[35] offer a compact statistical representation of a set of data items and
fast set inclusion tests. They are
one-way
, in that, the “contained” set items
cannot be enumerated easily. For more details see [65, 113].
2.2 Query Correctness
Informally, we will call a query mechanism
correct
if the server is bound
to the sequence of update requests performed by the client. Either the server
responds correctly to a query or its malicious behavior is immediately detected
by the client:
Definition 1.
A query protocol is correct, if (except with
negligible
probability
[65]) for all traces
T
with
T
≈
Q
T
T
and
, any query Q and server response
D
T
,Q
, we have
Cli(
T
,Q,D
T
,Q
)=
⊥
.
In applied settings,
correctness
in database outsourcing can be often de-
composed into two protocol properties, namely
data integrity
and
query com-
pleteness
. Data integrity guarantees that outsourced data sets are not tam-
pered with by the server. Completeness ensures that queries are executed
against their entire target data sets and that query results are not 'truncated”
by servers.
Existing work focuses mostly on solutions for simple one-dimensional range
queries, and variants thereof. In a publisher-subscriber model, Devanbu et
al. deployed Merkle trees to authenticate data published at a third party's
site [54], and then explored a general model for authenticating data structures
[97,98]. Hard-to-forge verification objects are provided by publishers to prove
the authenticity and provenance of query results.
