Cryptography Reference
In-Depth Information
A
Then the following public key is given to
:
(
g
1
,
g
2
,
c
,
d
,
h
,
H
),
where
H
is the collision resistant hash function being used by the scheme. Now
B
runs
the first stage of
A
in the CCA indistinguishability experiment. In this stage
A
queries
for decryptions and
B
acts as a simulator of the decryption oracle: upon receiving
and verifies that
v
x
1
+
β
y
1
1
v
x
2
+
β
y
2
2
(
v
1
,
v
2
,
f
,
w
)
it computes
β
:=
H
(
v
1
||
v
2
||
f
)
=
w
.
If this check fails
B
outputs
⊥
(meaning “invalid ciphertext”), otherwise
B
outputs
the message
fv
−
z
1
1
v
−
z
2
.
Observe that the value of
h
generated by
B
above for the public key is computed in
a different way than in the Cramer-Shoup key generation algorithm, but the adversary
A
g
z
1
g
z
2
g
1
,wehavethat
h
g
z
,
will not be able to detect this change. Since
g
2
=
=
=
where
z
=
z
1
+
xz
2
, and we can show that in the simulation above
B
acts the same as
a legitimate decryption oracle that uses this value of
z
(even if
B
does not know
z
as it
does not know
x
). Indeed, suppose first that the ciphertext
(
v
1
,
v
2
,
f
,
w
)
about which
A
is the correct encryption of a message. In this case the ciphertext satisfies
the verification condition in the Cramer-Shoup decryption algorithm and, moreover,
v
1
queries
B
g
1
and
v
2
g
2
for the same
r
=
=
∈ Z
q
or, in other words, log
g
1
v
1
=
log
g
2
v
2
.
g
1
g
r
Then this ciphertext passes
B
's check and, bearing in mind that
v
1
=
=
in the simulation is
fv
−
z
1
1
v
−
z
2
2
g
2
g
xr
, the message output by
=
=
B
=
and
v
2
fv
−
z
1
g
r
)
−
z
1
g
xr
)
−
z
2
g
r
)
−
z
1
−
xz
2
f
(
(
=
f
(
=
, which is exactly the same output that
would be produced by a decryption oracle.
Next, suppose that the ciphertext
(
v
1
,
v
2
,
f
,
w
)
submitted by
A
is invalid in the
sense that log
g
1
v
1
=
log
g
2
v
2
. If the ciphertext does not pass the verification check
then it will be rejected by
exactly the same as it would be by a Cramer-Shoup
decryption oracle. But what about the possibility that this verification check is passed?
If the simulation deviates from the decryption oracle behavior at this point, this might
alter the success probability of
B
and invalidate the proof. However, we next show
that this does not happen because in the first stage of
A
A
's attack (before the challenge
ciphertext is given to
and the legitimate decryption oracle will reject any
invalid ciphertext except with negligible probability.
The verification test is to check that
w
A
) both
B
v
x
1
+
β
y
1
1
v
x
2
+
β
y
2
2
=
(where
β
=
H
(
v
1
||
v
2
||
f
)
)
which, taking logarithms, can be written as log
g
w
=
(
log
g
v
1
)
x
1
+
(
log
g
v
2
)
x
2
+
g
r
2
g
r
,
v
2
=
(
log
g
v
1
)β
y
1
+
(
log
g
v
2
)β
y
2
or, in a more compact form, letting
v
1
=
=
g
xr
:
xr
x
2
+
β
xr
y
2
.
=
rx
1
+
ry
1
+
β
log
g
w
(8.3)
This can be seen as a linear equation in the variables
x
1
,
x
2
,
y
1
,
y
2
with coefficients
in
Z
q
. Thus it defines a linear variety of dimension 4
−
1
=
3 in the 4-dimensional
q
q
).
Z
q
-vector space
Z
(the linear system has rank 1 and defines a 'hyperplane' of
Z
Now we must also take into account that
may have some information about the
private key that it can use to guess a value of
w
satisfying Eq.
8.3
when submitting
its decryption queries. In particular,
A
A
knows the public key from which, taking
