Elliptic Curve Arithmetic for Quantum Cryptanalysis: A Study of Curve25519

What it is

Luo and Costello (ePrint 2026/2688, received 30 October 2026, approved 4 November 2026) estimate a quantum scalar multiplication circuit for Curve25519. It uses 47,199,530 CCX gates and 1,189 peak logical qubits. The page is an abstract only, so the circuit design is not described beyond the three contributions below.

How it works

The authors split the gain into three parts.

1. They apply established affine arithmetic and signed half-table techniques to Curve25519. In a comparison using the same arithmetic framework and signed half tables, Curve25519's field and subgroup parameters, together with the chosen GCD iteration budgets, save 2,218,944 CCX gates relative to secp256k1. That is about 4.7% of the 47.2 million total, so most of the headline 35% and 18% gap against Schrottenloher's circuits comes from the shared framework and tables, not from the curve itself.
2. Odd signed digit recoding is adapted to quantum windows using fixed output translations. It saves a further 15,204 CCX gates, and the abstract says it also applies to prime order curves.
3. Nonzero digits are combined with a fixed 8-torsion offset point, which keeps the accumulator outside the lookup points' subgroup. With zero slope support and exact field arithmetic, this gives an exception-free addition schedule and nonzero denominators during slope uncomputation. It needs no extra quantum point additions.

Preconditions / Affected

The 8-torsion offset relies on Curve25519 being a composite order curve. The recoding technique is the part the abstract says carries over to prime order curves.

Caveats

• The counts cover the full scalar schedule, lookup and cleanup.
• The implementation uses truncated arithmetic and heuristic GCD budgets.
• The counts exclude Fourier rotation synthesis and classical recovery.
• The page gives no wall-clock time, no physical qubit count and no error-correction assumptions.