Cryptography Reference
In-Depth Information
g
x
1
1
g
x
2
2
g
y
1
1
g
y
2
2
=
=
logarithms in the equations
c
,
d
, the following information is
obtained:
log
g
c
=
x
1
+
xx
2
(8.4)
log
g
d
=
y
1
+
xy
2
It is not difficult to see that this is all the information available to
A
on the values
x
1
,
x
2
,
y
1
,
y
2
, even assuming that
A
can compute discrete logarithms, which is hard
in general. Thus the point
(
x
1
,
x
2
,
y
1
,
y
2
)
looks to
A
like a random point in the
q
defined by Eqs.
8.4
which, since the linear system has rank 2,
linear variety of
Z
containing
q
2
points. If
is a plane
P
A
submits a ciphertext
(
v
1
,
v
2
,
f
,
w
)
such that
r
but Eq.
8.3
holds (and hence the ciphertext is not
r
=
log
g
1
v
1
=
log
g
2
v
2
=
rejected), then the point
lies in the linear variety defined by the three
Eqs.
8.3
,
8.4
. These equations define a linear system of rank 3 (it is easy to see that,
except when
x
(
x
1
,
x
2
,
y
1
,
y
2
)
0 which occurs with negligible probability, the three rows of the
coefficient matrix are linearly independent as vectors of
=
4
Z
q
) and hence define a line
P
(
x
1
,
x
2
,
y
1
,
y
2
)
in
must belong. Since the line has
q
points, the probability
that the first invalid ciphertext submitted by
to which
q
2
A
/
=
/
is not rejected is
q
1
q
, which
is negligible as a function of
k
=
len
(
q
)
. After each rejection,
A
can exclude one line
in
and so the probability that the
i
th invalid ciphertext submitted is not rejected is
at most 1
P
makes a polynomial number of queries, all invalid
ciphertexts are rejected except with negligible probability and in this phase
/(
q
−
i
+
1
)
. Since
A
A
's attack
in the simulation carried out by
B
proceeds in the same way as if
A
were interacting
with a legitimate decryption oracle.
After submitting its queries, at the end of this stage,
A
outputs two messages
m
0
,
m
1
∈
G
.Next
B
chooses a random bit
b
←{
0
,
1
}
and computes the challenge
g
x
g
y
g
a
ciphertext. For this,
B
uses the DDH input 3-tuple
(
,
,
)
and sets:
g
y
u
1
:=
,
g
a
u
2
:=
,
u
z
1
u
z
2
m
b
,
:=
e
α
:=
H
(
u
1
||
u
2
||
e
),
u
x
1
+
α
y
1
1
u
x
2
+
α
y
2
2
v
:=
.
Next,
B
gives to
A
the challenge ciphertext:
(
u
1
,
u
2
,
e
,
v
)
and
may continue querying for decryptions of ciphertexts distinct from this one,
which are answered by
A
outputs a bit
b
B
in the form indicated above. Finally,
A
which is its guess on the value of
b
.
Now, algorithm
b
which, recalling Definition 7.4 means that
B
outputs
b
⊕
B
b
, i.e., if and only if
guesses that
a
=
xy
if and only
b
=
A
succeeds in the CCA
b
.
indistinguishability experiment. Therefore,
B
guesses that
a
is random in case
b
=
The intuition behind this choice is based on the following facts:
