Cryptography Reference
In-Depth Information
g
r
h
r
m
(
c
1
,
c
2
)
=
((
,
,
),
)
=
(
,
)
Decryption works as intended: If
Enc
G
g
h
m
and
c
−
x
1
g
x
, then
Dec
g
−
rx
h
r
m
g
−
rx
g
rx
m
=
((
,
,
), (
c
1
,
c
2
))
=
c
2
=
=
=
h
G
g
x
m
.
Remarks 8.13
Elgamal encryption requires just two exponentiations in
G
, which
are obtained by applying the binary exponentiation algorithm to the multiplication
in
G
, and is, therefore, efficient. Moreover, the exponentiations are independent of
the plaintext being encrypted and hence they can be precomputed and their results
stored in advance, so that encryption will require only a group multiplication and
will be very efficient—much more so, for example, than RSA encryption. A minor
inconvenience is that the ciphertext doubles the size of the plaintext, i.e., the scheme
produces
message expansion
by a factor of 2. But this is compensated by the fact
that encryption is probabilistic which, as we have seen, is a necessary condition
for an encryption scheme to meet even minimal security requirements. Decryption
requires essentially one exponentiation in
G
and hence is also efficient although now
we cannot use the CRT to speed it up as we did with RSA decryption.
Exercise 8.26
Show that Elgamal is a homomorphic encryption scheme by proving
that, for a given key, the Elgamal decryption algorithm defines a group homomor-
phism
G
×
G
→
G
.
8.5.1 Security of Elgamal
Let us now analyze the security properties of Elgamal encryption. First, we have:
Proposition 8.7
Elgamal is OW-CPA secure if and only if the CDH problem is hard
relative to
Gen
G
.
Proof
We show that if the CDH problem is hard then Elgamal is OW-CPA secure.
Suppose, on the contrary, that Elgamal is not OW-CPA secure and hence, according to
Definition 8.4, there exists a PPT adversary
PubK
ow-cpa
A
such that Pr
(
A,
Elgamal
(
k
)
=
1
)
is non-negligible. Then we may show that there exists a PPT algorithm
B
that solves
g
x
g
y
the CDH problem with non-negligible probability. On input
(
G
,
g
,
,
)
where
G
is a cyclic group of order
t
,
g
a generator of
G
, and
x
,
y
← Z
t
,
B
tries to compute
g
xy
∈
G
by proceeding as follows:
g
x
•
After being given its input,
B
defines the Elgamal public key
pk
:=
(
G
,
g
,
)
g
y
and the ciphertext
c
:=
(
,
1
)
.
•
B
A
Then
runs
on input the public key
pk
and the challenge ciphertext
c
and
A
∈
eventually
returns a message
m
G
.
outputs
m
−
1
•
Finally
B
∈
G
.
succeeds in the
PubK
ow-cpa
g
y
If
A
A,
Elgamal
(
k
)
experiment, then we see that
(
,
1
)
=
g
x
g
r
g
xr
m
y
and
g
xr
m
g
xy
m
Enc
((
G
,
g
,
),
m
)
=
(
,
)
. Hence
r
=
=
=
1, so that
outputs
g
xy
and hence succeeds in solving the instance of the CDH problem.
Since, by hypothesis,
B
A
succeeds with non-negligible probability, so does
B
, and
