Cryptography Reference
In-Depth Information
The paper is organized as follows: Section 2 and 3 recall the main properties
of the rank distance and Chen's protocol. In Section 4 we explain the two attacks
that we propose and which break the original Chen protocol. Section 5 proposes
a repaired version of the protocol: the new version is immune to our attacks, but
at the cost of introducing a hash function. Finally Section 6 considers parameters
for the repaired protocol.
2 Basic Facts on Rank Distance
The rank distance was introduced in coding theory by Gabidulin in 1985 in [7].
Since the decoding problem is seemingly more dicult for the rank distance
than for the Hamming distance, codes for the rank metric have been variously
proposed as alternatives to ordinary error-correcting codes when they play a
role in a cryptographic protocol. In the following we recall basic facts on this
metric. We refer the reader to P. Loidreau's paper [9] for more details on the
rank distance and its use in cryptography.
2.1 Definitions and Notation
Notation :
Let
q
beapowerofaprime
p
,
m
an integer and let
V
n
be a
n
dimensional vector
space over the finite field GF(
q
m
). Let
β
=(
β
1
,...,β
m
)beabasisofGF(
q
m
)
over GF(
q
).
Let
F
i
be the map from GF(
q
m
)toGF(
q
)where
F
i
(
x
)isthe
i
i-th coordinate of
x
in the basis
β
.
To any
v
=(
v
1
,...,v
n
)in
V
n
we associate the matrix
v
∈M
m,n
(GF(
q
)) in
which
v
i,j
F
i
(
v
j
).
The rank weight of a vector
v
can be defined as the rank of the associated matrix
v
. If we name this value rank(
v
) we can have a distance between two vectors
x, y
using the formula rd(
x, y
)=rank(
x
−
y
).
We now introduce an equivalence relation
=
∼
between two vectors
x
and
y
of
V
n
:
Definition 1.
For
x, y
∈
V
n
we say that
x
and
y
are equivalent (denoted by
x
∼
y
) if and only if their coordinates generate the same vector space.
We remark that this definition is independent of the basis and that it is possible
to have rank(
x
)=rank(
y
) without
x
∼
y
.
We can see that
x
∼
y
is equivalent to the existence of a
n
×
n
invertible
matrix
P
over GF(
q
) which satisfy
xP
=
y
.
2.2 Properties
The isometry group for the rank distance is computed in [1] and is composed
of two families: right multiplication by an invertible matrix over GF(
q
)and
multiplication of columns by a non-zero element of GF(
q
m
). With these two
