Cryptography Reference
In-Depth Information
To compute the rank in this case it suffices to compute the determinant
d
which
turns out to be
=
=
4) except with negligible probability. Indeed,
by using elementary operations on columns and Laplace expansion we see that:
0 (and hence
rk
0
1
x
y
−
xy
d
=
x
(
y
)α
y
α
r
−
xr
x
(
r
)β
r
β
=
y
−
y
−
x
(
y
)α
x
(
y
)
x
2
y
−
r
−
=−
(α
−
β)(
y
)(
r
)
r
−
r
−
x
(
r
)β
x
(
r
)
0 and
y
=
Now, we know that, except with negligible probability,
x
=
y
, and
we have also assumed that
r
=
r
, and
α
=
β
, so that we may conclude that
d
0 (as usual, except with negligible probability). This means that the linear
variety defined by the matrix is a point
Q
. Therefore, the probability that an
invalid ciphertext submitted by
=
is equal to the probability
that a randomly chosen point
P
in the line defined by Eqs.
8.4
and
8.8
is precisely
Q
and so is equal to 1
A
is not rejected by
B
/
q
and hence negligible.
3.
(
. Since we are assuming that
H
is collision
resistant, the probability of this happening is, again, negligible.
v
1
,
v
2
,
f
)
=
(
u
1
,
u
2
,
e
)
and
β
=
α
In conclusion, since we have proved facts (i) and (ii) above, we know that there
exists a non-negligible function
ε(
k
)
such that
1
2
+
ε(
Pr
(B
succeeds
|
a
=
xy
)
=
k
)
and a negligible function
negl
(
k
)
such that
1
2
±
negl
(
k
).
Pr
(B
succeeds
|
a
=
xy
)
=
Since in the DDH experiment a random bit is chosen that determines whether the
triple is a DDH triple (i.e.,
a
=
xy
in the above notation) or a random triple, both
events have probability 1
/
2 and so, by Proposition 2.1 we have that
1
2
·
1
2
·
Pr
(B
succeeds
)
=
Pr
(B
succeeds
|
a
=
xy
)
+
Pr
(B
succeeds
|
a
=
xy
)
1
2
·
(
1
2
+
ε(
1
2
·
(
1
2
±
negl
(
k
))
=
k
))
+
1
2
+
1
2
·
(ε(
=
k
)
±
negl
(
k
)).
Since
ε(
k
)
is non-negligible we see that so is the function
ε(
k
)
±
negl
(
k
)
and
hence
B
succeeds with non-negligible advantage. This ends the proof.