Cryptography Reference
In-Depth Information
1.
[First commitment step]
The prover chooses
x
∈
V
n
and
P
∈
GL
n
(GF(
q
)).
c
=
HP
t
x
t
and
c
=
Hx
t
.
He sends
2.
[First challenge step]
The verifier sends a random
λ
∈
GF(
q
m
).
3.
[Second commitment step]
The prover computes
w
=
x
+
λsP
−
1
and sends it.
4.
[Second challenge step]
The verifier sends at random
b
∈{
0
,
1
}
.
5.
[Answer step]
The prover sends
P
if
b
=0or
x
if
b
=1.
6.
[Verification step]
If
b
=1and
λ
= 0, the verifier checks
c
and if rank(
w
−
x
)=
r
.
c
and if rank(
w
−
x
)=0.
If
b
=1and
λ
= 0, the verifier checks
HP
t
w
t
=
c
+
λi
.
If
b
= 0, the verifier checks if
Fig. 1.
Chen's protocol
secret not more than
3
where
d
is the minimum rank distance of the code whose
parity-check matrix is
H
(
d
corresponds to the Gilbert-Varshamov-like bound).
Notice that the rank weight of the secret was increased to
2
by Chabaud-Stern
in [4]. Later (in section 6) we will see how it is possible to push it up to
d
with
a new protocol.
4 Cryptanalysis
In this section we first explain why there are flaws in the zero-knowledge proof
of the Chen protocol and then we propose two full cryptanalysis by passive
attacks on the protocol which uses these flaws. The attacker will just need access
to the public data exchanged during the protocol to retrieve the secret key
of the protocol. The first attack relies on the fact that in the protocol, the
masking of the secret at Step 3 by a right multiplication by an invertible matrix
is not enough. This attack can be easily countered by modifying the masking
procedure. The second attack involves a recovery of the secret by linear algebra
from leaking information when
b
= 0 and does not seem to be reparable without
the introduction of hash functions.
4.1 Flaws in Chen's Zero-Knowledge Proof
The two attacks rely on a flaw in Chen's proof of zero-knowledge. Proofs of zero-
knowledge are generally made with a simulator of the scheme. The simulator
proves that someone can create a scheme indistinguishable from a real execution
in reasonable time without knowing the private key. With this assumption, it
is clear that the view of the execution of the scheme is not needed to attack
it. The simulator given by Chen in his paper [5] is in fact false since the zero-
knowledge proof omits the last sending of the scheme. Hence the incompleteness
