Databases Reference
In-Depth Information
J. Zhan et al.
Theorem 7.
(Correctness). Protocol 3 correctly computes e
(
Pr
(
v
j
)
i
=1
Pr
(
a
i
|
v
j
))
.
Proof.
In step 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
. They are equal to
e
(
Pr
(
v
j
)
i
=1
Pr
(
Pr
(
a
i
,v
j
))),
e
(
r
1
i
=1
Pr
(
Pr
(
a
i
,v
j
)))
,...,e
(
r
t
i
=1
Pr
(
Pr
(
a
i
,v
j
))) respec-
tively according to (2). In step 5,
P
n−
1
gets
e
(
Pr
(
v
j
)
i
=1
Pr
(
Pr
(
a
i
,v
j
)))
since he knows the permutations.
Theorem 8.
(Privacy-Preserving). Assuming the parties follow the protocol,
the private data are securely protected.
Proof.
In Protocol 3, all the data transmission, among the parties who have no
decryption key, are hidden under encryption. Therefore, these parties cannot
know the private data. In step 2,
P
n
obtains the sequence of
Pr
(
v
j
)
,r
1
,...,r
t
.
Since it is in a random order,
P
n
cannot identify
Pr
(
v
j
).
Theorem 9.
(E
ciency). Protocol 3 is e
cient in terms of computation and
communication complexity.
Proof.
The bit-wise communication cost of this protocol is upper bounded
by
α
(3
t
+ 4). The computation cost is upper bounded by 5
t
. Therefore, the
protocol is su
cient fast.
Through the above protocol,
e
(
Pr
(
v
j
)
i
=1
Pr
(
a
i
|
v
j
)) can be com-
puted for each
v
j
V
. Without loss of generality, let's assume
P
1
gets
e
(
V
NB
1
)
,e
(
V
NB
2
)
,...,e
(
V
NB
k
) The goal is to find the largest one.
∈
To Compute
V
NB
Protocol 4.
e
(
V
NB
j
)
−
1
1. P
1
computes e
(
V
NB
i
)
∈
[1
,k
]
,i > j, and sends the sequence denoted by ϕ to P
n
in a random
order.
2. P
n
decrypts each element in the sequence ϕ. He assigns the element
+1
if
the result of decryption is not less than
0
,and
×
=
e
(
V
NB
i
−
V
NB
j
)
for all i,j
−
1
, otherwise. Finally, he
1
sequence denoted by ϕ
.
obtains a
+1
/
−
1
sequence ϕ
to P
1
who computes the largest element.
3. P
n
sends
+1
/
−
Theorem 10.
(Correctness). Protocol 4 correctly computes V
NB
.
Proof. P
1
is able to remove permutation effects from
ϕ
(the resultant se-
quence is denoted by
ϕ
) since she has the permutation function that she
used to permute
ϕ
, so that the elements in
ϕ
and
ϕ
have the same order. It
means that if the
q
th position in sequence
ϕ
denotes
e
(
V
NB
i
−
V
NB
j
), then the
q
th position in sequence
ϕ
denotes the evaluation results of
V
NB
i
-
V
NB
j
.We
encode it as +1 if
V
NB
i
≥
V
NB
j
,andas
−
1 otherwise.
P
1
has two sequences:
