Cryptography Reference
In-Depth Information
families it is not possible to transform a word with fixed rank to any word with
same rank. The fact that isometries may transform a word of given (rank or
Hamming) weight to any other word with the same weight is very useful, it
is for instance the case for the Hamming weight with permutation. We now
introduce the product "
∗
" in order to obtain a similar propriety with the rank
metric.
For a given basis
β
,wedenote
Φ
β
the inverse of the function
V
n
→M
m,n
(GF(
q
)):
x
→
x
computed with the basis
β
.
Definition 2 (product).
Let
Q
be in
M
m,m
(GF(
q
))
,
v
∈
V
n
and
β
abasis.
We define the product
Q
∗
v
such that
Q
∗
v
=
Φ
β
(
Qv
)
,where
v
is constructed
from the basis
β
.
The following property of the product is useful.
Proposition 1.
For any
x
∈
V
n
,
P
∈M
n,n
(GF(
q
))
and
Q
∈M
m,m
(GF(
q
))
,
we have
(
Q
∗
x
)
P
=
Q
∗
(
xP
)
.
Proof.
It is clear that (
Qx
)
P
=
Q
(
xP
). To conclude we just have to notice that
xP
=
xP
.
Moreover the product has the two important straightforward following properties
(rank preservation and linearity over the base field
GF
(
q
)):
Proposition 2.
For any
x
∈
V
n
and
Q
∈
GL
m
(
q
)
,
rank(
Q
∗
x
)=rank(
x
)
and
for any
a, b
∈
GF
(
q
)
and
x, y
∈
V
n
:
aQ
∗
x
+
bQ
∗
y
=
Q
∗
(
ax
+
by
)
.
Finally the following property shows that the "*" permits to associate a word
with a given rank to any word with the same rank.
Proposition 3.
For any
x, y
∈
V
n
and
rank(
x
)=rank(
y
)
, it is possible to find
P
∈M
n,n
(GF(
q
))
and
Q
∈M
m,m
(GF(
q
))
such that
x
=
Q
∗
yP
.
Proof.
Let us denote by
r
the rank of
x
and
y
.Noticethat
r
is then less or
equal to
m
and
n
. To prove the property we just have to prove that there
is
Q
∈M
m,m
(GF(
q
)) which satisfies
x
∼
Q
∗
y
. As we said previously, this is
equivalent to the existence of a matrix
P
which satisfies
Q
∗
yP
=
x
.Let
y
1
,...,y
n
be the coordinates of
y
. We reorder them to obtain
y
σ
(1)
,...,y
σ
(
r
)
,...,y
σ
(
n
)
with
y
σ
(1)
,...,y
σ
(
r
)
linearly independent. We extend the family
y
σ
(1)
,...,y
σ
(
r
)
to make a basis
γ
.Wedothesamewith
x
1
,...,x
n
to make
γ
,anextendedbasis
of the family (
x
i
). Let
Q
be the matrix which transforms
γ
into
γ
;
Q
∗
y
is now
a vector with all its coordinates in
γ
and moreover, all its coordinates are in
x
σ
(1)
,...,x
σ
(
r
)
.
2.3 Codes for the Rank Distance
We refer to [9] for more details on codes for the rank distance.
Acode
C
of length
n
and dimension
k
over GF(
q
m
) is a subspace of dimension
k
of GF(
q
m
). The minimum rank distance of the code
C
is the miminum rank
of non-zero vectors of the code.
