Cryptography Reference
In-Depth Information
The IND-CPA security of the Elgamal KEM can be proved in the standard model (the
proof is analogous to the proof of Theorem
20.4.10
) under the assumption of Defini-
tion
23.1.6
. The IND-CCA security can also be proved in the standard model under an
interactive assumption called the oracle Diffie-Hellman assumption. We refer to Abdalla,
Bellare and Rogaway [
1
] for the details of both these results.
Definition 23.1.6
Let
G
be a group and
kdf
:
G
a key derivation function. The
hash
Diffie-Hellman problem
(
hash-DH
) is to distinguish the distributions (
g,g
a
,g
b
,
kdf
(
g
ab
))
and (
g,g
a
,g
b
,K
) where
K
is chosen uniformly from
→
K
.The
hash Diffie-Hellman
assumption
is that there exist instance generators such that all polynomial time algorithms
for hash-DH have negligible advantage.
K
l
be a key
derivation function such that log
2
(
r
)
/
2
<l<
log
2
(
r
) and such that the output distribution
is statistically close to uniform. Show that DDH
Exercise 23.1.7
Let
G
be a group of prime order
r
and let
kdf
:
G
→{
0
,
1
}
≤
R
hash-DH
≤
R
CDH.
An elegant variant of Elgamal, with IND-CCA security in the random oracle model
depending only on CDH rather than strong Diffie-Hellman, is given by Cash, Kiltz and
Shoup [
112
].
23.2 Cramer-Shoup encryption
In their landmark paper [
147
], Cramer and Shoup gave an encryption scheme with a proof
of CCA security in the standard model. Due to lack of space we will only be able to give a
sketch of the security analysis of the scheme.
To motivate how they achieve their result, consider the proof of security for the Elgamal
KEM (Theorem
23.1.4
). The simulator uses the adversary to solve an instance of the CDH
problem. To do this, one puts part of the CDH instance in the public key (and, hence,
one does not know the private key) and part in the challenge ciphertext. To prove CCA
security we must be able to answer decryption queries without knowing the private key. In
the proof of Theorem
23.1.4
this requires a DDH oracle (to determine correct ciphertexts
from incorrect ones) and also the use of the random oracle model (to be able to “see” some
internal operations of the adversary).
In the random oracle model one generally expects to be able to prove security under an
assumption of similar flavour to CDH (see Theorem
20.4.11
and Theorem
23.1.4
). On the
other hand, in the standard model one only expects
2
to be able to prove security under a
decisional assumption like DDH (see Theorem
20.4.10
). The insight of Cramer and Shoup
is to design a scheme where the security depends on DDH and is such that the entire DDH
instance can be incorporated into the challenge ciphertext. The crucial consequence is that
the simulator can now generate public and private keys for the scheme, run the adversary,
and be able to handle decryption queries.
2
Unless performing “bit by bit” encryption, which is a design approach not considered in this topic.
