The promise of quantum computing is that it will help us solve some of the world’s most complex challenges. When designed to scale, quantum systems will have capabilities that exceed our most powerful supercomputers. We’re seeing this begin to take shape even today, with early breakthroughs in material design, financial risk management, and MRI technology. As the global community of quantum researchers, scientists, engineers, and business leaders continue to collaborate to advance the quantum ecosystem, we expect to see quantum impact accelerate across every industry.
However, this same computing power that will unlock solutions to complex challenges will also break some of today’s most sophisticated cryptography. By anticipating the technology of the future, Microsoft Research – in collaboration with academic and industry partners – is getting ready to accept the challenge it poses by preparing customers for a post-quantum world, today.
Cryptography – the science of encrypting and decrypting data – ensures the confidentiality of the private communications of individuals and organizations online. Encryption is used to protect everything from sending text messages to your friends, to banks transferring billions of dollars to other banks, and these transactions happen in a matter of milliseconds. Online encryption scenarios typically use a combination of two techniques: symmetric-key cryptography and public-key cryptography. In symmetric-key cryptography, the sender and the recipient must know (and keep secret from everyone else) a shared encryption key that is used to encrypt and decrypt the messages to be sent. Public-key cryptography, in contrast, allows two parties to send and receive encrypted messages without any prior sharing of keys. It was the discovery of public-key cryptosystems (by Merkel, Diffie, and Hellman in 1976 and Rivest, Shamir, and Adelman in 1978) that allows us to connect securely with anyone in the world, whether we’ve exchanged data before or not, and to do it so fast that we don’t even realize it’s happening.
Classical vs. quantum computing
The public-key cryptosystems that we use today are based on certain hard mathematical problems. For example, the security of the RSA public-key cryptosystem rests on the difficulty of factoring products of two large prime numbers – if we take two 300-digit prime numbers we can easily multiply them together to get a ~600-digit product, but if we start with just the product it is difficult to figure out the two smaller factors, no matter how much classical computing power is available for the task.
In the early ’90s, Dr. Peter Shor at AT&T Bell Laboratories discovered an algorithm that could factor products of two large prime numbers quickly, but his algorithm requires a quantum computer in order to run. Now known as “Shor’s Algorithm,” his technique defeats the RSA encryption algorithm with the aid of a “big enough” quantum computer. A quantum computer with enough stable qubits to use Shor’s Algorithm to break today’s public-key cryptography is fairly far out, but the risk is on the horizon. Further, an adversary could be recording encrypted internet traffic now for decryption later, when a sufficiently large quantum computer becomes available. In this way, future quantum computers are a threat to the long-term security of today’s information.
To address this threat, the US National Institute of Standards and Technology (NIST) – whose charter is to promote innovation and industrial competitiveness across a broad spectrum of technologies and endeavors, including cybersecurity – has begun the process of standardizing new public-key cryptographic algorithms that cannot be attacked efficiently even with the aid of quantum computer. With participants from around the globe, this project’s goal is to identify new cryptographic algorithms that are resistant to attacks by quantum computers and then standardize them for broad use.
NIST’s initial call for proposals attracted sixty-nine total submissions from around the world for key exchange and digital signature algorithms, including four proposals co-submitted by Microsoft Research. In January 2019, NIST selected twenty-six of those proposals to move forward to Round 2 of the selection process, including all four of the Microsoft Research co-submissions. Here’s a list of the proposals in which Microsoft Research is a partner:
- Key encapsulation mechanisms (KEMs):
- Digital signature schemes:
How do we protect our customers?
It will be several more years before NIST finishes its process of selecting and standardizing new post-quantum algorithms. In the meantime, we need to get to work today to begin protecting our customers and their data from future attacks. We know it will take time to migrate all of today’s existing services and applications to new post-quantum public-key algorithms – replacing cryptographic algorithms in widely deployed systems can take years and we need a solution that can provide protection while that work is ongoing.
One approach Microsoft Research is exploring is applying the new post-quantum cryptography to network tunnels. By using both current algorithms and post-quantum algorithms simultaneously – what we call a “hybrid” approach – we comply with regulatory requirements such as FIPS (Federal Information Processing Standards) while protecting against both today’s classical attackers and tomorrow’s quantum-enabled ones.
To test this technology, Microsoft is turning to Project Natick, a years-long research effort to investigate manufacturing and operating environmentally-sustainable, prepackaged datacenter units that can be ordered to size, rapidly deployed and left to operate, lights out, on the seafloor for years. While tunneling can certainly be tested in dry environments, by putting this technology to the test under more difficult circumstances (underwater), on non-production data (safe to test), we have a good representation of what an actual data center customer experience would look like, under stress.
As Karen Easterbrook, Senior Principal PM Manager at Microsoft Research says, “If we can get this to work underwater, then we can get this to work anywhere… We want post-quantum cryptography to be running on every link between every Microsoft datacenter and ultimately between every Microsoft datacenter and every Microsoft customer. And this is a necessary first step toward being able to make that happen.”
Getting ready for a post-quantum world
Dr. Brian LaMacchia, Distinguished Engineer and Head of the Security and Cryptography Group at Microsoft Research, says, “The best way to start preparing is to ensure that all current and future systems have cryptographic agility – the ability to be easily reconfigured to add quantum-resistant algorithms.”
By working in partnership with collaborators around the world to develop post-quantum cryptographic algorithms and then applying them to common internet security protocols and use cases, we can use the power of quantum computing to tackle the large-scale problems facing our planet while also ensuring that all of our information remains safe and secure.
Learn more about quantum computing, quantum algorithms including Shor’s algorithm, and Microsoft Quantum:
- What is Quantum Computing
- Q# Quantum Programming Language
- Sample Q# Code for Shor’s algorithm
- Microsoft Quantum
- Microsoft Research Post-quantum Cryptography
- Microsoft Research: Improved quantum circuits for elliptic curve discrete logarithms
- Microsoft Research: Implementing Grover oracles for quantum key search on AES and LowMC