The May-Ozerov Algorithm for Syndrome Decoding is “Galactic”

In 2015, May and Ozerov proposed a new method to solve the Nearest Neighbor Problem. They also observed that it could be used as a subroutine in various Information Set Decoding (ISD) algorithms for arbitrary linear codes. This led to an asymptotic improvement in their complexity. However, the proposed improvement has been widely perceived as impractical because of the huge hidden factors in its asymptotic complexity. The main contribution of this article is to provide a sound foundation for this claim. We show that it is indeed “galactic”, namely that it only improves upon much simpler methods when instances are so large that they fill the whole universe. More precisely, we argue that for the May-Ozerov ISD algorithm to require less operations than a technique based on the Stern ISD algorithm, the length of the code has to be greater than 1,874,400 with a number of operation beyond 2 to the power 63489, making it practically useless.