How Well Can Today’s Quantum Computers Solve Elliptic-curve Cryptography?

Abstract

Ever since Peter Shor discovered an algorithm to solve discrete logarithm problems in 1994, it is widely known that quantum computers will play a significant role in the future of cryptography. An adaptation of this algorithm can also be applied to elliptic-curves, hence weakening the believed strength of elliptic-curve cryptography. In this thesis Shor’s quantum algorithm for the elliptic-curve discrete logarithm problem (ECDLP) is executed and its resource scaling is examined. The mathematical, quantum computing and information theoretical backgrounds are presented and the feasibility of the quantum algorithm on today’s quantum computing hardware is reviewed. Problems in these areas, especially of cryptographic nature, pose an important step towards connecting computer science, quantum computing, physics and mathematics to develop practical algorithms advocating quantum advantage.

1994 entdeckte Peter Shor ein Quantenalgorithmus zur Lösung von ganzzahligen Faktorisierungsprobleme und diskrete Logarithmen. Es ist seitdem generell bekannt, dass Quantenrechner eine besondere Rolle für die Zukunft der Kryptographie spielen werden. Insbesondere existiert eine Adaption des Quantenalgorithmus, welches auf diskrete Logarithmen über elliptische Kurven verwendet werden kann. Hierdurch wird die kryptographische Resistenz von Elliptischer-Kurven-Kryptographie verringert. In dieser Bachelorarbeit wird Shor’s Algorithmus für elliptische Kurven ausgeführt und die dafür benötigten Ressourcen analysiert. Die mathematischen, informatisch-theoretischen und physikalischen Hintergründe werden präsentiert und die Verwendbarkeit des Quantenalgorithmus wird in Bezug auf die Hardware, die uns heute zur Verfügung steht, in Betracht gezogen. Probleme dieser Art, insbesondere kryptographischer Natur, sind äußerst entscheidend, um Informatik, Physik und Mathematik im Bereich Quantencomputing zu verbinden und letztlich praktische Algorithmen auf Quantenrechnern zu entwickeln.