IACR News item: 03 March 2016
Shoichi Hirose
ePrint Report
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$.
Additional news items may be found on the IACR news page.