A More Efficient Method for Breaking Elliptic Curve Cryptography (ECC) Using a Fault Tolerant Quantum Computer
Cracking cryptographic protocols is a well-known impact area for fault-tolerant quantum computing. Clearly it is important to estimate just when quantum computers will impact cryptography. However, this is a technically challenging task, involving careful evaluation of the resources needed by quantum algorithms in light of numerous architectural and hardware specific considerations.
In a new publication we estimated the scale of quantum computers needed to break a commonly-used cryptosystem, considering a novel fault-tolerant quantum computing architecture we recently introduced. This active-volume architecture leverages the unique non-local connections available from photonic components to substantially reduce costs in the kind of quantum arithmetic needed in cryptographic applications.
Codebreaking with quantum computers
Secure digital communications, which underpin our modern use of the internet, rest on the success of public-key cryptographic systems. These cryptographic systems work by allowing a user to provide a public key, with which anyone can securely encode messages to them. These messages can then only be decoded with a secret private key held by the user. These keys for encoding and decoding are built from mathematical operations which are easy to apply (for the encoding), but hard to reverse (for the decoding). The difficulty of the decoding relies on the fact that reversing these mathematical operations is an impractically time consuming task for conventional computers.
Two prominent such schemes are RSA and elliptic curve cryptography (ECC). In RSA, the mathematical operation used to provide the public and private key strategy centers around the ease of multiplying two prime numbers, compared with the difficulty of the inverse process - recovering these prime factors only given the resulting large number. The mathematical approach taken by ECC is a little more obscure, but the concept is similar. Public key encoding can be performed using a mathematical operation known as elliptic curve point multiplication, and reversing this process to decode the messages is hard without information contained in a private key.
In both RSA and ECC, larger key sizes increase the difficulty faced by a malicious interloper trying to decode messages without the private key. In RSA, a larger key size means needing to find prime factors of bigger numbers, while ECC presents greater challenges in breaking larger elliptic curve keys. Determining an acceptable key size is a crucial consideration – too small and the system might be vulnerable, too large and encoded messages can become unwieldy. Because of the mathematical complexity of ECC, the National Institute for Standards and Technology advises using ECC keys only 256 bits long, compared to the 2048-bit keys they recommend when using RSA.
Both RSA and ECC keys are susceptible to being broken by quantum computers. Algorithms have been discovered for quantum computers that can, unlike conventional computers, efficiently reverse the mathematical operations at the heart of RSA and ECC. Surprisingly, although it involves more mathematically complex operations, breaking 256-bit ECC keys is easier than breaking 2048-bit RSA keys thanks to the shorter keys needing fewer resource-intensive arithmetic operations.
Universal tricks
We suspected that our active volume architecture would be well suited to give huge speedups in quantum algorithms for cracking ECC. But first we looked at whether we could find any architecture-independent improvements to existing ECC quantum algorithms. Surprisingly we found that a few small adjustments to the state of the art can significantly reduce the number of gates required for breaking ECC by up to 80%. This saving was primarily based on two small modifications:
1) Quantum algorithms for cracking ECC involve two steps. The first step is a preparatory phase, with details that are independent of the specific ECC public key that needs to be broken. The second step then generates the secret private key that can allow encoded messages to be read. We observe that by reusing the prepared state from the first half, it is possible to generate multiple private keys without the need to repeat the first preparatory step. This results in up to a 50% reduction in the number of quantum operations needed per key.
2) The cost of the algorithm is dominated by an arithmetic operation known as the modular multiplicative inverse (1). A known trick in the literature essentially allows us to essentially perform two or more of these inversions for the price of one2. Applying this technique provides an additional cost reduction of up to 60% per key cracked by the quantum algorithm.
Active volume alchemy
We also conducted resource estimates for implementing quantum algorithms for ECC within our active volume architecture.
Typically, the two resources which determine the cost of a fault-tolerant quantum algorithm are the required number of logical qubits and elementary Toffoli gates (the most expensive gate needed for fault-tolerant quantum computing). However, with active volume architectures, we need to take a slightly different perspective on resources. Instead of counting elementary gates, we deconstruct algorithms into larger subroutines, such as arithmetic operations, or the generation of lookup tables. Each subroutine carries an associated cost, enabling us to determine the overall cost of the algorithm.
Our results demonstrate the significant advantage that the ECC algorithm gains from the non-local connections leveraged in active volume architectures. Their presence leads to a remarkable reduction in the number of quantum operations need to crack an ECC key by a factor ranging between 300-700
(depending on details of the quantum computer we have available). Moreover, the cost per key is also substantially lower by a factor of 100-300 compared to the estimated cost for RSA-2048 keys which we discussed in a previous paper (3) on active-volume architectures (read more).
So, are all our secrets at immediate risk of being stolen? Not yet. Despite our breakthroughs, cracking 256-bit ECC keys still requires a quantum computer having millions of physical qubits. Even though photonic quantum computers can reduce the size of the required system thanks to long optical fiber delays (as we showed in work on our interleaving approach), this still entails a machine much larger than we expect from the first generation of useful, fault tolerant quantum computers.
Nevertheless, researchers are actively preparing for that eventuality with the development of post-quantum cryptography schemes such as lattice cryptography, and the recommendation of using longer RSA or ECC keys in the meantime. These approaches are suspected to be secure against quantum algorithms, and moreover other developing quantum technologies can actually offer encryption schemes that are provably secure against quantum algorithms.
Quantum computing is a powerful technology, and it is striking to realize that quantum computers will be able to easily break the cryptographic systems which we rely on every day. In this context, it is also notable that some of the earliest conventional computers were not commercially motivated – early computers were used for codebreaking (Turing’s Bombe), naval calculations (Kelvin’s Harmonic Analyzer) and simulation tasks (ENIAC, Connection Machine) amongst other applications.
We are excited that our approach progresses the state of the art in quantum algorithms and fault-tolerant compilation. These results illustrate a characteristic property of the field of quantum computing, which is that while much progress is made through slow and painful incremental development, it is also normal to see huge leaps forward by an order of magnitude or more. Because of this unpredictability, as well as the high potential impact of the technology, companies and organizations which are developing quantum computers carry a serious responsibility to ensure that quantum computing is deployed in a responsible and appropriately transparent way. This is why we are choosing to publish our methods in the public domain
_______________________
[1] The modular multiplicative inverse is equivalent to the 1/x inverse operation, but for modular arithmetic.
[2] This trick works by approaching the problem of finding the inverses 1/x1 and 1/x2 of two numbers x1 and x2 by first multiplying the two numbers and computing the inverse of their product, 1/(x1x2). Then one can obtain the individual inverses, 1/x1 and 1/x2, by multiplying 1/(x1x2) by either x2 or x1. This trick eliminates the need for separate inversions for each number and effectively replaces the cost of two inversions with a single inversion and three (much cheaper) multiplications.
[3] The resource estimates we provided for RSA in this previous work do omit some potential known optimizations, though even with these considered our ECC algorithm is still significantly cheaper.
