Databases Reference
In-Depth Information
query - specific metadata that enables correctness assurance protocols for a
set of primitive queries, and (2) mechanisms for trusted hardware.
In (1), additional server-side storage will be traded for ecient correctness
assurances. At outsourcing time, in a pre-processing phase, clients generate
query and predicate - specific metadata that will be stored on the server,
authenticated by minimal state information maintained by clients. For each
considered primitive predicate and type of query (e.g., simple range query),
its corresponding “correctness metadata” will allow the client (or a trusted
proxy such as a secure CPU) to assess the correctness of individual results. We
call such primitive queries for which correctness can be assessed, “correctness-
assured”.
It is important to build on existing work [57, 77, 94, 95, 104], to reduce
the computational footprint on the server, and allow consistent handling of
updates in the presence of a truly malicious server. For example, we believe
incremental hashing paradigms can be deployed to persist client-side authenti-
cation information. This will allow a client to eciently authenticate returned
signature values, thus detecting any malicious behavior even after updates.
Another future work item will be to design techniques that decompose
or rewrite complex queries into a subset of the primitive queries considered
above. Consider the following simple, yet illustrative query listing all account
holders with account rates less than the Federal Reserve's base rate on January
1st, 2006:
SELECT accounts.name FROM accounts WHERE accounts.rate <
(SELECT federalreserve.baserate FROM federalreserve
WHERE convert(char(10),federalreserve.date,101)='01/01/2006')
Its correctness can be eciently assessed by requiring the server to prove
correctness for the inner query first, followed by the outer query. Similar de-
compositions can be applied to any correctness-assured nested queries. Never-
theless, often such query decomposition or rewriting cannot be achieved with
eciency for arbitrary queries in fully unsecured environments. For example,
it is not trivial to extend correctness - assured simple range predicates to even
marginally more complex multi-dimensional range queries such as
SELECT X.a FROM X WHERE X.b > 10 AND X.c > 20
It is important to investigate composition mechanisms that allow the utiliza-
tion of metadata ensuring correctness of either simple range predicate (e.g.,
X
.
b
>
10
or
X
.
c
>
20
), to guarantee correctness for the composite predicate.
To achieve correctness assurances for a larger class of queries we propose
to consider mechanisms that leverage the presence of active secure hardware
such as secure co-processors (SCPUs). Achieving eciency however, is an
extremely challenging task. Trivially deploying query processor functionality
inside power - constrained SCPUs is simply not scalable in practice due to
limited communication and computation throughputs. We believe protocols
that combine the query decomposition approach in (1) with SCPU processing
