An implementation of Shor's algorithm for elliptic curve cryptography

Abstract

Elliptische-Kurven-Kryptografie, so wie es vom Signal Protokoll (Whatsapp), Bitcoin und Ethereum verwendet wird, basiert auf der angenommenen Schwierigkeit des Diskreten Logarithmus-Problems (DLP). Um das DLP mittels bekannter Algorithmen auf klassischen Computern zu lösen, wird zwar exponentielle Zeit benötigt, mit Quantencomputer kann es allerdings in polynomieller Zeit gelöst werden. Dies ist möglich mit Shors Algorithmus, welcher im Wesentlichen aus der Quantum Phase Estimation und Quantum Fourier Transformationen besteht. Zusammen mit Quantengattern für gewöhnliche Arithmetik, Montgomery modularer Arithmetik und Punktaddition kann der Algorithmus verwendet werden, um aus öffentlichen Schlüsseln den dazugehörigen privaten Schlüssel in polynomieller Zeit zu errechnen. Der Algorithmus wurde im Zuge der Arbeit in Python implementiert und bereits für kleine Schlüssel simuliert. Derzeit besitzen Quantencomputer nicht die benötigten Ressourcen, um Shors Algorithmus für bedeutsame Schlüsselgrößen auszuführen. In der Zukunft wird es aber Quantencomputer mit genügend vielen Qubits und der benötigten Dekohärenzzeit geben, um Elliptische-Kurven-Kryptografie unsicher zu machen. Die genaue Implementierung des Algorithmus und die Zusammensetzung der verschiedenen Gatter sind immer noch Teil von aktueller Forschung. Dadurch ist es denkbar, dass noch effizientere Quantenschaltkreise für die Quantengatter gefunden werden. Dies hat zur Folge, dass Elliptische-Kurven-Kryptografie noch früher keine ausreichende Sicherheit mehr bieten kann.

Elliptic curve cryptography, as used by the Signal protocol (Whatsapp), Bitcoin, and Ethereum, relies on the assumed computational hardness of the discrete logarithm problem (DLP). While the DLP for elliptic curves requires exponential time to be solved using known algorithms on classical computers, quantum computers require only polynomial time. This is possible using Shor's algorithm, essentially consisting of the quantum phase estimation and quantum Fourier transformations. Together with quantum gates for regular arithmetic, Montgomery modular arithmetic, and point addition, the algorithm can be used to derive elliptic curve private keys from their corresponding public keys in polynomial time. For this thesis, the algorithm has been implemented in Python and simulated for small keys. Currently, quantum computers are not powerful enough to actually execute Shor's algorithm for significant key sizes. In the future, they will have enough qubits and the required decoherence time to make elliptic curve cryptography insecure. The details of the algorithm and different gate decompositions are still subject of recent research. It is therefore likely that more efficient circuits for different gates will be found. As a consequence, elliptic curve cryptography will not provide the required security even sooner.