Databases Reference
In-Depth Information
the updates to the server. The first option is for the owner to transmit only
a delta table with the updated nodes of the MB-tree (or EMB-tree) plus the
signed root. The second option is to transmit only the signed root and the
updates themselves and let the servers redo the necessary computations on
the tree. The first approach minimizes the computation cost on the servers but
increases the communication cost, while the second approach has the opposite
effect.
5 Query Freshness
The dynamic scenarios considered before reveal a third dimension of the query
authentication problem, that of
query result freshness
. When the owner up-
dates the database, a malicious or compromised server may still retain an
older version of the data. Since the old version was authenticated by the
owner already, the client will still accept any query results originating from
an old version as authentic, unless the latter is informed by the owner that
this is no longer the case. In fact, a malicious server may choose to answer
queries using any previous version, and in some scenarios even a combination
of older versions of the data. If the client wishes to be assured that queries
are answered using the latest data updates, additional work is necessary.
This issue is similar to the problem of ensuring the freshness of signed
documents, which has been studied extensively in the context of certificate
validation and revocation. There are many approaches which we do not review
here. The simplest is to publish a list of revoked signatures, one for every
expired version of the database. More sophisticated ones are: 1. Including
the time interval of validity as part of the signed root of the authenticated
structures and reissuing the signature after the interval expires, 2. Using hash
chains to confirm validity of signatures at frequent intervals [33].
Clearly, all signature freshness techniques impose a cost which is linear to
the number of signatures used by any authentication structure. The advantage
of the Merkle tree based methods is that they use one signature only — that
of the root of the tree — which is sucient for authenticating the whole
database. Straightforwardly, database updates will also require re-issuing only
the signature of the root.
6 Extensions
This section extends our discussion to other interesting topics that are related
to the query authentication problem.
Multi-dimensional Selection and Aggregation Range Queries.
The
same ideas that we discussed before can be used for authenticating multi-
dimensional range queries. In particular, any tree based multi-dimensional
