Databases Reference
In-Depth Information
4.3 Privacy Against Malicious Parties
In the last section, we provide the secure protocol for semi-honest parties.
In practice, providing a protocol against malicious parties is demanding. We
cannot hope to stop all the attacks
I
1
,
I
2
,and
I
3
.
I
4
can be easily detected by
counting the number of terms received and comparing with the legal number
of terms. In this section, we will mainly deal with the second category. We also
think the attack in this category (i.e.,
II
1
) is critical from privacy protection
point of view. To deal with
II
1
, the collaborative parties need to predefine
the malicious pattern for their input vectors,
2
they then detect during the
protocol whether each other's input is legal by the following protocol:
Protocol 2.
(Oblivious K Computation)
1. P
2
performs the following:
a) P
2
generates a vector x
2
with m elements. (Note that x
2
cannot be a
malicious vector predefined by the collaborative parties.)
b) After P
2
receives the encrypted terms from P
1
, i.e., e
(
x
1
i
)
for all i
∈
[1
,m
]
,heusesx
2
to conduct Step 2 (protocol 1) except that he doesn't
send e
(
x
1
· x
2
)
to P
1
; he then uses x
2
to conduct Step 2 (Protocol 1)
except that he doesn't send e
(
x
1
· x
2
)
to P
1
.
c) P
2
flips a fair coin to decide the order in which e
(
x
1
·x
2
)
and e
(
x
1
·x
2
)
are to be sent to P
1
, e.g. if it is heads, he firstly sends e
(
x
1
· x
2
)
,and
then e
(
x
1
·x
2
)
to P
1
; if it is tails, he firstly sends e
(
x
1
·x
2
)
, and then
e
(
x
1
· x
2
)
.
2. P
1
performs the following:
a) P
1
decrypts the e
(
x
1
·x
2
)
and e
(
x
1
·x
2
)
and obtains x
1
·x
2
and x
1
·x
2
.
She checks whether P
2
uses a malicious input vector (a vector from a
closed list of predefined, special vector values). If she detects that P
2
uses a malicious input vector, she doesn't send x
1
· x
2
and x
1
· x
2
to
P
2
and halts the protocol. Otherwise, she sends P
2
x
1
· x
2
and x
1
· x
2
in the same order P
2
used.
3. P
2
checks whether P
1
uses a malicious input vector. If yes, he halts the
protocol without telling P
1
which of the two vectors is x
1
· x
2
, and which
one is x
1
·x
2
. Otherwise, he sends x
1
·x
2
to P
1
(he can distinguish between
x
1
· x
2
and x
1
· x
2
based on the order he received from P
1
.)
We now discuss that this protocol preserves the privacy in the presence of
the attack of type
II
1
.Since
P
1
is the first to obtain the results, i.e.
x
1
·x
2
and
x
1
· x
2
, she checks whether
P
2
is using a malicious input vector. If she finds
that he does, she keeps the final results and halts the protocol. Therefore,
P
1
's
privacy is preserved since
P
2
does not obtain the decrypted results. On the
other hand, since
P
2
has the other pseudo vector
x
2
,
P
1
can't distinguish which
of the two vectors gives correct result; she has to send the two results e.g.,
2
These patterns should be detectable through the targeted computation results.
