Design and Optimization of Quantum Arithmetic Circuits for Binary Elliptic Curve Discrete Logarithms
Summary:
Works on quantum cryptanalysis have increased significantly in the past decades, particularly after Shor's algorithm rose to prominence due to its potential applicability in breaking legacy public-key cryptosystems, namely Rivest-Shamir-Adleman (RSA) and Elliptic Curve Cryptography (ECC). However, the variant of the algorithm for cracking ECC has been less extensively investigated compared to its counterpart for RSA, despite the verdict that elliptic curve-based cryptosystems are likely to be crackable earlier due to their shorter key length.
In this dissertation, we focus on exploring Shor's algorithm for solving elliptic curve discrete logarithms, the variant that forms the foundation of cracking ECC. Notably, we present the design, optimization, and resource analyses of quantum arithmetic circuits involved in the subroutines for binary elliptic curves. In detail, our contributions encompass three key aspects. Firstly, we presented a comprehensive literature review of Shor's algorithm for elliptic curve discrete logarithms, serving as an introduction to the topic before delving into our quantum arithmetic proposals.
Secondly, we propose a depth-optimized variant of the quantum inversion circuit, modifying the existing Fermat Little Theorem (FLT)-based inversion by translating its Itoh-Tsujii's quantum algorithm version to suit a lower-depth design, which results in a smaller number of CNOT gates and a slightly reduced T depth, hence contributing to a reduced overall depth and gate count than previous work. We also propose employing Gidney's relative-phase Toffoli gate (i.e., GRT gate) for the decomposition of our circuit, achieving a significantly lower T depth while further reducing the overall depth. This approach complements the more prevalent width-optimized strategies commonly proposed in the existing literature.
Thirdly, we present concrete designs of quantumpoint-doubling circuits, which, to the best of our knowledge, have never been found in the literature. In particular, we propose three different constructions to suit diverse design considerations: depth-optimized, ancilla-optimized, and balanced implementation, which show the need for one additional n-sized register compared to point addition for each round, along with their resource analyses in both Toffoli-level and T-level circuit decomposition. In addition, we also present the design of our integration between point doubling and point addition circuits, which can serve as a reference for obtaining a more complete resource estimation of Shor's algorithm for binary elliptic curve discrete logarithms.