Databases Reference
In-Depth Information
•
n: the total number of parties. Assuming
n>
2.
•
m: the total number of class.
•
τ
: the total number attribute.
•
α
is the number of bits for each transmitted element in the privacy-
preserving protocols.
•
N: the total number of records.
3.2 Cryptography Tools
Our scheme is based on homomorphic encryption which was originally pro-
posed in [17]. Since then, many such systems have been proposed [3, 14-16].
We observe that some homomorphic encryption schemes, such as [4], are not
robust against chosen cleartext attacks. However, we base our secure protocols
on [16], which is semantically secure [9].
In our secure protocols, we use additive homomorphism offered by [16]. In
particular, we utilize the following characterizer of the homomorphic encryp-
tion functions:
e
(
a
1
)
e
(
a
2
)=
e
(
a
1
+
a
2
) where e is an encryption function;
a
1
and
a
2
are the data to be encrypted. Because of the property of associativity,
e
(
a
1
+
a
2
+
×
···
+
a
n
) can be computed as
e
(
a
1
)
×
e
(
a
2
)
×···×
e
(
a
n
)where
e
(
a
i
)
=0.Thatis
d
(
e
(
a
1
+
a
2
+
···
+
a
n
)) =
d
(
e
(
a
1
)
×
e
(
a
2
)
×···×
e
(
a
n
))
(1)
d
(
e
(
a
1
)
a
2
)=
d
(
e
(
a
1
a
2
))
(2)
3.3 Introducing Naive Bayesian Classification
The naive Bayesian classification is one of the most successful algorithms
in many classification domains. Despite of its simplicity, it is shown to be
competitive with other complex approaches, especially in text categoriza-
tion and content based filtering. The naive Bayesian classifier applies to
learning tasks where each instance x is described by a conjunction of at-
tribute values and where the target function f(x) can take on any value
from some finite set V. A set of training examples of the target function
is provided, and a new instance is presented, described by the tuple of at-
tribute values
<a
1
,a
2
,...,a
n
>
. The learner is asked to predict the target
value for this new instance. Under a conditional independence assumption,
i.e.,
Pr
(
a
1
,a
2
,...,a
n
|
v
j
)=
i
=1
Pr
(
a
i
|
v
j
), a naive Bayesian classifier can be
derived as follows:
τ
V
NB
=
argmax
v
j
∈V
Pr
(
v
j
)
Pr
(
a
i
|
v
j
)
(3)
i
=1
In this paper, we will design a privacy-preserving system to show how
to compute a naive Bayesian classifier. The goal of our privacy-preserving
