10 Secure Outsourcing of Geographical Data
219
10.3.1 Confidentiality
The main efforts carried out to address confidentiality in third-party architectures
have been focused on confidentiality with respect to publishers [15–17, 26] only.
What is interesting to note is that all the proposals enforce confidentiality by means
of cryptographic-based solutions. More precisely, the common underlying idea of
all these approaches is that data owners outsource to publishers an encrypted version of the data they are entitled to manage, without providing the corresponding decryption keys. Thus, the publisher is not able to access and, as a consequence, to misuse outsourced data. Obviously, applying such a solution to a thirdparty scenario implies considering an interesting problem; that is how to make
publishers able to evaluate queries on encrypted data, without accessing them. In
recent years, this problem has been investigated in depth by several researchers, with
two main resulting solutions [17, 26] that work for different data models. In what
follows, we briefly introduce the method proposed in [15–17] to query encrypted
relational databases, and the cryptographic scheme presented in [26] to query encrypted textual data.
Hagicumus et al. The approach proposed by Hacigumus et al. [15–17] exploits binning techniques and privacy homomorphic encryption to query encrypted relational
data. More precisely, binning techniques are used to perform selection queries on
encrypted relation data, whereas homomorphic encryption [25] is used to enable a
third-party to perform aggregate queries over encrypted tuples. Let us start to describe how, by partitioning relation data domains, Hacigumus et al.’s approach enables third parties to evaluate selection queries. The basic idea is that for each relation
R the owner divides the domain of each attribute in R into distinguished partitions, to
which it assigns a different id. Then, for each tuple t in R, the owner sends the publisher the corresponding encrypted tuple t
, together with the ids of the partitions to
which t’s attribute values belong. The publisher is able to evaluate queries by exploiting the received partition ids, without accessing the encrypted tuples. In order to do
that, a user, before submitting a query to a publisher, rewrites it in terms of partition
ids. Let us consider, for instance, the relation Dept(dname, Nemployees, address)
Table 10.1. Security requirements and possible approaches
security properties techniques
data
approaches
authenticity/
merkle hash trees
relational data Devanbu et al. [13]
integrity
XML data
Bertino et al. [5]
aggregate signatures relational data Mykletun et al. [19]
confidentiality
data encryption
relational data Hacigumus et al.
[15–17]
textual data
Song et al. [26]
completeness
merkle hash trees
relational data Devanbu et al. [13]
XML data
Bertino et al. [5]
aggregate signatures relational data Nara et al. [22]
219
10.3.1 Confidentiality
The main efforts carried out to address confidentiality in third-party architectures
have been focused on confidentiality with respect to publishers [15–17, 26] only.
What is interesting to note is that all the proposals enforce confidentiality by means
of cryptographic-based solutions. More precisely, the common underlying idea of
all these approaches is that data owners outsource to publishers an encrypted version of the data they are entitled to manage, without providing the corresponding decryption keys. Thus, the publisher is not able to access and, as a consequence, to misuse outsourced data. Obviously, applying such a solution to a thirdparty scenario implies considering an interesting problem; that is how to make
publishers able to evaluate queries on encrypted data, without accessing them. In
recent years, this problem has been investigated in depth by several researchers, with
two main resulting solutions [17, 26] that work for different data models. In what
follows, we briefly introduce the method proposed in [15–17] to query encrypted
relational databases, and the cryptographic scheme presented in [26] to query encrypted textual data.
Hagicumus et al. The approach proposed by Hacigumus et al. [15–17] exploits binning techniques and privacy homomorphic encryption to query encrypted relational
data. More precisely, binning techniques are used to perform selection queries on
encrypted relation data, whereas homomorphic encryption [25] is used to enable a
third-party to perform aggregate queries over encrypted tuples. Let us start to describe how, by partitioning relation data domains, Hacigumus et al.’s approach enables third parties to evaluate selection queries. The basic idea is that for each relation
R the owner divides the domain of each attribute in R into distinguished partitions, to
which it assigns a different id. Then, for each tuple t in R, the owner sends the publisher the corresponding encrypted tuple t
, together with the ids of the partitions to
which t’s attribute values belong. The publisher is able to evaluate queries by exploiting the received partition ids, without accessing the encrypted tuples. In order to do
that, a user, before submitting a query to a publisher, rewrites it in terms of partition
ids. Let us consider, for instance, the relation Dept(dname, Nemployees, address)
Table 10.1. Security requirements and possible approaches
security properties techniques
data
approaches
authenticity/
merkle hash trees
relational data Devanbu et al. [13]
integrity
XML data
Bertino et al. [5]
aggregate signatures relational data Mykletun et al. [19]
confidentiality
data encryption
relational data Hacigumus et al.
[15–17]
textual data
Song et al. [26]
completeness
merkle hash trees
relational data Devanbu et al. [13]
XML data
Bertino et al. [5]
aggregate signatures relational data Nara et al. [22]