Databases Reference
In-Depth Information
In [104], mechanisms for ecient integrity and origin authentication for
simple selection predicate query results are introduced. Different signature
schemes (DSA, RSA, Merkle trees [100] and BGLS [37]) are explored as po-
tential alternatives for data authentication primitives. Mykletun et al. [57]
introduce
signature immutability
for aggregate signature schemes - the di-
culty of computing new valid aggregated signatures from an existing set. Such
a property is defeating a frequent querier that could eventually gather enough
signatures data to answer other (un-posed) queries. The authors explore the
applicability of signature-aggregation schemes for ecient data authentica-
tion and integrity of outsourced data. The considered query types are simple
selection queries.
Similarly, in [94], digital signature and aggregation and chaining mech-
anisms are deployed to authenticate simple selection and projection opera-
tors. While these are important to consider, nevertheless, their expressiveness
is limited. A more comprehensive, query-independent approach is desirable.
Moreover, the use of strong cryptography renders this approach less useful.
Often simply transferring the data to the client side will be faster.
In [108]
verification objects
VO are deployed to authenticate simple data
retrieval in “edge computing” scenarios, where application logic and data is
pushed to the edge of the network, with the aim of improving availability and
scalability. Lack of trust in edge servers mandates validation for their results
- achieved through verification objects.
In [77] Merkle tree and cryptographic hashing constructs are deployed to
authenticate the result of simple range queries in a publishing scenario in
which data owners delegate the role of satisfying user queries to a third-party
un-trusted publisher. Additionally, in [95] virtually identical mechanisms are
deployed in database outsourcing scenarios. [53] proposes an approach for
signing XML documents allowing untrusted servers to answer certain types
of path and selection queries.
Drawbacks of these efforts include the fact that they operate in an unrealis-
tic “semi - honest” adversarial model. As a result, for example, data updates
are not handled properly and the mechanisms are vulnerable to “universe
split” attacks discussed in section 2.2.
Moreover, deploying expensive cryptographic operations (e.g., aggregate
signatures, homomorphisms) has the potential to defeat the very purpose of
outsourcing. Unless the actual query predicates are comparably compute in-
tensive, often simply transferring the
entire
database and executing the query
on the client will be faster. This is the case simply because securely server -
processing a bit will be more expensive that the bit transfer over a network.
A detailed argument can be found in [118] and in section 2.4. Maybe most im-
portantly, existing solutions operate under un-realistic “cooperating” server
assumptions. For example, they are unable to address data updates. More
specifically, at the time of a client update, the server is assumed to
cooperate
in also updating corresponding server-side security checksums and signature
chains. A truly malicious server however, can choose to ignore such requests
