Paper 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$.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Minor revision. SECITC 2016
Keywords
code-based cryptographyrandom linear codeinformation set decodingnearest-neighbor problem
Contact author(s)
hrs_shch @ u-fukui ac jp
History
2016-06-20: revised
2016-03-03: received
See all versions
Short URL
https://ia.cr/2016/237
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/237,
      author = {Shoichi Hirose},
      title = {May-Ozerov Algorithm for Nearest-Neighbor Problem over $\mathbb{F}_{q}$ and Its Application to Information Set Decoding},
      howpublished = {Cryptology ePrint Archive, Paper 2016/237},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/237}},
      url = {https://eprint.iacr.org/2016/237}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.