Generalized RS (GRS) code

Description

An \([n,k,n-k+1]_q\) linear code that is a modification of the RS code where codeword polynomials are multiplied by additional prefactors. Each message \(\mu\) is encoded into a string of values of the corresponding polynomial \(f_\mu\) at the points \(\alpha_i\), multiplied by a corresponding nonzero factor \(v_i \in GF(q)\), \begin{align} \mu\to\left( v_{1}f_{\mu}\left(\alpha_{1}\right),v_{2}f_{\mu}\left(\alpha_{2}\right),\cdots,v_{n}f_{\mu}\left(\alpha_{n}\right)\right)~. \end{align}

Protection

The code can detect \(n-k\) errors, and can correct errors \( \left\lfloor (n-k)/2\right\rfloor \) errors.

Decoding

The decoding process of GRS codes reduces to the solution of a polynomial congruence equation, usually referred to as the key equation. Decoding schemes are based on applications of the Euclid algorithm to solve the key equation.Berlekamp-Massey decoder with runtime of order \(O(n^2)\) [1][2][3].Guruswami-Sudan list decoder [4] and modification by Koetter-Vardy for soft-decision decoding [5].

Realizations

Commonly used in mass storage systems such as CDs, DVDs, QR codes etc.Various cloud storage systems [6].Public-key cryptosystems generalizing those that used Goppa codes [7][8][9], some of which were proven to be insecure [10]. More recent works focus on methods to mask the algebraic structure using subcodes of GRS codes [11]. For example, a key-recovery attack was developed in Ref. [12] for a variant of masking method proposed in Ref. [13].

Parents

  • Evaluation AG code — GRS (RS) codes are in one-to-one correspondence with evaluation AG codes of univariate polynomials \(f\) with \(\cal X\) being the projective (affine) line ([14], Thm. 15.3.24; [15], Ch. 3.2; [16]).
  • Polynomial evaluation code — GRS (RS) codes are in one-to-one correspondence with univariate polynomial evaluation codes with \(\cal X\) being the projective (affine) line ([14], Thm. 15.3.24; [15], Ch. 3.2; [16]).

Children

Cousins

References

[1]
E. Berlekamp, “Nonbinary BCH decoding (Abstr.)”, IEEE Transactions on Information Theory 14, 242 (1968). DOI
[2]
J. Massey, “Shift-register synthesis and BCH decoding”, IEEE Transactions on Information Theory 15, 122 (1969). DOI
[3]
E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, 1968
[4]
V. Guruswami and M. Sudan, “Improved decoding of Reed-Solomon and algebraic-geometric codes”, Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280). DOI
[5]
R. Koetter and A. Vardy, “Algebraic soft-decision decoding of reed-solomon codes”, IEEE Transactions on Information Theory 49, 2809 (2003). DOI
[6]
H. Dau et al., “Repairing Reed-Solomon Codes With Multiple Erasures”, IEEE Transactions on Information Theory 64, 6567 (2018). DOI; 1612.01361
[7]
R. J. McEliece, A public-key cryptosystem based on algebraic coding theory, Technical report, Jet Propulsion Lab. DSN Progress Report (1978).
[8]
H. Janwa and O. Moreno, “McEliece public key cryptosystems using algebraic-geometric codes”, Designs, Codes and Cryptography 8, (1996). DOI
[9]
H. Niederreiter (1986). Knapsack-type cryptosystems and algebraic coding theory. Problems of Control and Information Theory. Problemy Upravlenija I Teorii Informacii. 15: 159–166.
[10]
V. M. SIDELNIKOV and S. O. SHESTAKOV, “On insecurity of cryptosystems based on generalized Reed-Solomon codes”, Discrete Mathematics and Applications 2, (1992). DOI
[11]
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
[12]
Alain Couvreur et al., “Distinguisher-Based Attacks on Public-Key Cryptosystems Using Reed-Solomon Codes”. 1307.6458
[13]
Marco Baldi et al., “Enhanced public key security for the McEliece cryptosystem”. 1108.2462
[14]
W. C. Huffman, J.-L. Kim, and P. Solé, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021). DOI
[15]
M. A. Tsfasman and S. G. Vlăduţ, Algebraic-geometric Codes (Springer Netherlands, 1991). DOI
[16]
T. Høholdt, J.H. Van Lint, and R. Pellikaan, 1998. Algebraic geometry codes. Handbook of coding theory, 1 (Part 1), pp.871-961.
[17]
W. C. Huffman and V. Pless, Fundamentals of Error-correcting Codes (Cambridge University Press, 2003). DOI
[18]
T. Yaghoobian and I. F. Blake, “Hermitian codes as generalized Reed-Solomon codes”, Designs, Codes and Cryptography 2, 5 (1992). DOI
Page edit log

Zoo code information

Internal code ID: generalized_reed_solomon

Your contribution is welcome!

on github.com (edit & pull request)

edit on this site

Zoo Code ID: generalized_reed_solomon

Cite as:
“Generalized RS (GRS) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/generalized_reed_solomon
BibTeX:
@incollection{eczoo_generalized_reed_solomon, title={Generalized RS (GRS) code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/generalized_reed_solomon} }
Share via:
Twitter |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/generalized_reed_solomon

Cite as:

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

Github: https://github.com/errorcorrectionzoo/eczoo_data/tree/main/codes/classical/q-ary_digits/rs/generalized_reed_solomon.yml.