224
Barbara Carminati and Elena Ferrari
distinct message
6 and then aggregate them into a unique digital signature. By having
only the aggregate signature and by simply validating it, a user is able to authenticate selected messages received by third-party. Let us consider, for instance, how this
solution could be applied to relational data. Let us assume that the owner generates
a different signature for each tuple belonging to a relation R and then outsources
to publishers all these signatures together with the corresponding tuples. When a
user submits a query on relation R, the publisher evaluates the query on R. Then,
it aggregates all the signatures corresponding to the tuples in the result set, and returns to the user the resulting aggregate signature, as well as the tuples answering the
query. By the properties of aggregate signatures, the user, by simply verifying the
aggregate signature generated by publisher, is able to validate all tuples’ signatures
generated by the owner, and thus to prove tuples’ authenticity. Such a solution has
been proposed by Mykletun et al. in [19] for relational data, where two different aggregate signature schemes, namely condensed-RSA and Boneh et al. [6], have been
compared.
10.3.3 Completeness
Completeness is a novel property that is receiving growing attention due to its relevance in data outsourcing. So far completeness property has been investigated by few
research groups, but three strategies have been proposed to ensure completeness of
query answers in third-party architectures. In particular, two of them have been proposed for relational data [13, 22], whereas the third is for third-party distribution of
XML data [5]. In what follows we introduce approaches for relational data, and we
postpone completeness for XML data to Sect. 10.4. Completeness for relational data
has been investigated in conjunction with authenticity and integrity requirements.
The proposed solutions exploit Merkle hash tree mechanisms and aggregate signature schemes. However, it is interesting to note that despite the different exploited
mechanisms they obtain a similar result, in that both the approaches presented in [13]
and in [22] enable a user to prove answer completeness of range queries only. Let
us introduce how this is possible by means of Merkle hash trees. The approach presented in [13] assumes that Merkle hash trees are built over tuples sorted according
to a given attribute a and that the range query’s predicate is against a. To enable the
user to verify the answer’s completeness, the third-party inserts in the answer two
additional tuples, that is, a tuple preceding (subsequent) the lower (upper) bound of
the result set answering the range query. By having these two values, the user can
locally verify that the query answer is complete, that is, that no tuples answering the
range query have been omitted. Indeed, by verifying the owner’s signature, which
has been generated on a Merkle hash tree built over sorted tuples, the user also verifies thatthe received lower (upper) tuple effectively precedes (follows) the ones in
6 Here message has a general meaning. On the basis of the scenario, a message could be a
relational tuple, a node (i.e. element or attribute) of an XML document, or more generally
a data portion.
Barbara Carminati and Elena Ferrari
distinct message
6 and then aggregate them into a unique digital signature. By having
only the aggregate signature and by simply validating it, a user is able to authenticate selected messages received by third-party. Let us consider, for instance, how this
solution could be applied to relational data. Let us assume that the owner generates
a different signature for each tuple belonging to a relation R and then outsources
to publishers all these signatures together with the corresponding tuples. When a
user submits a query on relation R, the publisher evaluates the query on R. Then,
it aggregates all the signatures corresponding to the tuples in the result set, and returns to the user the resulting aggregate signature, as well as the tuples answering the
query. By the properties of aggregate signatures, the user, by simply verifying the
aggregate signature generated by publisher, is able to validate all tuples’ signatures
generated by the owner, and thus to prove tuples’ authenticity. Such a solution has
been proposed by Mykletun et al. in [19] for relational data, where two different aggregate signature schemes, namely condensed-RSA and Boneh et al. [6], have been
compared.
10.3.3 Completeness
Completeness is a novel property that is receiving growing attention due to its relevance in data outsourcing. So far completeness property has been investigated by few
research groups, but three strategies have been proposed to ensure completeness of
query answers in third-party architectures. In particular, two of them have been proposed for relational data [13, 22], whereas the third is for third-party distribution of
XML data [5]. In what follows we introduce approaches for relational data, and we
postpone completeness for XML data to Sect. 10.4. Completeness for relational data
has been investigated in conjunction with authenticity and integrity requirements.
The proposed solutions exploit Merkle hash tree mechanisms and aggregate signature schemes. However, it is interesting to note that despite the different exploited
mechanisms they obtain a similar result, in that both the approaches presented in [13]
and in [22] enable a user to prove answer completeness of range queries only. Let
us introduce how this is possible by means of Merkle hash trees. The approach presented in [13] assumes that Merkle hash trees are built over tuples sorted according
to a given attribute a and that the range query’s predicate is against a. To enable the
user to verify the answer’s completeness, the third-party inserts in the answer two
additional tuples, that is, a tuple preceding (subsequent) the lower (upper) bound of
the result set answering the range query. By having these two values, the user can
locally verify that the query answer is complete, that is, that no tuples answering the
range query have been omitted. Indeed, by verifying the owner’s signature, which
has been generated on a Merkle hash tree built over sorted tuples, the user also verifies thatthe received lower (upper) tuple effectively precedes (follows) the ones in
6 Here message has a general meaning. On the basis of the scenario, a message could be a
relational tuple, a node (i.e. element or attribute) of an XML document, or more generally
a data portion.