Generalization of BJMM-ISD Using May-Ozerov Nearest Neighbor Algorithm over an Arbitrary Finite Field F_q

摘要

The security of McEliece cryptosystem heavily relies on the hardness of decoding a random linear code. The best known generic decoding algorithms are derived from the Information-Set Decoding (ISD) algorithm. The ISD algorithm was proposed in 1962 by Prange and improved in 1989 by Stern and later in 1991 by Burner. Since then, there have been numerous works improving and generalizing the ISD algorithm: Peters in 2009, May, Meurer and Thomae in 2011, Becker, Joux, May and Meurer in 2012, May and Ozerov in 2015, and Hirose in 2016. Among all these improvement and generalization only those of Peters and Hirose are over F_q with q an arbitrary prime power. In Hirose's paper, he describes the May-Ozerov nearest-neighbor algorithm generalized to work for vectors over the finite field F_q with arbitrary prime power q. He also applies the generalized algorithm to the decoding problem of random linear codes over F_q. And he observed by a numerical analysis of asymptotic time complexity that the May-Ozerov nearest-neighbor algorithm may not contribute to the performance improvement of Stern's ISD algorithm over F_q with q ≥ 3. In this paper, we will extend the Becker, Joux, May, and Meurer's ISD using the May-Ozerov algorithm for Nearest-Neighbor problem over F_q with q an arbitrary prime power. We analyze the impact of May-Ozerov algorithm for Nearest-Neighbor Problem over F_q on the Becker, Joux, May and Meurer's ISD.