May-Ozerov Algorithm for Nearest-Neighbor Problem over F_q and Its Application to Information Set Decoding

摘要

May and Ozerov proposed an algorithm for the nearest-neighbor problem of vectors over the binary field at EUROCRYPT 2015. They applied their algorithm to the decoding problem of random linear codes over the binary field and confirmed the performance improvement. We describe a generalization of their algorithm for vectors over the finite field F_q with arbitrary prime power q. We also apply the generalized algorithm to the decoding problem of random linear codes over F_q. It is observed by our numerical analysis of asymptotic time complexity that the May-Ozerov nearest-neighbor algorithm may not contribute to the performance improvement of the Stern information set decoding over F_q with q ≥ 3.