Information Technology Reference
In-Depth Information
Additive homomorphism is demonstrated in the following way: Suppose
cEMg
MN
1
=
(
)
=
=
(
)
=
and
cEMg
MN
2
are two ciphertexts for
M
1
,
1
2
1
1
2
2
(
)
=
(
)
(
)
N
2
MM
+
2
mod . On decryption, we
have
D
(
c
1
.
c
2
mod
N
2
) =
M
1
+
M
2
mod
N
. Thus, the sum of the plaintexts can
be obtained from the ciphertext without the cloud knowing the values of
M
1
and
M
2
. We note that
r
N
is used only to make the homomorphic computation
nondeterministic; the same message can be encrypted into different cipher-
texts to prevent dictionary attacks.
Boneh, Goh, and Nissim [5] proposed a scheme capable of performing multi-
ple additions and only one multiplication at the same time. Before explaining
their homomorphic encryption technique, we define
bilinear pairing
.
M
2
∈ . Then,
cc
mod
Ng
rr
N
1
2
N
12
12
3.2.2 Bilinear Pairing
For bilinear pairing, let
G
be a cyclic group of prime order
p
generated by
g
.
Let
G
T
be a group of order
p
. We can define the map
e: G
×
G
→
G
T
. The map
satisfies the following properties:
1.
e
(
u
a
,
u
b
) =
e
(
u
,
v
)
ab
for all
u
,
v
∈
G
and
ab
, ∈ .
p
2. Nondegenerate:
e
(
g
,
g
) ≠ 1.
3.
e
is efficiently computable.
3.2.3 Homomorphic Encryption Using Bilinear Pairings
•
Gen
(κ) → (
pk
,
sk
): Given a security parameter κ,
Gen
(κ) chooses two
distinct
κ
2
-bit primes,
p
1
and
p
2
, and sets
n
=
p
1
p
2
. A positive integer
T
<
p
2
is selected. Two multiplicative groups
G
,
G
T
of order
n
are
selected, and a bilinear pairing
e
: (
G
×
G
) →
G
T
is defined. Random
generators
g
,
u
∈
G
are defined and
hu
=
2
is set, such that
h
is a
generator of the subgroup of order
p
1
. The public key is
pk
= (
n
,
g
,
h
,
G
,
G
T
,
e
), and the private key is
sk
=
p
1
.
•
Enc
(
m
,
pk
) →
c
: Given a message
m
∈ and public key
pk
,
Enc
(
pk
,
m
)
chooses random
r
∈
R
and calculates the ciphertext
mr
cgh
=
mod
n
•
Dec
(
c
,
sk
) →
m
: Given a ciphertext
c
∈ C and a private key
sk
,
Dec
(
sk
,
c
)
calculates
==
()
m
p
p
cc
g
mod
n
and using Pollard's lambda [38] method calculates the discrete logarithm of
c
′ in the base
g
p
.
Search WWH ::
Custom Search