On the Design and Optimization of a Quantum Polynomial-Time Attack on Elliptic Curve Cryptography

Abstract

We consider a quantum polynomial-time algorithm which solves the discrete logarithm problem for points on elliptic curves over $GF(2^m)$. We improve over earlier algorithms by constructing an efficient circuit for multiplying elements of binary finite fields and by representing elliptic curve points using a technique based on projective coordinates. The depth of our proposed implementation, executable in the Linear Nearest Neighbor (LNN) architecture, is $O(m^2)$, which is an improvement over the previous bound of $O(m^3)$ derived assuming no architectural restrictions.

12 pages, 3 figures: Extended from version submitted to TQC 2008, with corrections

References in corpus (5)

• Fast Quantum Modular Exponentiation
• Linear Depth Stabilizer and Quantum Fourier Transformation Circuits with no Auxiliary Qubits in Finite Neighbor Quantum Architectures
• Shor's algorithm on a nearest-neighbor machine
• Quantum Arithmetic on Galois Fields
• Optimized quantum implementation of elliptic curve arithmetic over binary fields

Cited by in corpus (2)

• Toward the first quantum simulation with quantum speedup
• Applying Grover's algorithm to AES: quantum resource estimates