Cryptography Reference
In-Depth Information
Z
q
and, except in the
This is, again, a linear equation in the variables
z
1
,
z
2
over
case
y
=
y
(which occurs with negligible probability), the equation is linearly inde-
pendent from Eq.
8.5
. Therefore, each element of
G
occurs as the value of
ε
for
exactly one choice of the pair
ε
is uniformly distributed in
G
and, as in the proof of perfect security of the one-time
pad based on Shannon's theorem (Theorem 3.1),
(
z
1
,
z
2
)
. This implies that from
A
's point of view,
obtains no information about
b
.
Let us now show that Claim (2) is also true. As in the previous analysis of the rejec-
tion of invalid ciphertexts in the attack phase preceding the generation of the challenge
ciphertext, we study the distribution of the point
P
A
q
condi-
=
(
x
1
,
x
2
,
y
1
,
y
2
)
∈ Z
tioned on
A
's view. Now the situation is different because, in addition to Eqs.
8.4
,
A
has additional information coming from the challenge ciphertext
(
u
1
,
u
2
,
e
,
v
)
.This
u
x
1
+
α
y
1
1
u
x
2
+
α
y
2
2
information comes from the fact that now
A
knows that
v
=
, where
g
xy
, with
y
=
g
y
,
u
2
=
g
a
u
1
=
=
y
except with negligible probability. Thus
P
4
must also lie in the hyperplane of
Z
q
defined by the linear equation:
xy
x
2
+
α
xy
y
2
.
log
g
v
=
yx
1
+
yy
1
+
α
(8.8)
Therefore, once the challenge ciphertext is received,
P
looks to
like a random
point in the intersection of the plane defined by Eqs.
8.4
with the hyperplane defined
by Eq.
8.8
. The linear system formed by these three equations is easily seen to have
rank 3, so it defines a line in which
P
must lie.
Now, in order to prove Claim (2), suppose that
A
A
submits to
B
an invalid cipher-
xr
, with
r
r
, and let
text
(
v
1
,
v
2
,
f
,
w
)
, where log
g
v
1
=
r
and log
g
v
2
=
=
β
=
H
(
v
1
||
v
2
||
f
)
. Note that, because of the rules of the CCA indistinguishability
experiment,
(
v
1
,
v
2
,
f
,
w
)
=
(
u
1
,
u
2
,
e
,
v
)
. There are three possibilities which we
consider separately:
(
v
1
,
v
2
,
)
=
(
u
1
,
u
2
,
)
=
α
=
(
u
1
||
u
2
||
)
1.
f
e
. In this case we know that
v
w
but
H
e
=
(
v
1
||
v
2
||
)
=
β
H
f
. Then, the verification test gives:
v
x
1
+
β
y
1
1
v
x
2
+
β
y
2
2
u
x
1
+
α
y
1
1
u
x
2
+
α
y
2
2
=
=
v
=
w
,
so that the ciphertext is rejected by
B
.
2.
(
. The ciphertext will be rejected unless
P
lies
in the hyperplane defined by Eq.
8.3
which expresses the verification condition.
The intersection of this hyperplane with the line defined by Eqs.
8.4
and
8.8
is a
linear variety whose dimension is 4
v
1
,
v
2
,
f
)
=
(
u
1
,
u
2
,
e
)
and
β
=
α
−
rk
, where
rk
is the rank of the coefficient
matrix of the linear system formed by these four equations, namely the matrix:
⎛
⎝
⎞
⎠
1
x
00
001
x
yxy
xy
α
y
α
rxr
xr
β
r
β
