Quantum Simulation of Elliptic Curve Crytography Arithmetic
By Sophia, Luv
Introduction:
Our proposed research aims to explore the implementation of elliptic curve cryptography (ECC) arithmetic on quantum computers by developing quantum circuits for group operations across multiple elliptic curve models. Building on prior work that optimized affine Weierstrass addition formulas for Shor’s algorithm, we extend these approaches to alternative curve models, including Montgomery curves, Twisted Edwards curves, and curves defined over binary fields. Our main hypothesis is that while all these models yield functionally equivalent group laws, their quantum circuit cost, in terms of qubit width, depth, and $T$-gate count, will vary substantially. By systematically comparing models, we aim to identify which curve representations present the lowest-cost path for quantum cryptanalysis of ECC.
Intellectual Merit:
The intellectual merit of this project lies in broadening the resource estimates for quantum attacks on ECC beyond the standard Weierstrass form. While previous studies have primarily focused on affine Weierstrass coordinates over prime fields, classical cryptography routinely employs Montgomery and Edwards curves for their efficiency and complete addition laws. Moreover, binary fields $\mathbb{F}_{2^m}$ remain in use in certain standards, yet quantum resource estimates for these settings remain scarce. By constructing and analyzing reversible arithmetic circuits for these models, our work contributes new insight into the comparative security of different ECC families under quantum adversaries. The results will not only test the universality of previous findings but also advance the methodology for designing and evaluating quantum circuits for algebraic structures beyond integer modular arithmetic.
Broader Impact:
Evaluating quantum circuit costs across multiple elliptic curve models will provide the cryptography community with a clearer picture of which ECC variants are most vulnerable to quantum attacks, thereby guiding future cryptographic standardization and migration to post-quantum schemes. Beyond cryptography, our work develops reusable building blocks for reversible polynomial arithmetic (for binary fields) and modular inversion circuits, both of which can be leveraged in other domains of quantum simulation and number-theoretic algorithms.