Databases Reference
In-Depth Information
instance
x
2
, she changes her vector
x
1
to
x
1
by setting the
j
th element
x
1
j
=0
for all
j
=
i
, and the
i
th element
x
1
i
be any value
except 0. As
we will discuss, after protocol 1,
P
1
obtains
∈
[1
,m
],
j
×
x
2
i
. She can easily know
x
2
i
. If she wants to know
i
=1
x
2
i
,she
by computing the following: (
×
x
2
i
)
÷
[1
,m
]. Since
x
1
· x
2
=
i
=1
x
2
i
, after Protocol 1,
may set
x
1
j
= 1 for all
j
∈
she obtains
i
=1
x
2
i
.
In the following, we firstly discuss secure protocol against semi-honest
parties, and then provide a secure protocol against malicious parties.
4.1 Introducing Homomorphic Encryption
The concept of homomorphic encryption was originally proposed in [23]. Since
then, many such systems have been proposed [4, 18, 19, 21]. We observe that
some homomorphic encryption schemes, such as [8], are not robust against
chosen plaintext attacks. However, we base our secure protocols on [21], which
is semantically secure [11].
In our secure protocols, we use additive homomorphism offered by [21]. 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
))
(8)
d
(
e
(
a
1
)
a
2
)=
d
(
e
(
a
1
a
2
))
(9)
4.2 Secure Protocol Against Semi-Honest Parties
Let's assume that
P
1
has an instance vector
x
1
and
P
2
has an instance vector
x
2
. Both vectors have
m
elements. We use
x
1
i
to denote the
ith
element in vec-
tor
x
1
,and
x
2
i
to denote the
i
th element in vector
x
2
. In order to compute the
K
(
x
1
,x
2
), the key issue is how
P
1
and
P
2
compute the inner product between
x
1
and
x
2
without disclosing them to each other. In our secure protocol,
P
1
adds a random number to each of her actual data values, encrypts the masked
values, and sends the encrypted masked terms to
P
2
. By adding the random
numbers,
P
2
is prevented from guessing
P
1
's actual values based on encryp-
tion patterns. Firstly, one of parties is randomly chosen as a key generator.
For simplicity, let's assume
P
1
is selected as the key generator.
P
1
generates a
cryptographic key pair (
d
,
e
) of a semantically-secure homomorphic encryp-
tion scheme and publishes its public key
e
.
P
1
applies the encryption key to
each element of
x
1
(e.g.,
e
(
x
1
i
+
r
i
)).
P
2
computes
e
(
x
1
· x
2
). He then sends
e
(
x
1
· x
2
)to
P
1
who decrypts it and gets (
x
1
· x
2
).
