Databases Reference
In-Depth Information
We describe this more formally as
Protocol 1.
INPUT: P
1
's input is a vector x
1
=
{
x
11
,x
12
,...,x
1
m
}
,and
P
2
's input is a vector x
2
=
{
x
21
,x
22
,...,x
2
m
}
. The elements in the input
vectors are taken from the real number domain.
1. P
1
performs the following operations:
a) She computes e
(
x
1
i
+
r
i
)
s
(
i
[1
,m
])
and sends them to P
2
. r
i
, known
only by P
1
, is a random number in real domain.
b) She computes e
(
∈
[1
,m
])
and sends them to P
2
.
2. P
2
performs the following operations:
a) He computes t
1
=
e
(
x
11
+
r
1
)
x
21
=
e
(
x
11
...x
21
+
r
1
x
21
)
, t
2
=
e
(
x
12
+
r
2
)
x
22
=
e
(
x
12
...x
22
+
r
2
x
22
)
,...,t
m
=
e
(
x
1
m
)
x
2
m
=
e
(
x
1
m
...x
2
m
+
r
m
x
2
m
)
.
b) He computes t
1
×
−
r
i
)
s
(
i
∈
t
2
×···×
t
m
=
e
(
x
11
·
x
21
+
x
12
·
x
22
+
···
+
x
1
m
·
+
r
m
x
2
m
)
= e
(
x
1
· x
2
+
i
=1
r
i
x
2
i
)
.
x
2
m
+
r
1
x
21
+
r
2
x
22
+
···
r
i
)
x
2
i
=
e
(
c) He computes e
(
−
−
r
i
x
2
i
)
for i
∈
[1
,m
]
.
d) He computes e
(
x
1
· x
2
+
i
=1
r
i
x
2
i
)
×
e
(
−
r
1
x
21
)
×
e
(
−
r
2
x
22
)
×···×
r
m
x
2
m
)=
e
(
x
1
· x
2
)
.
We need to show that the above protocol is correct, and that it preserves
the privacy of
P
1
and
P
2
as postulated in Sect. 3.1.
Lemma 1.
(Correctness). Protocol 1 correctly computes the inner product
(x
1
· x
2
) against semi-honest parties.
Proof.
When
P
2
receives each encrypted element
e
(
x
1
i
+
r
i
)and
e
(
e
(
−
−
r
i
), he
computes
i
=1
e
(
x
1
i
+
r
i
)
x
2
i
which, according to (9), is equal to
e
(
i
=1
x
1
i
·
x
2
i
+
i
=1
r
i
x
2
i
) for all
i
[1
,m
]. He then computes
e
(
x
1
·x
2
+
i
=1
r
i
x
2
i
)
∈
×
r
m
x
2
m
)=
e
(
x
1
· x
2
) according to (8). After
that, he sends it to
P
1
who computes
d
(
e
(
x
1
· x
2
)) = (
x
1
· x
2
). Therefore,
(
x
1
· x
2
) is correctly computed.
Lemma 2.
(Privacy-Preserving). Assuming the parties follow the protocol,
the private data are securely protected.
Proof.
There are two points we need analyze. (1) Whether
P
1
can obtain
P
2
's
private data. There is no information that
P
2
sends to
P
1
,thus,
P
2
's private
data cannot be disclosed to
P
1
. (2) Whether
P
2
can obtain
P
1
's private data.
What
P
2
receives from
P
1
is encrypted and masked element of
P
1
's data. Since
P
2
has no decryption key and doesn't know the random number used by
P
1
,
it is impossible that
P
2
can obtain
P
1
's private data.
Lemma 3.
(E
ciency). Protocol 1 is e
cient from both computation and
communication point of view.
Proof.
To prove the e
ciency, we need conduct complexity analysis of the
protocol. The bit-wise communication cost of this protocol is (2
m
+1)
α
where
α
is the number of bits for each transmitted element. The following contributes
to the computational cost: (1) 2m encryptions; (2) 2m exponentiations; (2)
2m
e
(
−
r
1
x
21
)
×
e
(
−
r
2
x
22
)
×···×
e
(
−
−
1 multiplications. Therefore, the protocol is su
cient fast.
