Databases Reference
In-Depth Information
classification system is to disclose no private data in every step. We firstly
select a key generator who produces the encryption and decryption key pairs.
The computation of the whole system is under encryption. For the purpose
of illustration, let's assume that
P
n
is the key generator who generates a
homomorphic encryption key pair (e, d). To build a NB classifier, we need
conduct the following major steps: (1) To compute
e
(
i
=1
Pr
(
a
i
|
v
j
)); (2) To
compute
e
(
Pr
(
v
j
)); (3) To compute
argmax
v
j
∈V
Pr
(
v
j
)
i
=1
Pr
(
a
i
|
v
j
). Next,
we will show how to conduct each step.
3.4 Privacy-Preserving Naive Bayesian Classification
To Compute
e
(
τ
i
=1
Pr
(
a
i
|v
j
))
Protocol 1.
1. P
n
computes e
(
a
i
∈P
n
Pr
(
a
i
|
v
j
))
denoted by e
(
G
n
)
and sends it to P
1
.
2. P
1
computes e
(
G
n
)
G
1
=
e
(
G
1
G
n
)
where G
1
=
a
i
∈P
1
Pr
(
a
i
|
v
j
)
, then
sends e
(
G
1
G
n
)
to P
2
.
3. P
2
computes e
(
G
1
G
n
)
G
2
=
e
(
G
1
G
2
G
n
)
where G
2
=
a
i
∈P
2
Pr
(
a
i
|
v
j
)
,
then sends e
(
G
1
G
2
G
n
)
to P
3
.
4. Continue until P
n−
1
obtains e
(
G
1
G
2
···G
n
)
= e
(
i
=1
Pr
(
a
i
|v
j
))
.
Theorem 1.
(Correctness). Protocol 1 correctly computes e
(
i
=1
Pr
(
a
i
|
v
j
))
.
Proof.
When
P
1
receives
e
(
G
n
), he computes
e
(
G
n
)
G
1
which is equal to
e
(
G
1
G
n
) according to (2). He sends it to
P
2
who computes
e
(
G
1
G
n
)
G
2
which
is equal to
e
(
G
1
G
2
G
n
) according to (2). Continuing to send the result to the
next party. Finally,
P
n−
1
obtains
e
(
G
1
G
2
···
G
n
)=
e
(
i
=1
Pr
(
a
i
|
v
j
)). There-
fore, Protocol 1 correctly computes
e
(
i
=1
Pr
(
a
i
|
v
j
)).
Theorem 2.
(Privacy-Preserving). Assuming the parties follow the protocol,
the private data are securely protected.
Proof.
In Protocol 1, all the data transmission are hidden under encryption.
The parties who are not the key generator can't see other parties' private
data. On the other hand, the key generator doesn't obtain the encryption of
other parties' private data. Therefore, Protocol 1 discloses no private data.
Theorem 3.
(E
ciency). Protocol 1 is e
cient in terms of computation and
communication complexity.
Proof.
To prove the e
ciency, we need conduct complexity analysis of the
protocol. The bit-wise communication cost of this protocol is
α
(
n
1). The
computation cost is upper bounded by
N
+
nt
. Therefore, the protocol is
su
cient fast.
−
