Databases Reference
In-Depth Information
To Compute
e
(
Pr
(
v
j
))
Protocol 2.
1. Each party computes the share Pr
(
v
j
)
for their own class label set. Let
assume that P
1
has the share s
1
, P
2
has the share s
2
,...,P
n
has the share
s
n
. Our goal is to compute
i
=1
s
i
.
2. P
n
computes e
(
s
n
)
and sends it to P
1
.
3. P
1
computes e
(
s
n
)
e
(
s
1
)=
e
(
s
1
+
s
n
)
, then sends it to P
2
.
4. P
2
computes e
(
s
1
+
s
n
)
×
×
e
(
s
2
)=
e
(
s
1
+
s
2
+
s
n
)
.
5. Repeat until P
n−
1
obtains e
(
i
=1
s
i
)=
e
(
Pr
(
v
j
))
.
Theorem 4.
(Correctness). Protocol 2 correctly computes e
(
Pr
(
v
j
))
.
Proof.
When
P
1
receives
e
(
s
n
), he computes
e
(
s
n
)
e
(
s
1
) which is equal to
e
(
s
1
+
s
n
) according to (2). He sends it to
P
2
who computes
e
(
s
1
+
s
n
)
×
e
(
s
2
)
which is equal to
e
(
s
1
+
s
2
+
s
n
) according to (2). Continuing to send the
result to the next party. Finally,
P
n−
1
obtains
e
(
s
1
+
s
2
···
×
s
n
)=
e
(
Pr
(
v
j
)).
Therefore, Protocol 2 correctly computes
e
(
Pr
(
v
j
)).
Theorem 5.
(Privacy-Preserving). Assuming the parties follow the protocol,
the private data are securely protected.
Proof.
In Protocol 2, 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 2 discloses no private data.
Theorem 6.
(E
ciency). Protocol 2 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
+
n
. Therefore, the protocol is
su
cient fast.
−
v
j
)
i
=1
Pr
To Compute
e
(
Pr
(
(
a
i
|v
j
))
Protocol 3.
1. P
n−
1
generates a set of random numbers: r
1
,r
2
,...,r
t
.Hethensends
e
(
Pr
(
v
j
))
, e
(
r
1
)
,...,r
t
to P
n
in a random order.
2. P
n
decrypts each element in the sequence, then sends them to P
1
in the
same order as P
n−
1
did.
3. P
n−
1
sends e
(
i
=1
Pr
(
Pr
(
a
i
,v
j
)))
to P
1
.
4. P
1
computes e
(
i
=1
Pr
(
Pr
(
a
i
,v
j
)))
Pr
(
v
j
)
, e
(
i
=1
Pr
(
Pr
(
a
i
,v
j
)))
r
1
,...,
e
(
i
=1
Pr
(
Pr
(
a
i
,v
j
)))
r
t
. P
1
then sends them to P
n−
1
.
5. P
n−
1
obtains e
(
Pr
(
v
j
)
i
=1
Pr
(
a
i
|
v
j
))
.
