Cryptography Reference
In-Depth Information
game continues with the adversary able to query the decryption oracle with any ciphertext
c
c
∗
. Finally, the adversary outputs a guess for whether
K
∗
is the key corresponding
to
c
∗
, or a random key (this is the same as the “real or random” security notion for key
exchange in Section
20.5
). Denote by Pr(
A
) the success probability of
A
in this game and
define the
advantage
Adv(
A
)
=
. The KEM is IND-CCA secure if every
polynomial-time adversary has negligible advantage.
=|
Pr(
A
)
−
1
/
2
|
Theorem 5 of Section 7.3 of [
149
] shows that, if a KEM satisfies IND-CCA security and
if a DEM satisfies an analogous security property, then the corresponding hybrid encryption
scheme has IND-CCA security. Due to lack of space we do not present the details.
23.1.2 Proof of security in the random oracle model
We now sketch a proof that the Elgamal KEM of Box
23.2
has IND-CCA security. The
proof is in the random oracle model. The result requires a strong assumption (namely, the
strong-Diffie-Hellman or gap-Diffie-Hellman assumption). Do not be misled by the use
of the word “strong”! This computational problem is not harder than the Diffie-Hellman
problem. Instead, the assumption that this problem is hard is a
stronger
(i.e., less likely to
be true) assumption than the assumption that the Diffie-Hellman problem is hard.
Definition 23.1.3
Let
G
be a group of prime order
r
.The
strong Diffie-Hellman problem
(
strong-DH
)is:given
g,g
a
,g
b
a,b<r
), together with a decision static
Diffie-Hellman oracle (
DStatic-DH oracle
)
A
g,g
a
(
h
1
,h
2
) (i.e.,
A
g,g
a
(
h
1
,h
2
)
∈
G
(where 1
≤
=
1 if and
h
1
), to compute
g
ab
.
only if
h
2
=
An instance generator for strong-DH takes as input a security parameter
κ
, outputs a
group
G
and an element
g
of prime order
r
(with
r>
2
2
κ
) and elements
g
a
,g
b
∈
G
where
1
a,b<r
are chosen uniformly at random. As usual, we say that strong-DH is hard
for the instance generator if all polynomial-time algorithms to solve the problem have
negligible success probability. The
strong Diffie-Hellman assumption
is that there is an
instance generator for which the Strong-DH problem is hard.
It may seem artificial to include access to a decision oracle as part of the assumption.
Indeed, it is a significant drawback of the encryption scheme that such an assumption is
needed for the security. Nevertheless, the problem is well-defined and seems to be hard in
groups for which the DLP is hard. A related problem is the
gap Diffie-Hellman problem
:
again the goal is to compute
g
ab
given (
g,g
a
,g
b
), but this time one is given a full DDH
oracle. In some situations (for example, when using supersingular elliptic or hyperelliptic
curves) one can use pairings to provide a DDH oracle and the artificial nature of the
assumption disappears. The proof of Theorem
23.1.4
does not require a full DDH oracle
and so it is traditional to only make the strong-DH assumption.
≤
Theorem 23.1.4
The Elgamal KEM of Box
23.2
, with the key derivation function replaced
by a random oracle, is IND-CCA secure if the strong Diffie-Hellman problem is hard.
