Shor's discrete logarithm quantum algorithm for elliptic curves

By John Proos, Christof Zalka. Quantum information & computation, 2003

391 citations recorded by the source corpus.

We show in some detail how to implement Shor's efficient quantum algorithm for discrete logarithms for the particular case of elliptic curve groups. It turns out that for this problem a smaller quantum computer can solve problems further beyond current computing than for integer factorisation. A 160 bit elliptic curve cryptographic key could be broken on a quantum computer using around 1000 qubits while factoring the security-wise equivalent 1024 bit RSA modulus would require about 2000 qubits. In this paper we only consider elliptic curves over GF(p) and not yet the equally important ones over GF(2n) or other finite fields. The main technical difficulty is to implement Euclid's gcd algorithm to compute multiplicative inverses modulo p. As the runtime of Euclid's algorithm depends on the input, one difficulty encountered is the "quantum halting problem".

Subfields: Artificial Intelligence, Information Systems

View Paper: https://www.semanticscholar.org/paper/2b6b49fd0794db647d0dbf65e7dd4d5795b4a1e9

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Information Systems

Citations in the corpus

Frodo: Take off the Ring! Practical, Quantum-Secure Key Exchange from LWE (2016, background): “prime p and elliptic curve groups) are vulnerable to polynomial-time quantum attacks [60, 56].”
The Impact of Quantum Computing on Present Cryptography (2018, background): “Furthermore, Proos and Zalka [19] explained that 160-bit elliptic curves could be broken by a 1000-qubit quantum computer, while factorizing 1024-bit RSA would require a 2000-qubit quantum computer.”
Guide to Elliptic Curve Cryptography (2004, methodology): “Acknowledgements We gratefully acknowledge the following people who provided valuable comments and advice: Mike Brown, Eric Fung, John Goyo, Rick Hite, Rob Lambert, Laurie Law, James Muir, Arash Reyhani-Masoleh, Paul Schellenberg, Adrian Tang, Edlyn Teske, and Christof Zalka.”
Towards Post-Quantum Blockchain: A Review on Blockchain Cryptography Resistant to Quantum Computing Attacks (2020, background): “However, researchers have determined that 160-bit elliptic curves can be broken with a 1000-qubit quantum computer, while 1024-bit RSA would need roughly 2,000 qubits [33].”
Curve25519: New Diffie-Hellman Speed Records (2006, background): “See [56] for details of a general elliptic-curve-discrete-logarithm algorithm.”
Quantum algorithms: an overview (2015, neutral): “Elliptic curve discrete log Elliptic curve Polynomial [76] ECDH, ECDSA, .”