Entering the quantum era opens doors to endless possibilities. Within seconds, a quantum computer can solve certain problems that would take a classical computer billions of years. This new potential can lead to breakthroughs across industries, from healthcare to life sciences, and beyond. But as our computational power grows exponentially, our cryptography must be upgraded as well.
Introducing the study
Today, the two most commonly used forms of public-key cryptography are the RSA cryptosystem and elliptic curve cryptography (ECC). The RSA cryptosystem is based upon factoring large numbers, and ECC is based upon computing discrete logarithms in groups of points on an elliptic curve defined over a finite field. Shor’s quantum algorithms can—in principle—be used to attack these mathematical problems that underlie both the RSA cryptosystem and ECC. However, to turn these theoretical insights into actual implementations that a quantum computer can carry out, a substantial amount of work is required to program and compile the algorithms into native gates that a quantum computer can understand.
This brings up fundamental questions: How many qubits will be required? What is the gate depth and how many gate sets need to be used? In this study, Quantum resource estimates for computing elliptic curve discrete logarithms, the Microsoft team sought to answer these questions to help support post-quantum cryptography research.
A motivating question for the study was to determine
Which case is more vulnerable to a quantum computer: real-world, comparable instances of ECC or RSA?
Knowing the precise cross-over points helps assess security levels of cryptosystems commonly found today in online encryption, key exchange, and digital signatures.
A quantum computation requires certain resources, such as the number of qubits used and the number of quantum gates that are executed. Quantum computations often are possible using different trade-offs between these resources. The goal in this study was to optimize for the fewest number of qubits required to break the mathematical problems underlying both ECC and RSA.
This entire study was written and executed using productivity tools implemented as part of the Microsoft quantum programming framework, much of which is available in the Microsoft Quantum Development Kit. This included programming the algorithm, compiling it into a quantum circuit that implements the algorithm at an assembly level, running a simulation of this quantum circuit on a classical computer, and confirming the results. The results of the study outlined estimates for the quantum resources needed in order to break public-key encryption schemes at various security levels recommended by the National Institute of Standards and Technology (NIST).
Choosing the gate set
Classical computers use Boolean logic, so many developers are familiar with AND, NOT, OR, and XOR gates. However, a quantum computer requires unitary gate sets because quantum circuits must also function in reverse. Reversible classical gates are a special case of unitary gates; they permute bit strings, but never create superpositions, as opposed to general unitary gates which can send bit strings to superpositions of bit strings. Reversible classical gates can be simulated on a classical computer by tracking the step-by-step evolution of a set of randomly chosen test bit strings.
Toffoli gates are ideal for building up large-scale reversible circuits that have thousands of qubits and billions of gates, as they work in both a classical and quantum environment. The gates sit between the high-level, abstract algorithm and the low-level, assembler-like instruction set which will ultimately drive the quantum computer. Results of the resource estimates—number of qubits, depth, etc.—are translated into physical level estimates once the quantum computer’s architecture and error rates are known.
Reviewing the results
To demonstrate the resource estimates, the team presented the results in a table to outline the number of qubits, the gate depth, and the number of gates required to complete the computation—solving the mathematical problems that underlie the cryptosystem—for the various levels of security set by the NIST. Resource estimates are outlined at each comparable security level, comparing ECC and RSA.
Read the published paper to explore the full results.
The Microsoft team presented this work at the Asiacrypt 2017 conference in December, 2017—a main consortium of the International Association for Cryptologic Research (IACR). Watch the video of the talk.
Important findings: optimizations were key
One of the most resource-intensive bottlenecks was the process of computing the so-called modular inverse. In 1/x modulo p —where p is a prime— bottom line estimates receive a significant inflation. If you use the straightforward approach without optimization, you would require a million qubits. But the right mix of algorithmic tricks to cut down the cost of computing the inverse yields a dramatic reduction—from one million down to 2330 logical qubits.
The memory footprint was another important optimization. Quantum memory can be used as a scratch space, even if it has already been allocated in an earlier computation. Where ‘clean’ memory is reset into a known state, ‘dirty’ memory has already been written into. The methods developed by the Microsoft team allow the use of such allocated memory for arithmetic operations such as addition, multiplication, subtraction, and division.
Final thoughts
Quantum solutions can lead to breakthroughs in healthcare, energy, environmental systems, smart materials, and more. But gaining this powerful new potential means an upgrade from current standards—including cryptography—so we’re ready to embrace this new future.
This study was the first time this resource estimation process was ever completed end-to-end for ECC and RSA encryption, with the resulting circuits simulated and thereby validated. By knowing the number of qubits required to break public-key encryption, we have a better understanding of the levels of security needed to keep data safe.
In collaboration with industries, institutions, and universities, Microsoft has united talent throughout the globe to work toward a successful transition into the quantum age.
Learn more about the research conducted by the Quantum Architectures and Computation group as well as by the Security and Cryptography group.
Learn more about post-quantum cryptography research at Microsoft.
Research overview
Microsoft researchers leveraged resource estimation techniques to analyze the cost of mounting quantum attacks on real-world public-key cryptographic schemes. Case in point are RSA encryption, where the underlying hard problem is that of factoring large integers and elliptic curve cryptography (ECC), where the underlying problem is that of computing discrete logarithms.
The Microsoft team presented this work at the Asiacrypt 2017 conference in December, 2017—a main consortium of the International Association for Cryptologic Research (IACR). Watch the video of the talk.
Learn more about the findings in the published paper:
Quantum resources estimates for computing elliptic curve discrete logarithms
December 31, 2017
Authors:
Martin Roetteler
Michael Naehrig
Krysta M. Svore
Kristin Lauter
Other related works
- An analysis of Shor’s algorithm for factoring, which breaks RSA, was completed in this published paper.
- The LIQUi|> programming language in which the resource estimation was performed.
- The Q# programming language which is part of the Microsoft Quantum Development Kit and the basis of next generation quantum programming.