Gabidulin code

Gabidulin code[1,2]

Also known as Vector rank-metric code.

Description

A linear code over \(GF(q^N)\) that corrects errors over rank metric instead of the traditional Hamming distance. Every element \(GF(q^N)\) can be written as an \(N\)-dimensional vector with coefficients in \(GF(q)\), and the rank of a set of elements is rank of the matrix formed by their coefficients.

Given \(X^n=\text{span}\{x_i\}\), an \(n\)-dimensional vector space over \(GF(q^N)\) (where \(q\) is a power of a prime number), the rank metric \(d(x, y)\) is defined via the rank norm \(r(x, q) = \mathrm{rank}(A(x))\), where \begin{align} A(x) = \begin{pmatrix} a_{11} & a_{12} & \ldots & a_{1n} \\ a_{21} & a_{22} & \ldots & a_{2n} \\ a_{N1} & a_{N2} & \ldots & a_{Nn}~, \end{pmatrix} \tag*{(1)}\end{align} and \(x_i = a_{1i} u_1 + a_{2i} u_2 + \ldots + a_{Ni}u_N \) for some fixed basis \(\{u_i\}_{i=1}^N\).

Protection

Set of vectors \(\{x_1, x_2, \ldots, x_M\}\) determines a rank code with distance \(d=\min d(x_i, x_j)\). The code with distance \(d\) corrects all errors with rank of the error not greater than \(\lfloor (d-1)/2\rfloor\).

Decoding

Fast decoder based on a transform-domain approach [3].Algebraic list decoder that decodes up to the Singleton bound [4].

Realizations

Public-key cryptosystems [5,6].Digital watermarking. The Gabidulin code provides efficient correction against luminance tampering and image-slicing distortion due to the consistency of the rank against alterations such as column swapping [7].

Parent

Rank-metric code — Gabidulin codes over \(GF(q^N)\), when expressed as matrices over \(GF(q)\), are rank-metric codes (see Def. 14 in Ref. [8]). The reverse is not always true since Gabidulin codes are not always \(GF(q^N)\)-linear [8; Rm. 16].

Cousins

Maximum-rank distance (MRD) code — Gabidulin codes over \(GF(q^N)\) with maximum rank-distance, when expressed as matrices over \(GF(q)\), are MRD codes.
Linear \(q\)-ary code — Gabidulin codes over \(GF(q^N)\), when expressed as vectors over \(GF(q^N)\), are linear \(q\)-ary codes.

References

[1]: E. M. Gabidulin, Theory of Codes with Maximum Rank Distance, Problemy Peredachi Informacii, Volume 21, Issue 1, 3–16 (1985)
[2]: R. M. Roth, “Maximum-rank array codes and their application to crisscross error correction”, IEEE Transactions on Information Theory 37, 328 (1991) DOI
[3]: D. Silva and F. R. Kschischang, “Fast encoding and decoding of Gabidulin codes”, 2009 IEEE International Symposium on Information Theory (2009) arXiv:0901.2483 DOI
[4]: V. Guruswami and C. Xing, “List decoding reed-solomon, algebraic-geometric, and gabidulin subcodes up to the singleton bound”, Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (2013) DOI
[5]: T. P. Berger and P. Loidreau, “How to Mask the Structure of Codes for a Cryptographic Use”, Designs, Codes and Cryptography 35, 63 (2005) DOI
[6]: T. Lau and C. Tan, “A New Technique in Rank Metric Code-Based Encryption”, Cryptography 2, 32 (2018) DOI
[7]: P. Lefevre, P. Carre, and P. Gaborit, “Watermarking and Rank Metric Codes”, 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) (2018) DOI
[8]: A. Ravagnani, “Rank-metric codes and their duality theory”, (2015) arXiv:1410.1333

Page edit log

Micah Shaw (2022-08-09) — most recent
Victor V. Albert (2022-05-25)
Victor V. Albert (2021-12-16)
Marianna Podzorova (2021-12-13)

Cite as:

“Gabidulin code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/gabidulin

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/matrices/rank-metric/gabidulin.yml.