Affiliations: Institute of Mathematical Sciences, Ewha Womans University, Seodaemun-gu, 120-750, Seoul, South Korea. seongannym@ewha.ac.kr | Department of Mathematics, Ewha Womans University, Seoul, South Korea. hsl@ewha.ac.kr
Note: [] This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Science, ICT and Future Planning (Grant Number: 2012R1A2A1A03006706). Address for correspondence: Seongan Lim, Institute of Mathematical Sciences, Ewha Womans University, 52 Ewhayeodae-gil Seodaemun-gu, Seoul 120-750, South Korea
Note: [] This research was supported by Basic Science Research Programs through the National Research Foundation of Korea (NRF) funded by the Ministry of Science, ICT and Future Planning (Grant Number: 2012R1A2A1A03006706) and funded by the Ministry of Education (Grant Number 2009-0093827).
Abstract: 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.
