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.
The availability of large-scale quantum computers would enable the efficient solution of some computational problems that are assumed to be infeasible on current computer architectures. A subject area where the potential of quantum computing is particulary high is cryptanalysis: some of the most prominent encryption and digital signature schemes are vulnerable to attacks based on quantum algorithms. In particular, the so-called discrete logarithm problem can be solved efficiently on a quantum computer, and the computational intractibility of this problem (in suitable algebraic structures) forms, e.g., the foundation of popular digital signature schemes. It turns out that the practical implementation of quantum algorithms is a formidable experimental challenge, however, and with the current state-of-the-art quantum computers do not pose an imminent threat to established cryptographic schemes. To understand the practical potential of quantum attacks when more complex quantum computations become feasible, it is necessary to understand the implementation details of quantum algorithms. To this aim, the details of a quantum algorithm can be expressed as a quantum circuit. Focusing on small-scale quantum systems, this project set out to optimize such quantum circuits for solving certain types of discrete logarithm problems. In mathematical terms, the results achieved in the project support the efficient solution of discrete logarithm problems on binary elliptic curves. Binary elliptic curves are well-suited for efficient hardware implementation and a popular choice for implementing digital signature algorithms. The results achieved in this project help to reduce the number of so-called T-gates. These are needed to implement the pertinent algebraic operations. T-gates can be seen as an elementary operation in quantum computing whose implementation cost is particularly high---substantially higher than for other elementary operations. As a secondary goal, quantum circuits identified in this project were optimized for T-depth. This can be interpreted as reducing the number of costly steps needed for performing computations. Integrating classical techniques for efficient arithmetic in the design of quantum circuits was central for the approach taken in this project. It turns out that classical optimization criteria do not seem to be a perfect fit for optimizing quantum circuits. Notwithstanding this observation, the quantum circuits identified in the project demonstrate that classical techniques can enable substantial savings in the implementation cost of a cryptanalytic attack based on quantum computing. To make optimal use of quantum resources, further research along this line certainly appears to be worthwhile.
