Cryptography Reference
In-Depth Information
vector space of dimension
r
. The coordinates of
sP
−
1
generate the vector space
E
so we can construct a basis of
E
over GF(q) with them.
Let us denote
γ
=(
γ
1
,...,γ
r
) this basis, with
γ
GF(
q
m
)
r
.Wecanex-
press each coordinate
s
j
,
j
from 1 to
n
,of
s
into this basis and obtain
s
j
=
∈
k
=1
a
k,j
γ
k
)with
a
k,j
GF(q) for
k
between 1 and
r
and
j
between 1 and
n
.
We construct a basis of GF(
q
m
)overGF(
q
) such that its first
r
vectors are equal
to
γ
1
,...,γ
r
.Wecallit
γ
=(
γ
1
,...,γ
r
,γ
r
+1
,...,γ
m
)with
γ
l
∈
GF(
q
m
)for
l
from 1 to
m
. Writing the equation
Hs
t
=
i
into GF(
q
) with the basis
γ
,permits
to obtain (
n
−
k
)
∈
×
m
equations on GF(
q
)and
n
×
r
unknowns (the
a
k,j
). In the
parameters proposed for the Chen protocol we always have
n
×
r
≤
×
m
,
so the system is directly solvable by Gaussian elimination and one can recover
the secret
s
.
(
n
−
k
)
Attack's complexity.
For this algorithm we have to generate a basis of car-
dinality
r
from
n
vectors, complete this basis and invert an
n
×
r
matrix over
GF(
q
). The only cost we have to focus on is the matrix inversion, a O(
N
3
) algo-
rithm, with
N
=
n
×
r
equal to 128 as proposed in [4], this attack cost about 2
21
operations in GF(
q
). Our approach , which is specific to this protocol, permits to
avoid the (exponential) search for a basis in which one can express the secret
s
.
As soon as the previous inequality is satisfied, which is the case for all proposed
parameters (the original Chen parameters and Chabaud and Stern parameters)
the protocol can be broken in polynomial time at the cost of a Gaussian elimina-
tion for a matrix of size
n
×
r
. We checked on examples that the attack worked
in practice with this complexity.
We now describe our second attack.
4.3 Linear Attack
High level overview.
This attack relies on the fact that no hash function is
used in the commitment step, which makes it possible to use information from
each commitment.
Suppose a passive attacker can observe an exchange between a prover and
a verifier with
b
= 0 in the protocol. In this case, the values
HP
t
x
t
and
Hx
t
correspond to a system of 2
k
equations in the
n
coordinates of
x
.IntheChen
parameters, where
n
is equal to 2
k
, it is possible to retrieve
x
in only one iteration
of the protocol. With the knowledge of
P
(in the
b
=0case)and
x
, the secret
s
can be deduced from
w
=
x
+
λsP
−
1
. In this paragraph we show how to deduce
the secret
s
for any type of possible parameters. Indeed, each occurrence of the
protocol for the
b
= 0 case has the possibility to give new linear equations in
the variables which compose the secret key
s
.Morespecifically,everytimethe
prover sends a new
P
,(say
P
j
), there are as many new equations as the number
of rows of
HP
j
independent from the rows of
HP
k
for
k
≤
j
and
H
.
Description.
In order to prove his identity to a verifier, a prover runs the pro-
tocol several times. For every execution of the protocol, the prover sends two
