Cryptography Reference
In-Depth Information
possible values (see step 5 of the description of the Chen protocol). The linear at-
tack works when the prover has to send the variable named
P
(see description of
the protocol). Since the protocol is based on a choice between two challenges, we
can consider that it happens often. We call this challenge the challenge "
b
=0".
Let us denote by
x, P, w, λ, c
, the variables used in a challenge "
b
= 0" encoun-
tered, corresponding to the variables with same names as in the description of
the Chen protocol. Remember that for the challenge "
b
=0"thevariable
x
is
unknown and the variables
P, w, λ
and
c
are known. We will prove that other
occurrences of the challenge "
b
= 0" give linear equations in the coordinates of
s
.
The definition of
Hs
t
=
i
gives equations in the coordinates of
s
but not
enough to solve a system. To add more equations to the system we use those
given by the challenge ”
b
=0”:
w
=
x
+
λsP
−
1
c
=
xH
t
We o bta in :
Hw
t
=
c
+
λH
(
sP
−
1
)
t
In the challenge ”
b
= 0” the only unknown here is
s
, this gives new equations
in the coordinates of
s
as long as these equations are linearly independent. Sup-
posing that we have
n
−
1 equations in our system, which is the worst case, the
probability for uniformly generated equations to be dependent of the system is
equal to
q
m
.Thefactthat
P
is uniformly generated implies that
HP
−
t
forms
uniformly generated equations. The probability of obtaining linearly indepen-
dent equations is therefore very high.
The attack is finished when the number of equations is sucient to solve the
system.
Example
[Active attack] The previous passive attack can easily be turned into
an active attack. An attacker can choose to send only the value 0 in the fourth
step of the protocol and obtain information leakage which eventually gives the
previous attack.
The attack is based on the fact that no hash function is used in the commit-
ment which makes a leakage of information possible.
1
Complexity of the attack and implementation.
A square matrix in GF(
q
m
)
has a good probability of being invertible, since the cardinality of GF(
q
m
)isfar
from 2. The only cost we have to focus on is the matrix inversion which is cubic
in O(
N
3
) with a simple algorithm and can be decreased with fast multiplica-
tion. With
n
about equal to 32 as proposed in [5], the complexity of the attack is
about
W
×
(2
5
)
3
with
W
the cost of a multiplication in GF(
q
m
). An implemen-
tation of this attack using the mathematics software sage [12] found 2
21
secrets
s
in 38013
.
98 seconds and it happened only once during the 2
21
tests that the
matrix was not invertible. It makes the attack very fast and is coherent with the
expected computational complexity.
