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

Alexander May · Ilya Ozerov

Eurocrypt 2015

Time bound

2^{0.114 n + o(n)}

Space bound

—

Source / version date

26 Apr 2015

Comparison variant

Binary · full GV distance

Cost scale

2^{c n + o(n)}

Code alphabet

𝔽₂

Rate convention

Maximize over 0≤R≤1

Error weight

Full GV distance: n H₂⁻¹(1−R)

Computation model

Classical random-code ISD analysis

reference

MO15

coefficient_source

https://link.springer.com/chapter/10.1007/978-3-662-46800-5_9

Assumptions and source notes

Rounded full-distance bound from the paper abstract. Date is the EUROCRYPT opening day; earlier disclosure is not established here.

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}
}