Grover vs. McEliece

Daniel J. Bernstein

Post-Quantum Cryptography 2010

Time bound

2^{0.06035 n + o(n)}

Space bound

—

Source / version date

23 Nov 2009

Comparison variant

Quantum · 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

Quantum Grover search of information sets

access

Polynomial-size decoding circuit; no exponential lookup table

reference

Bernstein10

coefficient_source

https://arxiv.org/pdf/1703.00263

Assumptions and source notes

Prange with Grover search. The five-digit full-GV specialization is tabulated in Kachigar–Tillich 2017. Date is the author-listed original manuscript date.

Primary source ↗

@inproceedings{paper-1121d4329e21,
  author = {Daniel J. Bernstein},
  title = {{Grover vs. McEliece}},
  booktitle = {Post-Quantum Cryptography 2010},
  year = {2010},
  volume = {6061},
  pages = {73--80},
  publisher = {Springer},
  doi = {10.1007/978-3-642-12929-2_6},
  url = {https://cr.yp.to/papers.html#grovercode},
  cr_date = {2009-11-23},
  cr_status = {published},
  cr_venue = {Post-Quantum Cryptography 2010},
  cr_author_ids = {daniel-j-bernstein},
  series = {Lecture Notes in Computer Science}
}