Databases Reference
In-Depth Information
and (iii) on data not specified/allowed by the client - specifically, no inter-
attribute transitivity should be possible. Additionally it should not be able to
(iv) evaluate other predicates on “unlocked” data. This also means that no
additional information should be leaked in the process of predicate evaluation.
For example, allowing the evaluation of
p
(
x, y
):=(
|
x
−
y
|
<
100), should not
reveal
.
One solution relies on the use of predicate-specific metadata that clients
place on the server together with the main data sets. This metadata does
not reveal anything about the main data fields and stays in a “locked” state
until its corresponding data is involved in a join. The client then provides
“unlocking” information for the metadata and the server is able to perform
exactly
the considered query, without finding out any additional information.
In the following we briefly outline this. For more details see [42].
Let
N
be a public security parameter, and
K
a symmetric (semantically
secure) encryption key. For each column
A
,let
R
1
|
x
−
y
|
=
R
2
be two random uni-
N
. In a client
pre-processing
phase, for each confidential
data attribute
A
with elements
a
i
,
i
=1
..n
, the client computes an obfuscation
of
a
i
,
O
(
a
i
):=
H
(
a
i
)
form values in
{
0
,
1
}
R
1
. For all values
y
⊕
∈
P
(
a
i
):=
{
y
|
p
(
a
i
,y
)=
true
}
,
R
2
. and stores it into a Bloom filter specific to
a
i
,
BF
(
a
i
). It then outsources
the client computes
H
(
y
)
⊕
to the server. To al-
low a join of two columns
A
and
B
on the predicate
p
, the client sends the
server the value
q
AB
=
R
2
⊕
{
E
K
(
a
i
),
O
(
a
i
),
BF
(
a
i
)
}
R
1
. For each element
a
i
in column
A
and
b
j
in
column
B
, the server computes
T
b→a
:=
O
(
b
j
)
R
2
.Itthen
outputs all tuples
<E
K
(
a
i
)
,E
K
(
b
j
)
,... >
for which
BF
(
a
i
) contains
T
b→a
.
The following can be shown:
⊕
q
AB
=
H
(
b
j
)
⊕
Theorem 1.
The server cannot perform join operations on initially stored
data.
Theorem 2.
The server cannot perform transitive joins.
Theorem 3.
Given a binary EFM predicate p, for any matching pair of values
returned as a result of a join, <x
=
E
K
(
a
i
)
,y
=
E
K
(
b
j
)
>, no additional
information about a
i
and b
j
or their relationship can be inferred by the server,
other than the fact that p
(
a
i
,b
j
)=
true.
The solution handles
data updates
naturally. For any new incoming data
item, the client pre-processing can be executed per-item and its results simply
forwarded to the server. Additionally, in the case of a multi-threaded server,
multiple clients (sharing secrets and keys) can access the same data store
simultaneously.
We note also that
multiple predicate evaluations
are also accommodated
naturally. Confidentiality can be provided for the attributes involved in binary
EFM predicates. In the following database schema, the association between
patients and diseases is confidential but any other information is public and
can be used in joins. To return a list of New York City patient names and
their associated antibiotics (but not their disease) the server will access both
