Geodesic
Decoding algorithms for Goppa codes with errors and erasures
Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 22 (2022) no. 1, pp. 28-47.

Voir la notice de l'article provenant de la source Math-Net.Ru

In 1978, McEliece built the first public key cryptosystem based on error-correcting codes. This cryptosystem based on Goppa codes is considered promising and cryptographically stable, taking into account quantum computing. At the same time, effective attacks on the secret keys of this cryptosystem have not yet been found. In the paper, algorithms for decoding Goppa codes in the case of errors and erasures are investigated. Four decoding algorithms based on the algorithms for Reed–Solomon codes proposed by Gao, Berlekamp and Massey, Sugiyama, and others are given. The first two algorithms are based on Gao algorithm and related to syndrome-free decoding algorithms, the rest are related to syndrome decoding algorithms. Moreover, any of these algorithms is also applicable for the case of a communication channel with errors only. Examples of decoding separable Goppa codes using these algorithms are also given. 
@article{ISU_2022_22_1_a2,
     author = {S. M. Ratseev and O. I. Cherevatenko},
     title = {Decoding algorithms for {Goppa} codes with errors and erasures},
     journal = {Izvestiya of Saratov University. Mathematics. Mechanics. Informatics},
     pages = {28--47},
     publisher = {mathdoc},
     volume = {22},
     number = {1},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ISU_2022_22_1_a2/}
}
TY  - JOUR
AU  - S. M. Ratseev
AU  - O. I. Cherevatenko
TI  - Decoding algorithms for Goppa codes with errors and erasures
JO  - Izvestiya of Saratov University. Mathematics. Mechanics. Informatics
PY  - 2022
SP  - 28
EP  - 47
VL  - 22
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ISU_2022_22_1_a2/
LA  - ru
ID  - ISU_2022_22_1_a2
ER  - 
%0 Journal Article
%A S. M. Ratseev
%A O. I. Cherevatenko
%T Decoding algorithms for Goppa codes with errors and erasures
%J Izvestiya of Saratov University. Mathematics. Mechanics. Informatics
%D 2022
%P 28-47
%V 22
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ISU_2022_22_1_a2/
%G ru
%F ISU_2022_22_1_a2
S. M. Ratseev; O. I. Cherevatenko. Decoding algorithms for Goppa codes with errors and erasures. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 22 (2022) no. 1, pp. 28-47. http://geodesic.mathdoc.fr/item/ISU_2022_22_1_a2/

[1] Status Report on the First Round of the NIST Post-Quantum Cryptography Standardization Process. National Institute of Standards and Technology. Internal Report 8240, January 2019, 27 pp. | DOI

[2] Goppa V. D., “A New Class of Linear Correcting Codes”, Problems of Information Transmission, 6:3 (1970), 207–212 | MR | Zbl

[3] MacWilliams F. J., Sloane N. J. A., The Theory of Error Correcting Codes, North-Holland Pub. Co, Amsterdam–New York, 1977, 762 pp. | MR | Zbl

[4] Blahut R. E., Theory and Practice of Error Control Codes, Addison-Wesley Pub. Co, Reading, Mass., 1983, 500 pp. | MR | MR | Zbl

[5] Gao S., “A new algorithm for decoding Reed–Solomon codes”, Communications, Information and Network Security, 712, eds. V. Bhargava, H. V. Poor, V. Tarokh, S. Yoon, Kluwer, Norwell, MA, 2003, 55–68 | DOI

[6] Huffman W. C., Pless V., Fundamentals of Error-Correcting Codes, Cambridge University Press, New York–Cambridge, 2003, 646 pp. | MR | Zbl

[7] Ratseev S. M., Elements of Higher Algebra and Coding Theory, Lan', St. Petersburg, 2022, 656 pp. (in Russian)

[8] Fedorenko S. V., “Simple algorithm for decoding algebraic codes”, Information and Control Systems, 2008, no. 3, 23–27 (in Russian)

[9] Gohberg I., Olshevsky V., “The fast generalized Parker–Traub algorithm for inversion of Vandermonde and related matrices”, Journal of Complexity, 13:2 (1997), 208–234 | DOI | MR | Zbl

[10] Yan S., Yang A., “Explicit algorithm to the inverse of Vandermonde matrix”, 2009 International Conference on Test and Measurement (Hong Kong, 2009), 176–179 | DOI

[11] Rawashdeh E. A., “A simple method for finding the inverse matrix of Vandermonde matrix”, MATEMATIC̆KI VESNIK, 71:3 (2019), 207–213 | MR | Zbl

[12] Ratseev S. M., Cherevatenko O. I., “On decoding algorithms for generalized Reed–Solomon codes with errors and erasures”, Vestnik of Samara University. Natural Science Series, 26:3 (2020), 17–29 (in Russian) | DOI | MR