Databases Reference
In-Depth Information
for required, yet unavailable correctness-assured primitive queries constitute
a promising avenue of future research. As a result, SCPU processing will be
minimal and amortized over multiple query instances.
As an example, in the above multi-dimensional range query, a trusted
SCPU hosted by the server will instruct the main server CPU to execute
and prove correctness for the first predicate (
X
.
b
>
10
) and then evaluate
the second predicate (
X
.
c
>
20
) securely on the result. Heuristics could be
deployed to evaluate which of the individual predicates would result in a
smaller result set so as to minimize the SCPU computation. Optionally, the
process will also generate associated metadata for the joint predicate and
cache it on the server for future use, effectively amortizing the cost of this
query over multiple instances.
Operating in an
unified client model
[54, 104] assumes the existence of
a single client accessing the data store at any one time. In multi-threaded
data-intensive application scenarios however, such a model is often of limited
applicability. It is important to allow multiple client instances or even different
parties to simultaneously access outsourced data sets.
This is challenging because allowing different parties to access the same
data store may require the sharing of secrets among them. This is often not
a scalable proposition, in particular considering different administrative do-
mains. Moreover, data updates require special consideration in such a scenario
due to what we call the
“universe split” phenomenon
. We explain this in the
following.
In single - client settings, to eciently handle incoming data updates,
update-able metadata structures can be designed, e.g., leveraging such mecha-
nisms as the incremental hashing paradigm of Bellare and Micciancio [26]. Re-
cently we have demonstrated the feasibility of such methods in the framework
of network data storage. In [117] outsourced documents were incrementally
authenticated with ecient checksums allowing updates, document additions
and removals in constant time.
However, when two clients simultaneously access the same data sets, a
malicious server can chose to present to each client a customized version of
the data universe, by keeping the other client's updates hidden from the cur-
rent view. We believe other authors have encountered this issue in different
settings, e.g., by Li et al. [91] in an un-trusted networked file system setting
2
.
Naturally, if mutually aware of their accesses, the clients can use an external
authenticated channel to exchange transactional state on each other's updates.
This can occur either during their access, if simultaneous, or asynchronously
otherwise. Periodically executing such exchanges will significantly decrease the
probability of undetected illicit “universe split” server behavior. Over multiple
transactions, undetected malicious behavior will become unsustainable.
In practice, such awareness and online interaction assumptions are not al-
ways acceptable, and often the only potential point of contact between clients
2
In their work universe splitting would be the inverse of “fetch-consistency”
