Databases Reference
In-Depth Information
errors). Hence, this model raises important issues on how to guarantee quality
of service in untrusted database management environments, which translates
into providing verification proofs to both data owners and clients that the
information they process is correct.
Three main entities exist in the ODB model as discussed so far: the data
owner, the database service provider (a.k.a. server) and the client. In prac-
tice, there is a single or a few data owners, a few servers, and many clients.
The data owners create their databases, along with the necessary index and
authentication structures, and upload them to the servers. The clients issue
queries about the owner's data through the servers, which use the authenti-
cation structures to provide provably correct answers. It is assumed that the
data owners may update their databases periodically and, hence, authentica-
tion techniques should be able to support dynamic updates. In this setting,
query authentication has three important dimensions:
correctness
,
complete-
ness
and
freshness
. Correctness means that the client must be able to validate
that the returned answers truly exist in the owner's database and have not
been tampered with. Completeness means that no answers have been omitted
from the result. Finally, freshness means that the results are based on the most
current version of the database, that incorporates the latest owner updates.
It should be stressed here that result freshness is an important dimension of
query authentication that is directly related to incorporating dynamic updates
into the ODB model.
There are a number of important costs pertaining to the aforementioned
model, relating to the database construction, querying, and updating phases.
In particular, in this chapter the following metrics are considered: 1. The
computation overhead for the owner, 2. The owner-server communication cost,
3. The storage overhead for the server, 4. The computation overhead for the
server, 5. The client-server communication cost, and 6. The computation cost
for the client (for verification).
It should be pointed out that there are other important security issues in
ODB systems that are orthogonal to the problems considered here. Exam-
ples include privacy-preservation issues [2, 3, 4], secure query execution [5],
security in conjunction with access control requirements [6, 7, 8, 9] and query
execution assurance [10]. Aslo, we concentrate on large databases that need
to be stored on external memory. Therefore, we will not discuss main memory
structures [11, 12, 13] or data stream authentication [14, 15].
2 Cryptographic Background
In this section we discuss some basic cryptographic tools. These tools are
essential components of the authentication data structures that we discuss
later.
