Elliptic curve cryptographic challenges for benchmarking early fault-tolerant quantum computers

As we are transitioning from the NISQ era to the early fault-tolerant quantum computing era, it becomes imperative to benchmark the progress of the technology at performing tasks that are otherwise classically intractable. Despite the fact that there will be important societal consequences of enabling the ability to factor large numbers and compute discrete logarithms, the exact timeline of the development of those capabilities remains approximate and speculative. In this work, we take a first step at quantitatively characterizing the cryptanalytic capabilities of quantum computers in the next decade by developing sets of elliptic curve cryptographic challenges with a fine gradation in difficulty in order to provide accurate statistical signal of the progress of the quantum hardware. We define two approaches to constructing these challenges. In the first one, we modulate the difficulty by giving sets of hint bits of the solution for challenges on a 256-bit elliptic curve. In the second approach, we use the same curve equation over smaller primes to get a smaller group such that the Shor algorithm is easy to compile. The advantage of using elliptic curves for our challenges is that we can deploy our benchmarking platform on blockchains for a decentralized access to the results.