Generalized Reed-Solomon (GRS) code

Generalized Reed-Solomon (GRS) code[1]

Description

Stub.

Realizations

Various cloud storage systems [2].Public-key cryptosystems [3]. Initial construction of McEliece Public Key Cryptosystem was based on Goppa codes which are subfield subcode of GRS codes. Public Key Cryptosystem designs based on GRS codes first proposed in Ref. [4], which replaced the generator matrix with the parity check matrix, were proven to be insecure [5] since the public key exposes algebraic structure of code. More recent works focus on methods to mask the algebraic structure using subcodes of GRS codes [3]. Lately a key-recovery attack was developed in [6] for a variant of masking method proposed by [7].

Parents

Alternant code
Evaluation AG code — GRS codes are evaluation AG codes on the projetive line; see Thm. 15.3.24 of Ref. [8].
Distributed-storage code — GRS codes are used in various cloud storage systems [2].

Children

Bose–Chaudhuri–Hocquenghem (BCH) code — BCH codes are subfield subcodes of GRS codes.
Goppa code — Goppa codes are subfield subcodes of GRS codes.
Reed-Solomon (RS) code

Cousin

Quantum maximum-distance-separable (MDS) code — Quantum MDS codes can be constructed through classical generalized Reed-Solomon codes [9].

References

[1]: F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977
[2]: H. Dau et al., “Repairing Reed-Solomon Codes With Multiple Erasures”, IEEE Transactions on Information Theory 64, 6567 (2018). DOI; 1612.01361
[3]: 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
[4]: L. Socha, “Some remarks about open-loop control in stochastic quasilinear systems”, Optimal Control Applications and Methods 7, 105 (1986). DOI
[5]: V. M. SIDELNIKOV and S. O. SHESTAKOV, “On insecurity of cryptosystems based on generalized Reed-Solomon codes”, Discrete Mathematics and Applications 2, (1992). DOI
[6]: Alain Couvreur et al., “Distinguisher-Based Attacks on Public-Key Cryptosystems Using Reed-Solomon Codes”. 1307.6458
[7]: Marco Baldi et al., “Enhanced public key security for the McEliece cryptosystem”. 1108.2462
[8]: W. C. Huffman, J.-L. Kim, and P. Solé, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021). DOI
[9]: Hualu Liu and Xiusheng Liu, “Constructions of quantum MDS codes”. 2002.06040

Cite as:

“Generalized Reed-Solomon (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/generalized_reed_solomon.yml.