Additional information

• Images
• Videos
• Documents
• Books
• Articles

Rank metric

Let X n {\displaystyle X^{n}} be an n-dimensional vector space over the finite field G F ( q N ) {\displaystyle GF\left({q^{N}}\right)} , where q {\displaystyle q} is a power of a prime and N {\displaystyle N} is a positive integer. Let ( u 1 , u 2 , … , u N ) {\displaystyle \left(u_{1},u_{2},\dots ,u_{N}\right)} , with u i ∈ G F ( q N ) {\displaystyle u_{i}\in GF(q^{N})} , be a base of G F ( q N ) {\displaystyle GF\left({q^{N}}\right)} as a vector space over the field G F ( q ) {\displaystyle GF\left({q}\right)} .

Every element x i ∈ G F ( q N ) {\displaystyle x_{i}\in GF\left({q^{N}}\right)} can be represented as x i = a 1 i u 1 + a 2 i u 2 + ⋯ + a N i u N {\displaystyle x_{i}=a_{1i}u_{1}+a_{2i}u_{2}+\dots +a_{Ni}u_{N}} . Hence, every vector x → = ( x 1 , x 2 , … , x n ) {\displaystyle {\vec {x}}=\left({x_{1},x_{2},\dots ,x_{n}}\right)} over G F ( q N ) {\displaystyle GF\left({q^{N}}\right)} can be written as matrix:

x → = ‖ a 1 , 1 a 1 , 2 … a 1 , n a 2 , 1 a 2 , 2 … a 2 , n … … … … a N , 1 a N , 2 … a N , n ‖ {\displaystyle {\vec {x}}=\left\|{\begin{array}{*{20}c}a_{1,1}&a_{1,2}&\ldots &a_{1,n}\\a_{2,1}&a_{2,2}&\ldots &a_{2,n}\\\ldots &\ldots &\ldots &\ldots \\a_{N,1}&a_{N,2}&\ldots &a_{N,n}\end{array}}\right\|}

Rank of the vector x → {\displaystyle {\vec {x}}} over the field G F ( q N ) {\displaystyle GF\left({q^{N}}\right)} is a rank of the corresponding matrix A ( x → ) {\displaystyle A\left({\vec {x}}\right)} over the field G F ( q ) {\displaystyle GF\left({q}\right)} denoted by r ( x → ; q ) {\displaystyle r\left({{\vec {x}};q}\right)} .

The set of all vectors x → {\displaystyle {\vec {x}}} is a space X n = A N n {\displaystyle X^{n}=A_{N}^{n}} . The map x → → r ( x → ; q ) {\displaystyle {\vec {x}}\to r\left({\vec {x}};q\right)} ) defines a norm over X n {\displaystyle X^{n}} and a rank metric:

d ( x → ; y → ) = r ( x → − y → ; q ) {\displaystyle d\left({{\vec {x}};{\vec {y}}}\right)=r\left({{\vec {x}}-{\vec {y}};q}\right)}

Rank code

A set { x 1 , x 2 , … , x n } {\displaystyle \{x_{1},x_{2},\dots ,x_{n}\}} of vectors from X n {\displaystyle X^{n}} is called a code with code distance d = min d ( x i , x j ) {\displaystyle d=\min d\left(x_{i},x_{j}\right)} . If the set also forms a k-dimensional subspace of X n {\displaystyle X^{n}} , then it is called a linear (n, k)-code with distance d {\displaystyle d} . Such a linear rank metric code always satisfies the Singleton bound d ≤ n − k + 1 {\displaystyle d\leq n-k+1} with equality.

Generating matrix

There are several known constructions of rank codes, which are maximum rank distance (or MRD) codes with d = n − k + 1. The easiest one to construct is known as the (generalized) Gabidulin code, it was discovered first by Delsarte (who called it a Singleton system) and later by Gabidulin ² (and Kshevetskiy ³ ).

Let's define a Frobenius power [ i ] {\displaystyle [i]} of the element x ∈ G F ( q N ) {\displaystyle x\in GF(q^{N})} as

x [ i ] = x q i mod N . {\displaystyle x^{[i]}=x^{q^{i\mod N}}.\,}

Then, every vector g → = ( g 1 , g 2 , … , g n ) ,   g i ∈ G F ( q N ) ,   n ≤ N {\displaystyle {\vec {g}}=(g_{1},g_{2},\dots ,g_{n}),~g_{i}\in GF(q^{N}),~n\leq N} , linearly independent over G F ( q ) {\displaystyle GF(q)} , defines a generating matrix of the MRD (n, k, d = n − k + 1)-code.

G = ‖ g 1 g 2 … g n g 1 [ m ] g 2 [ m ] … g n [ m ] g 1 [ 2 m ] g 2 [ 2 m ] … g n [ 2 m ] … … … … g 1 [ ( k − 1 ) m ] g 2 [ ( k − 1 ) m ] … g n [ ( k − 1 ) m ] ‖ , {\displaystyle G=\left\|{\begin{array}{*{20}c}g_{1}&g_{2}&\dots &g_{n}\\g_{1}^{[m]}&g_{2}^{[m]}&\dots &g_{n}^{[m]}\\g_{1}^{[2m]}&g_{2}^{[2m]}&\dots &g_{n}^{[2m]}\\\dots &\dots &\dots &\dots \\g_{1}^{[(k-1)m]}&g_{2}^{[(k-1)m]}&\dots &g_{n}^{[(k-1)m]}\end{array}}\right\|,}

where gcd ( m , N ) = 1 {\displaystyle \gcd(m,N)=1} .

Applications

There are several proposals for public-key cryptosystems based on rank codes. However, most of them have been proven insecure (see e.g. Journal of Cryptology, April 2008⁴).

Rank codes are also useful for error and erasure correction in network coding.

See also

• Linear code
• Reed–Solomon error correction
• Berlekamp–Massey algorithm
• Network coding

Notes

• Gabidulin, Ernst M. (1985), "Theory of codes with maximum rank distance", Problems of Information Transmission, 21 (1): 1–12
• Kshevetskiy, Alexander; Gabidulin, Ernst M. (4–9 September 2005). "The new construction of rank codes". Proceedings. International Symposium on Information Theory, 2005. ISIT 2005. pp. 2105–2108. doi:10.1109/ISIT.2005.1523717. ISBN 978-0-7803-9151-2. S2CID 11679865.
• Gabidulin, Ernst M.; Pilipchuk, Nina I. (June 29 – July 4, 2003). "A new method of erasure correction by rank codes". IEEE International Symposium on Information Theory, 2003. Proceedings. p. 423. doi:10.1109/ISIT.2003.1228440. ISBN 978-0-7803-7728-8. S2CID 122552232.

External links

• MATLAB implementation of a Rank–metric codec

References

1. Codes for which each input symbol is from a set of size greater than 2. ↩

2. Gabidulin, Ernst M. (1985). "Theory of codes with maximum rank distance". Problems of Information Transmission. 21 (1): 1–12. https://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=ppi&paperid=967&option_lang=eng ↩

3. Kshevetskiy, Alexander; Gabidulin, Ernst M. (4–9 September 2005). "The new construction of rank codes". Proceedings. International Symposium on Information Theory, 2005. ISIT 2005. pp. 2105–2108. doi:10.1109/ISIT.2005.1523717. ISBN 978-0-7803-9151-2. S2CID 11679865. 978-0-7803-9151-2 ↩

4. Overbeck, R. (2008). "Structural Attacks for Public Key Cryptosystems based on Gabidulin Codes". Journal of Cryptology. 21 (2): 280–301. doi:10.1007/s00145-007-9003-9. S2CID 2393853. https://doi.org/10.1007%2Fs00145-007-9003-9 ↩