ECDLP / Binary fields · quantum resource bounds

Concrete quantum cryptanalysis of binary elliptic curves

Gustavo Banegas · Daniel J. Bernstein · Iggy van Hoof · Tanja Lange

TCHES 2021

PublishedSource checked

Time bound: 48n³ + 8n^log₂(3)+1 + 352n² log₂(n) + 512n² + O(n^log₂(3)) logical Toffoli gates
Space bound: 7n + floor(log₂ n) + 9 logical qubits

Source / version date: 19 Oct 2020
Comparison variant: Binary fields · quantum resource bounds
Cost scale: Expression only

Assumptions and source notes

Double-and-add scalar multiplication variant over F_{2^n}. The source also provides a fixed-window variant with a logarithmic factor improvement. These are logical resource bounds, not physical attack timings.

Source location

Abstract
Version: Version available at the cited URL; bibliographic metadata and stated bound checked on 2026-11-08

Primary source ↗

BibTeXDownload .bib

@misc{bbhl20,
  author = {Gustavo Banegas and Daniel J. Bernstein and Iggy van Hoof and Tanja Lange},
  title = {{Concrete quantum cryptanalysis of binary elliptic curves}},
  journal = {IACR Transactions on Cryptographic Hardware and Embedded Systems 2021(1)},
  year = {2021},
  url = {https://eprint.iacr.org/2020/1296},
  keywords = {quantum, elliptic curves, binary fields, logical resources},
  cr_date = {2020-10-19},
  cr_date_precision = {day},
  cr_status = {published},
  cr_venue = {IACR Transactions on Cryptographic Hardware and Embedded Systems 2021(1)},
  cr_author_ids = {gustavo-banegas; daniel-j-bernstein; iggy-van-hoof; tanja-lange}
}