On Computing Nearest Neighbors with Applications to Decoding of Binary Linear Codes

Alexander May · Ilya Ozerov

Eurocrypt 2015

Time bound

2^{0.0473 n + o(n)}

Space bound

—

Source / version date

26 Apr 2015

Comparison variant

Binary · half distance

Cost scale

2^{c n + o(n)}

Field

𝔽₂

Code rate convention

Worst rate in the half-distance convention

Error-weight regime

Half the GV distance

Cost model

Asymptotic nearest-neighbor ISD

reference

MO15

Assumptions and source notes

EUROCRYPT 2015. Source gives 0.0473 in the half (bounded) distance setting. Historical reference, not a claim that all later ISD improvements have been included. Date denotes EUROCRYPT 2015 opening day, not a verified first preprint date.

Primary source ↗

@misc{paper-bb2a5c84c79d,
  author = {Alexander May and Ilya Ozerov},
  title = {{On Computing Nearest Neighbors with Applications to Decoding of Binary Linear Codes}},
  year = {2015},
  url = {https://www.iacr.org/archive/eurocrypt2015/90560136/90560136.pdf},
  cr_date = {2015-04-26},
  cr_status = {published},
  cr_author_ids = {alexander-may; ilya-ozerov},
  howpublished = {EUROCRYPT 2015}
}