An Efficient Decoding of Goppa Codes for the McEliece Cryptosystem

• Autorzy: Lim S. , Lee H.-S. , Choi M.

Identyfikatory

DOI

10.3233/FI-2014-1082

• Języki publikacji: EN

Abstrakty

EN

The McEliece cryptosystem is defined using a Goppa code, and decoding the Goppa code is a crucial step of its decryption. Patterson’s decoding algorithm is the best known algorithm for decoding Goppa codes. Currently, the most efficient implementation of Patterson’s algorithm uses a precomputation. In this paper, we modify Patterson’s decoding algorithm so that one can remove the precomputation part while sustaining the best efficiency. Precomputations yield additional storage requirement to store the precomputed value which increases as the security level increases in McEliece cryptosystem. In the original decoding algorithm of Patterson, computing square root in a quotient field of polynomial ring over a finite field is necessary. In our modification, the computations are involved only in the arithmetics of polynomial ring over a finite field, not in the quotient field. This achieves better efficiency because one can remove polynomial reductions in the computations of quotient field.

Słowa kluczowe

EN

McEliece cryptosystem; Goppa code; Patterson’s algorithm; square roots

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 133, nr 4
• Strony: 387--397
• Opis fizyczny: Bibliogr. 8 poz., tab.

Twórcy

autor

Lim S.

• Institute of Mathematical Sciences, Ewha Womans University Seodaemun-gu, 120-750, Seoul, South Korea

autor

Lee H.-S.

• Department of Mathematics, Ewha Womans University Seoul, South Korea

autor

Choi M.

• Department of Mathematics, Ewha Womans University Seoul, South Korea

Bibliografia

• [1] Barreto P. and Voloch J.: Efficient computation of roots in finite fields, Des. Codes Cryptography, 39 (2), 2006, pp.275–280
• [2] Bernstein D. , Buchmann J., Dahmen E. (Eds.): Post- Quantum Cryptography, Springer, 2009, pp. 95–141
• [3] Bernstein D., Lange T. and Peters C.: Attacking and defending McEliece cryptosystem, PQCrypto 2008, LNCS 5299, 2008, pp. 31–46
• [4] Craven D.: Computing with Magma, personal lecture notes of Trinity Term, 2008, http://people.maths.ox.ac.uk/craven/docs/lectures/magma.pdf
• [5] Goppa V.: A New Class of Linear Correcting Codes, Problems of Information Transmission, 6, 1970, pp. 207–212
• [6] Huber K.: Note on Decoding binary Goppa codes, Electronics Letters, 32, 1996, pp.102–103
• [7] McEliece R.: A public key cryptosystem based on algebraic coding theory, DSN progress report, 42-44, 1978, pp.114–116
• [8] Patterson N.: The algebraic decoding of Goppa codes, IEEE Transactions on Information Theory, IT-21 (2), 1975, pp.203–207