Databases Reference
In-Depth Information
3.2 Authentication & Integrity issues
When a client queries the data on the server, he expects in return a set of
records satisfying the query predicates. A query on a single relational table
having
m
rows for instance, may require any one of the possible 2
m
possible
different subsets to be retrieved. The problem then is that of facilitating secure
and ecient authentication of all possible query replies. Authors in [37] look at
the problem when the server cannot be trusted with the integrity of the data.
In other words, if the malicious server or an adversary inserts fake records
into the database or modifies existing records, the client wants to detect this
eciently, without spending too much resources. This work concentrates only
on simple query predicates involving relational operators like =,
<
,
≤
,
≥
,and
>
.
Data integrity and authentication can be provided at different levels of
granularity. In principle, integrity checks can be at the level of a table, a col-
umn, a row (record), or an individual field (attribute) value in a row. Record-
level integrity checking is thought to be the best choice to balance the tradeoff
between flexibility of query answering and overhead of integrity checking. The
authors look at 3 different scenarios: unified client model (where the client and
data owner are one and the same entity), multiple clients-single owner and
multiple clients-multiple owners.
The simplest approach for a client scenario is to store for each record a
message authentication code
(MAC) of that record. MAC is a keyed hash of
the record's content. The secret key is known only to the client and therefore
computable only at the client. The MAC-s tend to be small and of constant
length, therefore making them easier to handle. Then with a query response,
the server inserts a single integrity check computed as a hash (not a keyed
hash) of all record-level MAC-s in the query reply which the client can verify.
With a very high probability such hashes will be collision-free, i.e., distinct
for different sets of records. The advantage of this approach is that bandwidth
overhead is minimal and the computation overhead at the client is low.
The MAC-s are attractive for the unified client model, but in multi owner
and multi querier models, one would require the MAC key to be shared be-
tween all the entities. This means non-repudiation for the queriers cannot be
achieved. Instead of MAC-s, public-key digital signatures can be used for in-
tegrity checking (verification), i.e., the record content is encrypted using the
owner's private key and verified by the client by decrypting it with the owner's
public key.
In using public key algorithms for verification, the eciency issues become
a key concern due to their substantially higher complexity. The proposed so-
lution is to carry out some form of
signature aggregation
which allows the
client to aggregate multiple individual signatures into one unified signature.
Authors in [37] suggest two aggregation based signature verification schemes,
one uses the RSA encryption algorithm and the other uses elliptic-curve and
bilinear mappings to aggregate multiple signatures into one. The
condensed-
