Databases Reference
In-Depth Information
more rigid case where partitions are non-overlapping. We describe the work
in [30] later in this section. The mapping information is stored on the client to
enable query translation (i.e., from plaintext queries to server-side queries).
More details about query translation can be found in [21, 26].
Storing Encrypted Data
:
For each tuple
t
=
a
1
,a
2
,...,a
n
in
R
, the relation
R
S
stores a tuple:
encrypt
(
{
a
1
,a
2
,...,a
n
}
)
,Map
R.A
1
(
a
1
)
,Map
R.A
2
(
a
2
)
,...,Map
R.A
n
(
a
n
)
where
encrypt
is the function used to encrypt a tuple of the relation. For
instance, the following is the encrypted relation
emp
S
stored on the server:
eid
S
ename
S
salary
S
addr
S
did
S
etuple
1100110011110010. . .
2
19
81
18
2
1000000000011101. . .
4
31
59
41
4
1111101000010001. . .
7
7
7
22
2
1010101010111110. . .
4
71
49
22
4
The first column
etuple
contains the string corresponding to the encrypted
tuples in
emp
. For instance, the first tuple is encrypted to “1100110011110. . . ”
that is equal to
encrypt
(23
,Tom,
70
K, Maple,
40). The second is encrypted
to “1000000000011101. . . ” equal to
encrypt
(860
,Mary,
60
K, Main,
80). The
encryption function is treated as a black box and any block cipher technique
such as AES, Blowfish, DES etc., can be used to encrypt the tuples. We
discuss some of the issues related to choice of encryption function in the next
section. The second column corresponds to the index on the employee ids. For
example, value for attribute
eid
in the first tuple is 23, and its corresponding
partition is [0
,
200]. Since this partition is identified to 2, we store the value
“2” as the identifier of the
eid
for this tuple.
Decryption Functions
:
Given the operator
E
that maps a relation to its en-
crypted representation, its inverse operator
D
maps the encrypted represen-
tation to its corresponding decrypted representation. That is,
D
(
R
S
)=
R
.In
the example above,
D
(
emp
S
)=
emp
.The
D
operator may also be applied
on query expressions. A query expression consists of multiple tables related
by arbitrary relational operators (e.g., joins, selections, etc). Decryption will
regenerate the whole record.
Mapping Conditions
To translate specific query conditions in operations (such as selections and
joins) to corresponding conditions over the server-side representation, a trans-
lation function called
Map
cond
is used. These conditions help translate rela-
tional operators for server-side implementation, and how query trees are trans-
lated. For each relation, the server-side stores the encrypted tuples, along with
the attribute indices determined by their mapping functions. The client stores
the meta data about the specific indices, such as the information about the
