Cryptography Reference
In-Depth Information
•
Dec
:
1. On input the private key
(
x
1
,
x
2
,
y
1
,
y
2
,
z
)
and the ciphertext
(
u
1
,
u
2
,
e
,
v
)
, com-
pute:
α
:=
H
(
u
1
||
u
2
||
e
).
2. Test whether
u
x
1
+
α
y
1
1
u
x
2
+
α
y
2
2
=
v
.
3. If the preceding condition does not hold then reject the ciphertext as invalid,
otherwise output the plaintext
eu
−
z
1
.
Let us now show that the scheme is correct in the sense that encryption followed by
decryption recovers the original message. Suppose that
(
u
1
,
u
2
,
e
,
v
)
is the ciphertext
g
1
,
u
2
=
g
2
,
e
h
r
m
and
v
c
r
d
r
α
.
corresponding to the message
m
, with
u
1
=
=
=
Then the ciphertext will pass the correctness test above because:
g
y
1
1
g
y
2
2
g
r
(
x
1
+
y
1
α)
1
g
r
(
x
2
+
y
2
α)
2
u
x
1
+
α
y
1
1
u
x
2
+
α
y
2
2
c
r
d
r
α
=
(
g
x
1
1
g
x
2
2
r
r
α
=
v
=
)
(
)
=
.
Once the test is passed, the message that the decryption algorithm outputs is:
eu
−
z
1
mh
r
u
−
z
1
mg
rz
1
g
−
rz
1
=
=
=
m
,
so that the correct message is recovered.
The main result about the security of the Cramer-Shoup encryption scheme is
then the following (see [57, Theorem 1] and [59, Theorem 1]):
Theorem 8.5
If the DDH problem is hard in the group G and H is a collision
resistant hash function then the Cramer-Shoup scheme is IND-CCA secure.
Proof
The proof is a reduction that shows that if there is a successful adversary
against the scheme, then a successful attacker against the DDH problem in
G
can
be constructed. We present its essential aspects following [57] and refer to [59] for
additional variants of the scheme and for a more detailed proof.
Suppose that
A
is a PPT adversary that succeeds in the indistinguishability exper-
iment
PubK
ind-cca
A
,
E
(
k
)
with non-negligible advantage, where
E
is now the Cramer-
Shoup scheme and
k
(we will assume throughout that the function
H
used by the scheme is collision resistant). We construct an algorithm
=
len
(
q
)
B
that, using
g
x
g
y
g
a
A
as a subroutine, tries to solve the DDH problem. On input a triple
(
,
,
)
,
where
x
and
y
are random elements of
Z
q
, and
a
is either random or
a
=
xy
,
B
will try to distinguish which of these two alternatives holds. For this
B
will generate
a Cramer-Shoup public key that will be given to
A
and
B
will simulate a Cramer-
Shoup decryption oracle responding to
A
's queries.
B
chooses random elements
g
x
, computes:
x
1
,
x
2
,
y
1
,
y
2
,
z
1
,
z
2
← Z
q
and, after setting
g
1
:=
g
,
g
2
:=
g
x
1
1
g
x
2
2
g
y
1
1
g
y
2
2
g
z
1
g
z
2
c
=
,
d
=
,
h
=
.
