Cryptology ePrint Archive: Report 2016/237

May-Ozerov Algorithm for Nearest-Neighbor Problem over $\mathbb{F}_{q}$ and Its Application to Information Set Decoding

Shoichi Hirose

Abstract: 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 their algorithm generalized to work for vectors over the finite field $\mathbb{F}_{q}$ with arbitrary prime power $q$. We also apply the generalized algorithm to the decoding problem of random linear codes over $\mathbb{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 $\mathbb{F}_{q}$ with $q\geq 3$.

Category / Keywords: code-based cryptography, random linear code, information set decoding, nearest-neighbor problem

Original Publication (with minor differences): SECITC 2016

Date: received 3 Mar 2016, last revised 20 Jun 2016

Contact author: hrs_shch at u-fukui ac jp

Available format(s): PDF | BibTeX Citation

Version: 20160620:065247 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]