Cryptography Reference
In-Depth Information
The values
w,w
1
,w
2
,k,k
,α
are all uniquely determined but, by Lemma
23.2.1
,
x
2
and
y
2
can take any values between 0 and
r
1. Hence,
u
x
1
+
αy
1
1
u
x
2
+
αy
2
2
−
equals any fixed value
v
for exactly
r
of the
r
2
choices for (
x
2
,y
2
).
Theorem 23.2.9
The basic Cramer-Shoup encryption scheme is IND-CCA secure if DDH
is hard and if the function H is target collision resistant.
Proof
(Sketch) Let
A
be an adversary against the Cramer-Shoup scheme. Given a DDH
instance (
g
1
,g
2
,u
1
,u
2
) the simulator performs the KeyGen algorithm using the given values
g
1
,g
2
. Hence, the simulator knows the private key (
x
1
,x
2
,y
1
,y
2
,z
1
,z
2
). The simulator runs
A
with this public key.
The algorithm
A
makes decryption queries and these can be answered correctly by the
simulator since it knows the private key. Eventually,
A
outputs two messages (
m
0
,
m
1
)
and asks for a challenge ciphertext. The simulator chooses a random
b
∈{
0
,
1
}
, computes
1
u
x
2
+
y
2
2
. Here, and throughout this proof,
u
1
and
u
2
denote the values in the DDH instance that was given to the simulator. The
simulator returns
u
z
1
u
z
2
m
b
,
α
u
x
1
+
y
1
α
e
=
=
H
(
u
1
,u
2
,e
) and
v
=
c
∗
=
(
u
1
,u
2
,e,v
)
.
to
A
. The adversary
A
continues to make decryption queries, which are answered as above.
Eventually,
A
outputs a bit
b
. The simulator returns “valid” as the answer to the DDH
instance if
b
b
and “invalid” otherwise.
The central idea is that if the input is a valid DDH tuple then
c
∗
is a valid encryption of
m
b
and so
A
ought to be able to guess
b
correctly with non-negligible probability. On the
other hand, if the input is not a valid DDH tuple then, by Lemma
23.2.1
,
u
z
1
u
z
2
could be
any element in
G
(with equal probability) and so
c
∗
could be an encryption of any message
m
=
G
. Hence, given
c
∗
, both messages
m
0
and
m
1
are equally likely and so the adversary
can do no better than output a random bit. (Of course,
A
may actually output a fixed bit in
this case, such as 0, but this is not a problem since
b
was randomly chosen.)
There are several subtleties remaining in the proof. First, by Lemma
23.2.8
, before the
challenge ciphertext has been received there is a negligible probability that a ciphertext that
was not produced by the Encrypt algorithm satisfies equation (
23.1
). Hence, the simulation
is correct with overwhelming probability. However, the challenge ciphertext is potentially
an example of a ciphertext that satisfies equation (
23.1
) and yet is not a valid output of the
algorithm Encrypt. It is necessary to analyse the probability that
A
can somehow produce
another ciphertext that satisfies equation (
23.1
) without just running the Encrypt algorithm.
The target collision resistance of the hash function enters at this point (since a ciphertext
of the form (
u
1
,u
2
,e
,v
) such that
H
(
u
1
,u
2
,e
)
∈
H
(
u
1
,u
2
,e
) would pass the test). Due
to lack of space we refer to Section 4 of [
147
] (for a direct proof) or Section 6.2 of [
149
]
(for a proof using “game hopping”).
=
A number of variants of the basic scheme are given by Cramer and Shoup [
149
] and
other authors. In particular, one can design a KEM based on the Cramer-Shoup scheme (see
