For citation:
Ratseev S. M., Cherevatenko O. I. Decoding algorithms for Goppa codes with errors and erasures. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 2022, vol. 22, iss. 1, pp. 28-47. DOI: 10.18500/1816-9791-2022-22-1-28-47, EDN: SKXHVX
Decoding algorithms for Goppa codes with errors and erasures
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.
- 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 p. https://doi.org/10.6028/NIST.IR.8240
- Goppa V. D. A New Class of Linear Correcting Codes. Problems of Information Transmission, 1970, vol. 6, iss. 3, pp. 207–212.
- MacWilliams F. J., Sloane N. J. A. The Theory of Error Correcting Codes. Amsterdam, New York, North-Holland Pub. Co, 1977. 762 p. (Russ. ed.: Moscow, Sviaz’, 1979. 744 p.).
- Blahut R. E. Theory and Practice of Error Control Codes. Reading, Mass., Addison-Wesley Pub. Co., 1983. 500 p. (Russ. ed.: Moscow, Mir, 1986. 576 p.).
- Gao S. A new algorithm for decoding Reed—Solomon codes. In: V. Bhargava, H. V. Poor, V. Tarokh, S. Yoon, eds. Communications, Information and Network Security. Norwell, MA, Kluwer, 2003, vol. 712, pp. 55–68.
- Huffman W. C., Pless V. Fundamentals of Error-Correcting Codes. New York, Cambridge, Cambridge University Press, 2003. 646 p.
- Ratseev S. M. Elementy vysshei algebry i teorii kodirovaniya [Elements of Higher Algebra and Coding Theory]. St. Petersburg, Lan’, 2022. 656 p. (in Russian).
- Fedorenko S. V. Simple algorithm for decoding algebraic codes. Informatsionno-upravlyayushchie sistemy [Information and Control Systems], 2008, no. 3, pp. 23–27 (in Russian).
- Gohberg I., Olshevsky V. The fast generalized Parker–Traub algorithm for inversion of Vandermonde and related matrices. Journal of Complexity, 1997, vol. 13, iss. 2, pp. 208–234. https://doi.org/10.1006/jcom.1997.0442
- Yan S., Yang A. Explicit algorithm to the inverse of Vandermonde matrix. 2009 International Conference on Test and Measurement. Hong Kong, 2009, pp. 176–179. https://doi.org/10. 1109/ICTM.2009.5413083
- Rawashdeh E. A. A simple method for finding the inverse matrix of Vandermonde matrix. MATEMATICKI VESNIK, 2019, vol. 71, no. 3, pp. 207–213.
- Ratseev S. M., Cherevatenko O. I. On decoding algorithms for generalized Reed–Solomon codes with errors and erasures. Vestnik Samarskogo universiteta. Estestvennonauchnaia seriia [Vestnik of Samara University. Natural Science Series], 2020, vol. 26, no. 3, pp. 17–29 (in Russian). http://doi.org/10.18287/2541-7525-2020-26-3-17-29
- 2146 reads