Database Reference
In-Depth Information
have sets
C
x
1
and
C
x
2
, which are a disjoint cover of
C
x
. In order to compute this, they
could each form a vector (
v
1
,
v
2
) of size
n
(where
n
is the total number of rows) of
zeros and ones. For the vector
v
k
, the value at
i
is1ifrow
i
contains all members of
C
x
k
, and 0 otherwise. The two parties could then compute the dot product of these two
vectors. This would yield the total number of rows containing the set
X
. The support
is easily found by dividing by the total number of rows [
52
]. This implies that using
a secure dot product protocol (e.g., [
25
]), we can get a two party privacy-preserving
ARM algorithm for vertically partitioned data.
Secure dot product protocols could be easily obtained using additively homo-
morphic public key encryption. A secure public key cryptosystem is called
additive
homomorphic
[
42
] if it satisfies the following requirements:
Let
E
pk
(
.
) denote the encryption function with public key
pk
and
D
pr
(
.
) denote
the decryption function with private key
pr
. Given the encryption of
m
1
and
m
2
,
E
pk
(
m
1
) and
E
pk
(
m
2
), there exists an efficient algorithm to compute the public
key encryption of
m
1
+
m
2
, denoted by
E
pk
(
m
1
+
m
2
):
=
E
pk
(
m
1
)
+
h
E
pk
(
m
2
).
Given a constant
k
and the encryption of
m
1
,
E
pk
(
m
1
), there exists an efficient
algorithm to compute the public key encryption of
k
·
m
1
, denoted by
E
pk
(
km
1
):
=
×
h
E
pk
(
m
1
).
Using such an additive homomorphic encryption scheme, we can easily compute
the dot product of vectors securely. Basically, site
S
1
, creates a public key
pk
and
private key
pr
pair. Later on, for all elements of
v
1
,
S
1
computes
E
pk
(
v
1
j
) and this
encrypted vector is send to site
S
2
. Site
S
2
keeps an encrypted counter
C
and adds
E
pk
(
v
1
j
) using
k
+
h
operation, if
v
2
j
is 1. Finally, before sending the
C
to site
S
1
,
S
2
generates a random value
r
and computes
C
+
h
E
pk
(
r
) and sends this blinded value
to
S
1
.
S
1
can decrypt this value to learn the dot product result blinded with random
value. Now
S
1
and
S
2
can use the secure comparison protocol to check whether the
support threshold condition is satisfied.
Extending the above protocol to the multi-party case requires securely computing
j
=
1
I
C
x
i
j
⊆
T
for each transaction. Please note that this is equivalent to computing
j
=
1
I
C
x
i
j
⊆
T
, which could be easily achieved by using the secure logical
protocol [
27
].
One issue with the vertically partitioned data case is that all the protocols require
O
(
n
) cryptographic operations, where
n
. This could be especially problematic
for big data scenarios where a database contains billions of rows. Recent work has
tried to address this problem by developing secure approximate dot product protocols
that can provide two orders of magnitude improvement [
28
,
37
]. These protocols
(e.g., [
37
]) basically leverage dimensionality reduction techniques to reduce the
dimension of the vectors that are provided as input to secure dot product protocols.
Still more work needs to be done to provide secure protocols that can scale to billions
of transactions.
=|
U
|
