Databases Reference
In-Depth Information
the sequence of
V
NB
i
−
V
NB
j
, he can't get each individual information gain.
Thus private data are not revealed.
Theorem 12.
(E
ciency). The computation of Protocol 4 is e
cient from
both computation and communication point of view.
Proof.
The total communication cost is upper bounded by
αm
2
. The total
computation cost is upper bounded by
m
2
+
m
+ 1. Therefore, the protocols
are very fast.
4 Overall Discussion
Our privacy-preserving classification system contains several components. In
Sect. 3.4, we show how to correctly compute
e
(
Pr
(
a
i
|
v
j
))). In Sect. 3.4, we
discuss how to compute
e
(
Pr
(
v
j
)). In Sect. 3.4, we present protocols to com-
pute
e
(
Pr
(
v
j
)
i
=1
Pr
(
a
i
,v
j
)
V
. In Sect. 3.4, we show how to
compute the final naive Bayesian classifier. We discussed the correctness of
the computation in each section. Overall correctness is also guaranteed.
As for the privacy protection, all the communications between the par-
ties are encrypted, therefore, the parties who has no decryption key cannot
gain anything out of the communication. On the other hand, there are some
communication between the key generator and other parties. Although the
communications are still encrypted, the key generator may gain some useful
information. However, we guarantee that the key generator cannot gain the
private data by adding random numbers in the original encrypted data so that
even if the key generator get the intermediate results, there is little possibility
that he can know the intermediate results. Therefore, the private data are
securely protected with overwhelming probability.
In conclusion, we provide a novel solution for naive Bayesian classification
over horizontally partitioned private data. Instead of using data transforma-
tion, we define a protocol using homomorphic encryption to exchange the data
while keeping it private. Our classification system is quite e
cient that can
be envisioned by the communication and computation complexity. The total
communication complexity is upper bounded by
α
(
m
2
+2
n
+3
t
+ 2). The
computation complexity is upper bounded by 2
N
+
m
2
+(5+
n
)
t
+
n
+
m
+1.
) for each
v
j
∈
Pr
(
v
j
)
References
1. G. Aggarwal, N. Mishra, and B. Pinkas. Secure computation of the k th-ranked
element. In
EUROCRYPT pp 40-55
, 2004.
2. R. Agrawal and R. Srikant. Privacy-preserving data mining. In
Proceedings of
the ACM SIGMOD Conference on Management of Data, pp 439-450
.ACM,
May 2000.
