按年被提到
20172018 · 1 次2026
物理与量子›量子计算·arXiv:1706.06752 · quant-ph

Quantum resource estimates for computing elliptic curve discrete logarithms

Martin Roetteler, Michael Naehrig, Krysta M. Svore, Kristin Lauter · 2017
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 2 人首次 2018-06-29 · 最近 2026-03-24
2不同的人
2活跃月份
2讨论串
226被引(OpenAlex)
arXiv 摘要(候选层不写导读)

We give precise quantum resource estimates for Shor's algorithm to compute discrete logarithms on elliptic curves over prime fields. The estimates are derived from a simulation of a Toffoli gate network for controlled elliptic curve point addition, implemented within the framework of the quantum computing software tool suite LIQ$Ui|\rangle$. We determine circuit implementations for reversible modular arithmetic, including modular addition, multiplication and inversion, as well as reversible elliptic curve point addition. We conclude that elliptic curve discrete logarithms on an elliptic curve defined over an $n$-bit prime field can be computed on a quantum computer with at most $9n + 2\lceil\log_2(n)\rceil+10$ qubits using a quantum circuit of at most $448 n^3 \log_2(n) + 4090 n^3$ Toffoli gates. We are able to classically simulate the Toffoli networks corresponding to the controlled elliptic curve point addition as the core piece of Shor's algorithm for the NIST standard curves P-192, P-224, P-256, P-384 and P-521. Our approach allows gate-level comparisons to recent resource estimates for Shor's factoring algorithm. The results also support estimates given earlier by Proos and Zalka and indicate that, for current parameters at comparable classical security levels, the number of qubits required to tackle elliptic curves is less than for attacking RSA, suggesting that indeed ECC is an easier target than RSA.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
评论Strilanc · 2018-06

“Even if the number of qubits doubled every year from here on out, it would be 15+ years until we had enough working space to run Shor's algorithm on modern cryptographic key sizes. Back of the envelope: - It takes 9n error-corrected qubits to break an n-bit ECDH key [1] - Each error-corrected qubit requires ~2500 physical qubits [2][3] - Typical ECDH …”

I'm Scott Aaronson, quantum computing/computational complexity researcher. AMA原评论 ↗
评论bob1029 · 2026-03

“> ECC algorithms with smaller key sizes would be more vulnerable to a quantum attack, as it would require a currently theoretical quantum computer with fewer qubits than would be required for an RSA key with the same cryptographic strength [25]. This is what keeps me skeptical about ECC. RSA is really chunky, and maybe that's a fundamental advantage from…”

Secure Domain Name System (DNS) Deployment 2026 Guide [pdf]原评论 ↗