Binary decoding / Binary · half distance

Decoding Linear Codes with High Error Rate and its Impact for LPN Security

Leif Both · Alexander May

PQCrypto 2018

PublishedSource checked

Time bound: 2^{0.0488 n + o(n)}
Space bound: 2^{0.029 n + o(n)}

Source / version date: 27 Nov 2017
Comparison variant: Binary · half distance
Cost scale: 2^{c n + o(n)}
depth: 2

Assumptions and source notes

Depth 2; Figure 6.

Source location

Theorem 3; Figure 6
Version: 2018-01-31

Primary source ↗

BibTeXDownload .bib

@misc{both-may2017-high-error,
  author = {Leif Both and Alexander May},
  title = {{Decoding Linear Codes with High Error Rate and its Impact for LPN Security}},
  year = {2018},
  url = {https://eprint.iacr.org/2017/1139},
  cr_date = {2017-11-27},
  cr_status = {published},
  cr_venue = {PQCrypto 2018},
  cr_author_ids = {leif-both; alexander-may}
}