220
Barbara Carminati and Elena Ferrari
and, for simplicity, consider only the Nemployees attribute representing the number
of employees belonging to the department. Suppose that the domain of Nemployees
is in the interval [1, 300], and that an equi-partition with 10 as range is applied on
that domain. Moreover, suppose that a user wants to perform the following query:
“SELECT * FROM Dept WHERE Nemployees =35.” This query needs to be translated by the user into “SELECT * FROM Dept WHERE Nemployees =id 35 ,” where
id 35 is the id of the partition containing the value 35.
2 Thus, the publisher is able
to evaluate this query by simply looking for those tuples having the partition id associated with attribute Nemployees equal to id 35 . However, we have to note that
the publisher returns to the user an approximate result, in that it returns all the tuples of the Dept relation whose Nemployees attribute belongs to the range [30, 39].
Thus, further query processing has to be performed by the user to refine the received
answer.
Moreover, in [17] the proposed encryption scheme is extended by enhancing it
with privacy homomorphisms (PH) to enable the third-party to evaluate aggregate
functions. This class of encryption functions, introduced by Rivest et al. in [25], provides the capability to calculate arithmetic operations directly on encrypted data.
Indeed, the PH functions have the property that if E(X) op E(Y) = E(Z), then
D(Z) = X op Y, where E() and D() are the encryption and decryption function,
respectively. In [17] this property is exploited to evaluate aggregate queries on encrypted tuples. More precisely, given a relation R, the proposed strategy requires to
encrypt with a PH function each attribute of R, where it is expected to do some
aggregations, called aggregation attributes. Then, the owner outsources together
with the encrypted tuples, and the corresponding partition ids, also the encrypted
aggregation attributes. In [17] it is shown that, by having the PH of the aggregation attributes, the third-party is able to evaluate aggregate functions over them. To
better clarify how PH functions are exploited, let us consider the following query:
“SELECT SUM(Nemployees) FROM Dept” which returns the total number of employees. Let us assume that the data owner has encrypted Nemployees with the PH
function and that the publisher has been provided with PH(t.Nemployees), for each
tuple t outsourced by the owner. To calculate the SUM(), the publisher has to select
all Nemployees attributes
3 and simply calculate the total sum. By the properties of
PH functions, when a user decrypts this sum he/she will obtain the effective number
of employees.
Song et al. Another relevant study carried out in the context of searching encrypted
data has been done by Song et al. [26]. In particular, in [26] the authors propose an interesting cryptographic scheme that supports searching functionalities on encrypted
textual data without loss of data confidentiality. The basic idea of the scheme is the
following. Given a set of words, the proposed scheme first encrypts each word using
a symmetric encryption algorithm with a single secret key k. Then, it generates the
XOR of each encrypted word with a pseudorandom number. The resulting ciphered
2 Clearly, users should receive the owner information on the techniques used to partition data
and generate ids.
3 If a WHERE condition was applied, publisher could evaluate it by means of partition ids.
Barbara Carminati and Elena Ferrari
and, for simplicity, consider only the Nemployees attribute representing the number
of employees belonging to the department. Suppose that the domain of Nemployees
is in the interval [1, 300], and that an equi-partition with 10 as range is applied on
that domain. Moreover, suppose that a user wants to perform the following query:
“SELECT * FROM Dept WHERE Nemployees =35.” This query needs to be translated by the user into “SELECT * FROM Dept WHERE Nemployees =id 35 ,” where
id 35 is the id of the partition containing the value 35.
2 Thus, the publisher is able
to evaluate this query by simply looking for those tuples having the partition id associated with attribute Nemployees equal to id 35 . However, we have to note that
the publisher returns to the user an approximate result, in that it returns all the tuples of the Dept relation whose Nemployees attribute belongs to the range [30, 39].
Thus, further query processing has to be performed by the user to refine the received
answer.
Moreover, in [17] the proposed encryption scheme is extended by enhancing it
with privacy homomorphisms (PH) to enable the third-party to evaluate aggregate
functions. This class of encryption functions, introduced by Rivest et al. in [25], provides the capability to calculate arithmetic operations directly on encrypted data.
Indeed, the PH functions have the property that if E(X) op E(Y) = E(Z), then
D(Z) = X op Y, where E() and D() are the encryption and decryption function,
respectively. In [17] this property is exploited to evaluate aggregate queries on encrypted tuples. More precisely, given a relation R, the proposed strategy requires to
encrypt with a PH function each attribute of R, where it is expected to do some
aggregations, called aggregation attributes. Then, the owner outsources together
with the encrypted tuples, and the corresponding partition ids, also the encrypted
aggregation attributes. In [17] it is shown that, by having the PH of the aggregation attributes, the third-party is able to evaluate aggregate functions over them. To
better clarify how PH functions are exploited, let us consider the following query:
“SELECT SUM(Nemployees) FROM Dept” which returns the total number of employees. Let us assume that the data owner has encrypted Nemployees with the PH
function and that the publisher has been provided with PH(t.Nemployees), for each
tuple t outsourced by the owner. To calculate the SUM(), the publisher has to select
all Nemployees attributes
3 and simply calculate the total sum. By the properties of
PH functions, when a user decrypts this sum he/she will obtain the effective number
of employees.
Song et al. Another relevant study carried out in the context of searching encrypted
data has been done by Song et al. [26]. In particular, in [26] the authors propose an interesting cryptographic scheme that supports searching functionalities on encrypted
textual data without loss of data confidentiality. The basic idea of the scheme is the
following. Given a set of words, the proposed scheme first encrypts each word using
a symmetric encryption algorithm with a single secret key k. Then, it generates the
XOR of each encrypted word with a pseudorandom number. The resulting ciphered
2 Clearly, users should receive the owner information on the techniques used to partition data
and generate ids.
3 If a WHERE condition was applied, publisher could evaluate it by means of partition ids.