Cryptography Reference
In-Depth Information
=
A
(i)
If
a
xy
then the challenge ciphertext given to
in the oracle simulation
A
is a legitimate encryption of
m
b
. Our hypothesis that
succeeds in the CCA
indistinguishability experiment with non-negligible probability then implies
that the probability that
b
b
is non-negligibly better than 1
=
/
2 and hence so
is the probability that
B
outputs 0, in which case
B
succeeds.
(ii)
If
a
is random (and hence
a
's
view in the CCA indistinguishability experiment is essentially independent from
b
and hence so is
=
xy
except with negligible probability), then
A
's output
b
. Therefore, in this case,
b
b
with probability
A
=
negligibly different from 1
/
2 and
B
succeeds in the DDH experiment with this
same probability.
(i) is easy to prove as follows. If
(
u
1
,
u
2
,
e
,
v
)
is the challenge ciphertext, then,
g
1
,
u
2
g
xy
1
g
2
. Moreover,
g
y
g
a
by construction, we have that
u
1
=
=
=
=
=
u
z
1
u
z
2
m
b
g
1
)
g
2
)
g
yz
1
z
1
z
2
m
b
setting
z
=
z
1
+
xz
2
we have that
e
=
=
(
(
=
m
b
.
u
x
1
+
α
y
1
1
u
x
2
+
α
y
2
2
We also have that
α
=
H
(
u
1
||
u
2
||
e
)
and, finally, that
v
=
=
g
1
)
g
1
)
α
y
1
g
2
)
g
2
)
α
y
2
g
x
1
1
g
x
2
2
g
y
1
1
g
y
2
2
x
1
x
2
y
y
α
c
y
d
y
α
. Thus we see that
(
(
(
(
=
(
)
(
)
=
the challenge ciphertext is an encryption of
m
b
with
r
=
y
.
g
xy
, where
y
g
y
,
u
2
g
a
y
except
with negligible probability. Then (ii) is a consequence of the following claims:
Next, in order to prove (ii) let
u
1
=
=
=
=
B
Claim (1)
If
, simulating a decryption oracle, rejects all invalid ciphertexts, then
the bit
b
is independent of
A
's view (which includes the challenge cipher-
text).
Claim (2)
B
rejects all invalid ciphertexts submitted by
A
except with negligible
probability.
In order to prove Claim (1), we show that if
(
u
1
,
u
2
,
e
,
v
)
is the challenge ciphertext
, then
u
z
1
u
z
2
given to
A
by
B
is uniformly distributed in
G
in
A
's view and hence
u
z
1
u
z
2
m
b
looks independent from
m
b
(and hence from
b
)to
e
=
A
. To see this
q
. At the beginning of the attack
consider the point
(
z
1
,
z
2
)
∈ Z
A
knows from the
g
z
1
g
z
2
, which, taking logarithms, gives the linear equation in
the variables
z
1
,
z
2
with coefficients in
public key that
h
=
Z
q
:
log
g
h
=
z
1
+
xz
2
.
(8.5)
At this point,
(
z
1
,
z
2
)
looks to
A
like a random point in the line defined by this
equation. Next,
A
may submit decryption queries that
B
will answer but, as we are
assuming that
B
only answerswhen the submitted ciphertext
(
v
1
,
v
2
,
f
,
w
)
is valid, we
g
r
z
1
1
g
r
z
2
2
see that then
h
r
v
z
1
v
z
2
for some
r
∈ Z
q
and this gives an equation:
=
=
r
log
g
h
r
z
1
+
r
xz
2
,
=
(8.6)
which is a scalar multiple of Eq.
8.5
and hence provides no additional informa-
tion to
A
about
(
z
1
,
z
2
)
. Consider now the challenge ciphertext
(
u
1
,
u
2
,
e
,
v
)
, where
u
z
1
u
z
2
. This gives the equation:
log
g
ε
=
e
=
ε
m
b
with
ε
=
y
xz
2
.
yz
1
+
(8.7)
