222
Barbara Carminati and Elena Ferrari
Asymmetric encryption relies on the definition of a pair of keys for each user, a public
and a private key. These keys are defined in such a way that a message encrypted with
the public key can be decrypted only by using the private key, and vice versa. Public
keys are available to anyone who needs them, whereas private keys should be kept
secret. The sender computes the digest of the data being signed, that is, numerical
summary or fingerprint computed using a one-way hash function. By the properties
of one-way hash functions, it is infeasible to change a message digest back into the
original data from which it was created. Then, the digest is encrypted with the private
key. The receiver first decrypts the signature using the sender’s public key, changing
it back into a digest. The receiver then computes the message digest of the received
data and compares it with the decrypted one. If the two coincide, then the receiver
knows that the signed data has not been altered during transmission and that data
has been generated by the sender, because only the sender has the corresponding
private key. As pointed out in Sect. 10.2, such scheme is not suitable for third-party
architectures. This is mainly due to the fact that users must be able to validate the
owner’s signature even if they receive a selected portion of the signed data. A naive
solution to overcome this problem, but still exploiting traditional signature schemes,
is to force the owner to separately sign each possible portion of data. This set of
digital signatures could be outsourced together with the data, and could be properly
returned to the users by the publisher. However, this solution implies an enormous
overhead both in owner computation and in query answer size. For this reason, in
recent years, several alternative strategies have been presented. We can group these
strategies on the basis of the underlying adopted techniques. In particular, there are
two main exploited techniques, that is, Merkle tree authentication [20] and signature
aggregation [6]. In what follows we present them by introducing some of the related
proposals.
Merkle Trees. In [20], Merkle proposed a method to sign multiple messages, by
producing a unique digital signature. The method exploits a binary hash tree generated by means of the following bottom-up recursive construction: at the beginning,
for each different message m, a different leaf containing the hash value of m is inserted in the tree; then, for each internal node, the value associated with it is equal to
H(h l ||h r ), where h l ||h r denotes the concatenation of the hash values corresponding to
the left and right children nodes (see Fig. 10.2), and H() is an hash function.
The root node of the resulting binary hash tree can be considered as the digest
of all messages, and thus it can be digitally signed by using a standard signature
technique and distributed. The main benefit of this method is that a user is able
to validate the signature by having a subset of messages, providing him/her with a
set of additional hash values. Indeed, a user, by having hash values of the missing
messages, is able to locally build up the binary hash tree and thus to validate the
signature.
Merkle hash trees have been used in several computer areas for certified query
processing. For instance, they have been exploited by Naor and Nissim in [21]
to create and maintain efficient authenticated data structures holding information
about certificates validity. More precisely, [21] proposes a sorted hash tree as data
Barbara Carminati and Elena Ferrari
Asymmetric encryption relies on the definition of a pair of keys for each user, a public
and a private key. These keys are defined in such a way that a message encrypted with
the public key can be decrypted only by using the private key, and vice versa. Public
keys are available to anyone who needs them, whereas private keys should be kept
secret. The sender computes the digest of the data being signed, that is, numerical
summary or fingerprint computed using a one-way hash function. By the properties
of one-way hash functions, it is infeasible to change a message digest back into the
original data from which it was created. Then, the digest is encrypted with the private
key. The receiver first decrypts the signature using the sender’s public key, changing
it back into a digest. The receiver then computes the message digest of the received
data and compares it with the decrypted one. If the two coincide, then the receiver
knows that the signed data has not been altered during transmission and that data
has been generated by the sender, because only the sender has the corresponding
private key. As pointed out in Sect. 10.2, such scheme is not suitable for third-party
architectures. This is mainly due to the fact that users must be able to validate the
owner’s signature even if they receive a selected portion of the signed data. A naive
solution to overcome this problem, but still exploiting traditional signature schemes,
is to force the owner to separately sign each possible portion of data. This set of
digital signatures could be outsourced together with the data, and could be properly
returned to the users by the publisher. However, this solution implies an enormous
overhead both in owner computation and in query answer size. For this reason, in
recent years, several alternative strategies have been presented. We can group these
strategies on the basis of the underlying adopted techniques. In particular, there are
two main exploited techniques, that is, Merkle tree authentication [20] and signature
aggregation [6]. In what follows we present them by introducing some of the related
proposals.
Merkle Trees. In [20], Merkle proposed a method to sign multiple messages, by
producing a unique digital signature. The method exploits a binary hash tree generated by means of the following bottom-up recursive construction: at the beginning,
for each different message m, a different leaf containing the hash value of m is inserted in the tree; then, for each internal node, the value associated with it is equal to
H(h l ||h r ), where h l ||h r denotes the concatenation of the hash values corresponding to
the left and right children nodes (see Fig. 10.2), and H() is an hash function.
The root node of the resulting binary hash tree can be considered as the digest
of all messages, and thus it can be digitally signed by using a standard signature
technique and distributed. The main benefit of this method is that a user is able
to validate the signature by having a subset of messages, providing him/her with a
set of additional hash values. Indeed, a user, by having hash values of the missing
messages, is able to locally build up the binary hash tree and thus to validate the
signature.
Merkle hash trees have been used in several computer areas for certified query
processing. For instance, they have been exploited by Naor and Nissim in [21]
to create and maintain efficient authenticated data structures holding information
about certificates validity. More precisely, [21] proposes a sorted hash tree as data