10 Secure Outsourcing of Geographical Data
223
Fig. 10.2. An example of Merkle hash tree
structure, built in such a way that the tree leaves correspond to revoked certificates.
Thus, verifying whether a certificate is revoked or not is equivalent to verify the existence of certain leaves in the tree. Similar schemes have also been used for micropayments [10], where Merkle hash trees are used to minimize the number of public key
signatures that are required in issuing or authenticating a sequence of certificates.
Merkle hash trees have also been exploited for data outsourcing. For instance,
in [13] Devanbu et al. adapt Merkle hash trees to the relational data model to prove
the completeness and authenticity of query answers. In particular, in Devanbu et al.’s
approach for each relation R, a different Merkle hash tree is generated, in such a way
that leaf nodes represent hash values of tuples. Let us see how this enables a user
to verify answer authenticity, whereas we postpone the discussion on completeness
verification to Sect. 10.3.3. When a user submits a query on relation R, the publisher
replies him/her with the tuples answering the submitted query and the signature generated by exploiting the Merkle hash tree generated on R, plus the hash values of
the tuples of R not included in the result set. By having these additional hash values,
the user is able to validate the signature of R, and thus to prove authenticity of the
received tuples.
Merkle hash trees have also been investigated for third-party distribution of XML
data [5, 14]. Here the challenge is how the XML hierarchical data model can be
exploited in the construction of Merkle trees. A brief introduction of Merkle tree
application to XML documents is given in Sect. 10.4, and also we refer interested
readers to [5] for an in-depth presentation.
Signature Aggregation Schemes. Another technique recently exploited to ensure
authenticity in third-party architectures is based on signature aggregation. In general, signature aggregation schemes allow one to aggregate into a unique digital signature n distinct signatures generated by n distinct data owners [6]. The
validation of this unique digital signature implies the validation of each component
signature. Aggregate signature schemes have also been investigated to aggregate into
a unique signature n signatures generated by the same owner. This last kind of aggregation scheme can be adopted to ensure authenticity in third-party scenarios. Indeed,
according to this solution, a data owner could generate a distinct signature for each
223
Fig. 10.2. An example of Merkle hash tree
structure, built in such a way that the tree leaves correspond to revoked certificates.
Thus, verifying whether a certificate is revoked or not is equivalent to verify the existence of certain leaves in the tree. Similar schemes have also been used for micropayments [10], where Merkle hash trees are used to minimize the number of public key
signatures that are required in issuing or authenticating a sequence of certificates.
Merkle hash trees have also been exploited for data outsourcing. For instance,
in [13] Devanbu et al. adapt Merkle hash trees to the relational data model to prove
the completeness and authenticity of query answers. In particular, in Devanbu et al.’s
approach for each relation R, a different Merkle hash tree is generated, in such a way
that leaf nodes represent hash values of tuples. Let us see how this enables a user
to verify answer authenticity, whereas we postpone the discussion on completeness
verification to Sect. 10.3.3. When a user submits a query on relation R, the publisher
replies him/her with the tuples answering the submitted query and the signature generated by exploiting the Merkle hash tree generated on R, plus the hash values of
the tuples of R not included in the result set. By having these additional hash values,
the user is able to validate the signature of R, and thus to prove authenticity of the
received tuples.
Merkle hash trees have also been investigated for third-party distribution of XML
data [5, 14]. Here the challenge is how the XML hierarchical data model can be
exploited in the construction of Merkle trees. A brief introduction of Merkle tree
application to XML documents is given in Sect. 10.4, and also we refer interested
readers to [5] for an in-depth presentation.
Signature Aggregation Schemes. Another technique recently exploited to ensure
authenticity in third-party architectures is based on signature aggregation. In general, signature aggregation schemes allow one to aggregate into a unique digital signature n distinct signatures generated by n distinct data owners [6]. The
validation of this unique digital signature implies the validation of each component
signature. Aggregate signature schemes have also been investigated to aggregate into
a unique signature n signatures generated by the same owner. This last kind of aggregation scheme can be adopted to ensure authenticity in third-party scenarios. Indeed,
according to this solution, a data owner could generate a distinct signature for each