Cryptography Reference
In-Depth Information
Proof
(Sketch) Let (
g,g
a
,g
b
) be the Strong-DH instance and let
A
g,g
a
be the DStatic-DH
oracle. Let
B
be an IND-CCA adversary against the KEM. We want to use
B
to solve our
strong-DH instance. To do this we will simulate the game that
B
is designed to play. The
simulation starts
B
by giving it the public key (
g,g
a
). Note that the simulator does not
know the corresponding private key.
Since the key derivation function is now a random oracle, it is necessary for
B
to
query the simulator whenever it wants to compute
kdf
; this fact is crucial for the proof.
Indeed, the whole idea of the proof is that when
B
requests the challenge ciphertext we
reply with
c
∗
=
g
b
and with a randomly chosen
K
∗
∈
K
κ
. Since
kdf
is a random oracle, the
adversary can have no information about whether or not
c
∗
encapsulates
K
∗
unless the query
kdf
((
c
∗
)
a
) is made. Finally, note that (
c
∗
)
a
g
ab
is precisely the value the simulator wants
=
to find.
More precisely, let
E
be the event (on the probability space of strong-DH instances
and random choices made by
B
) that
B
queries
kdf
on (
c
∗
)
a
g
ab
. The advantage of
B
is
=
2
where Pr(
B
) is the probability that
B
wins the IND-CCA security
game. Note that Pr(
B
)
Pr(
B
)
1
Adv(
B
)
=
−
=
Pr(
B
|
E
)Pr(
E
)
+
Pr(
B
|¬
E
)Pr(
¬
E
). When
kdf
is a random oracle
|¬
=
|
=
+
−
≤
≤
we have Pr(
B
E
)
1
/
2. Writing Pr(
B
E
)
1
/
2
u
for some
1
/
2
u
1
/
2wehave
=
+
=|
|
Pr(
B
)
Pr(
E
). Since Adv(
B
) is assumed to be non-
negligible it follows that Pr(
E
) is non-negligible. In other words, a successful adversary
makes an oracle query on the value
g
ab
with non-negligible probability.
To complete the proof it is necessary to explain how to simulate
kdf
and Decrypt queries
and to analyse the probabilities. The simulator maintains a list of all queries to
kdf
.The
list is initially empty. Every time that
kdf
(
u
) is queried, the simulator first checks whether
u
1
/
2
u
Pr(
E
) and so Adv(
B
)
u
if not. Then the simulator checks whether an entry (
u,K
) appears in
the list of queries and, if so, returns
K
. If no entry appears in the list then use the oracle
A
g,g
a
to determine whether
u
∈
G
and returns
⊥
1). If this is the case then
g
ab
has been computed and the simulation outputs that value and halts. In all other cases, a
value
K
is chosen uniformly and independently at random from
g
ab
(i.e., if
A
g,g
a
(
g
b
,u
)
=
=
K
κ
,(
u,K
) is added to the
list of
kdf
queries, and
K
is returned to
B
.
Similarly, when a decryption query on ciphertext
c
is made then one checks, for each
pair (
u,K
) in the list of
kdf
values, whether
A
g,g
a
(
c
,u
)
=
1. If this is the case then return
K
. If there is no such triple then return a random
K
∈
K
.
One can check that the simulation is sound (in the sense that Decrypt does perform
the reverse of Encrypt) and that the outputs of
kdf
are indistinguishable from random.
Determining the advantage of the simulator in solving the strong-DH problem is then
straightforward. We refer to Section 10.4 of Cramer and Shoup [
149
] for a careful proof
using the “game hopping” methodology (actually, that proof applies to the variant in
Exercise
23.1.5
, but it is easily adapted to the general case).
Exercise 23.1.5
A variant of the scheme has the key derivation function applied to the pair
(
g
k
,h
k
) in Encrypt instead of just
h
k
(respectively, (
c
1
,
c
1
) in Decrypt). Adapt the security
proof to this case. What impact does this have on the running time of the simulator?
