EAGER: Small-Scale Quantum Circuits with Applications in Cryptanalysis

Florida Atlantic University, Boca Raton FL

Investigators

Abstract

One of the central algorithmic problems in public key cryptography is the so-called discrete logarithm problem for elliptic curves; the assumed hardness of this problem lies at the heart of major cryptographic schemes. While no efficient (polynomial time) solution on classical hardware is known, for quantum computers an efficient algorithm to compute discrete logarithms is available. In view of the notorious hardness of controlling large-scale quantum systems, the availability of an efficient "quantum attack" does not seem to pose an immediate cryptanalytic threat, but it remains difficult to predict what is feasible to implement within a few years. Especially for cryptographic schemes requiring extreme parameter choices, like implementations on low-cost devices, it would be desirable to have a better understanding of the potential of attacks relying on quantum circuits. Quantum circuits involving just a few qubits are the most likely to be available in the short-term, and this project explores the cryptanalytic use of such circuits, the main focus being on the discrete logarithm problem for elliptic curves. Some years ago a new representation of elliptic curves has been identified, and this led to interesting algorithmic improvements for classical architectures. For quantum computers one may hope that this new representation enables relevant implementation improvements as well. Looking at algorithmic questions in the context of elliptic curves, one has to deal with computations in another algebraic structure: finite fields. Accordingly, this project also explores quantum cicuits for finite fields with cryptanalytic significance. It is planned that small-scale quantum circuits that are identified in this project will be made available through a web site, providing a collection of candidate algorithms for experiments in quantum computing.