Cryptography Reference
In-Depth Information
It is known from [9] that these codes satisfy a Gilbert-Varshamov-like bound
and that random codes attain this bound with a very high probability. In the
following we will use this result to set up our parameters.
2.4 Rank Distance and Cryptography
The security of the Chen protocol is based on the rank version of an NP-hard
problem, namely the syndrome decoding problem for the Hamming distance [2].
Syndrome Decoding Problem
Let
H
be a ((
n
−
k
)
×
n
)matrixoverGF(
q
m
)with
k
≤
n
,
i
∈
GF(
q
m
)
k
and
ω
≤
ω
and
Hs
t
=
i
where
wt
an integer. The problem is to find
s
such that
wt
(
s
)
denotes the Hamming weight.
The problem is considered hard in general, especially when the matrix
H
is
chosen at random. The best known algorithms for solving this problem are all
exponential in
ω
, a recent survey on this complexity can be found in [6].
The previous problem can be naturally extended to the rank distance:
Syndrome Decoding Problem for the Rank Distance.
Let
H
be a ((
n
−
k
)
×
n
)matrixoverGF(
q
m
)with
k
≤
n
,
i
∈
GF(
q
m
)
k
and
r
an integer. The
problem is to find
s
such that rank(
s
)=
r
and
Hs
t
=
i
.
In that case it is not proven that the problem is NP-hard, but the relation
with the Hamming case and the fact that the best known algorithms are all
exponential makes this problem dicult in practice and the problem is generally
believed to be hard.
There are two main approaches to this problem in the case of the rank matrix:
Chabaud and Stern proposed an algorithm to solve the problem in
O
((
nr
+
m
)
3
q
(
m
−
r
)(
r
−
1)
)(see [4]) Ourivski and Johannson proposed two algorithms, the
first uses a basis enumeration and is in
O
((
k
+
r
)
3
q
(
m
−
r
)(
r
−
1)+2
), the second uses
a coordinate enumeration and is in
O
((
k
+
r
)
3
q
(
m
−
r
)(
k
+1)
)(see [10]).
3 The Chen Protocol
The Chen identification protocol is a 5-pass zero-knowledge protocol with a
cheating probability of 1
/
2. This protocol has the attractive feature that it does
not use any hash function, as the original Fiat-Shamir protocol, but unlike other
zero-knowledge protocols based on linear functions. Indeed, the PKP protocol
and Stern's SD protocol both need a hash function. Chen's protocol works as
follows. Let
H
bearandommatrixoverGF(
q
m
),
s
awordoflowrankweight
and
i
=
Hs
t
. If Alice knows the secret
s
then
i
is called her identity. The aim of
the protocol is for Alice to prove that she knows
s
and for Bob to know whether
Alice knows
s
. The protocol is split into six steps and uses the word
s
of rank
r
as private key and a random matrix
H
and the syndrome
i
=
Hs
t
as public key.
The diculty of the protocol relies on the diculty of solving the syndrome
decoding problem for the rank distance. In the original paper, Chen proved that
to satisfy the soundness property one needs to choose the rank weight of the
