Elliptic-curve discrete logarithms
Compute discrete logarithms in elliptic-curve groups; distinguish ordinary cryptographic curves from anomalous or other exceptional families.
Binary fields · quantum resource bounds
Logical Toffoli count and logical qubits; scalar-multiplication variant specified
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| — | Concrete quantum cryptanalysis of binary elliptic curvesTCHES 2021SourceBibTeX / detailslogical Toffoli gates logical qubits double-and-add | 19 Oct 2020 | 48n3 + 8nlog₂(3)+1 + 352n² log₂(n) + 512n² + O(nlog₂(3)) logical Toffoli gates | 7n + floor(log₂ n) + 9 logical qubits | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Logical Toffoli count and logical qubits; scalar-multiplication variant specified
- Computation
- Quantum
- Rigor
- Provable circuit analysis
- Instances
- elliptic curves over F_{2^n}
- Cost scale
- Expression only
- Parameter
- n
- Description
- Quantum ECDLP over binary fields. These formulas should not be ranked directly against prime-field circuits.
- Comparison rules
- Quantum ECDLP over binary fields. These formulas should not be ranked directly against prime-field circuits. Only compare entries with this cost scale, input domain and computational model. Polynomial and quasi-polynomial expressions without an extracted scalar are not ranked.
- Tags
- binary fields, quantum, logical resources