Every four years, the Computing Research Association (CRA) releases a new set of Quadrennial Papers that call out areas of computing research that it believes to be among the top national priorities. From next-generation wireless to artificial-intelligence infrastructure to disinformation detection, each carries its own urgency in the way it will impact the evolving technology landscape and our increasingly tech-centric society. Among the October 2020 papers is one that I co-authored, “Post Quantum Cryptography: Readiness Challenges and the Approaching Storm.”
The story told by this short white paper includes two key areas that are on a collision course with one another: public key cryptography and quantum computing. In this short blog, I’d like to describe the big picture and set the stage for looking at some of the details in subsequent blogs.
Public key cryptography: the privacy workhorse of the internet
Public key cryptography was invented in the 1970s as a way for two parties who don’t know each other to establish a private communication exchange across a public communication channel. Instead of agreeing upon a common secret (referred to as a key) in advance for every communication partner, public key cryptography provides a much simpler alternative. Each party needs only two keys: a public key that is openly announced to anyone who might wish to communicate and a private key that is kept as a secret by its owner. There are some clever mathematics that explain how the two keys are created and relate to one another. An important property is that given a public key, deriving the private key is computationally infeasible within a reasonable amount of time (say, our lifetime).
Public key cryptography has two important uses that have enabled Internet privacy as we know it. As mentioned above, it is a foundation technology for secure communications. For example, your web browser is using it for secure HTTP (HTTPS) as you connect with myriad sites across the Internet. It also protects email, instant messaging, voice over IP, and your laptop’s connection to the company network. Actually, you are probably unaware of its extensive use for all kinds of communications behind the scenes across the Internet — interactions between servers, secure database transactions, cloud-computing communications, and more.
A second application of public key cryptography is digital signatures. In a digital signature, a person or organization will use their private key to encrypt a message. Anyone who needs verification of the message origin can then decrypt it using their public key. This provides proof of authenticity and integrity: the message must have come from the expected source and it has not been altered. This is widely used — for example, in digital certificates and public key infrastructure (PKI). The idea is that an organization can provide an electronic document (with its digital signature) to prove its identity. Have you ever wondered how your web browser can be sure the website you are interacting with is not an imposter? Yep — certificates are used to verify, for example, that you really are interacting with facebook.com and not a rogue impersonator. Digital signatures are also used to verify software updates, email messages, mobile devices, and all kinds of authentication transactions.
It’s fair to say that public key cryptography has enabled much of the Internet application world as we know it today (electronic commerce, for example) and that it is used by billions of users every day — whether they know it or not.
Quantum computers: and now for something completely different…
Quantum computers are broadly defined as a new kind of programmable device that leverages quantum physical phenomena in controlled ways to compute solutions to problems that would seem otherwise impossible. At the heart of this technology is the qubit (quantum bit), which — unlike conventional bits — can simultaneously hold both a 0 and a 1. Quantum computers leverage two surprising notions that defy conventional rules of digital electronics: superposition, in which multiple states can be held simultaneously within a single probabilistic system, and entanglement, in which groups of qubits can collectively create complex state superpositions that are beyond the simple combination of individual qubits. Interestingly, when you extract a result from a quantum computer (called a measurement), all of this complexity disappears and only a single value remains.
With these surprising properties, a quantum computer is potentially capable of encoding and solving problems that are far too complex for even today’s most powerful supercomputers. For example, there is a great deal of optimism that quantum computers will help the field of quantum chemistry (such as material science or pharmaceuticals) by simulating complex molecular systems and chemical reactions. Understanding how particles interact under various circumstances is enormously complex, given their inherently uncertain behavior at the atomic level. Some other areas of application include optimization, computational biology, and machine learning.
For a long time, quantum computers were on the drawing board as merely a theoretical technology that seemed impossibly difficult to build. (How do you control quantum physical phenomena?) But as you’ve seen in the media, there has been a great deal of activity and progress among both established companies (IBM, Google, Intel, and Honeywell among them) and startups (such as Rigetti, IonQ, and Xanadu) who have built prototypes in the 50-80 qubit range. While the story of where we are with it technology-wise is a long one, it’s clear that the industry is optimistic, as indicated by the tremendous outpouring of government funding and venture-capital investment around the world.
Post-quantum cryptography: new protections for our public key cryptography
But how does public key cryptography relate to quantum computing?
In the 1990s, an algorithm was discovered by Peter Shor (now a highly decorated MIT professor of mathematics who, at the time, was working for Bell Labs) that showed how a quantum computer could be used to reverse engineer a private key from a public key by leveraging the special properties of quantum computers. This was an amazing discovery at the time, but one which wasn’t particularly impactful, since quantum computers were a long way away from being built. Today, quantum computers are still in early form and not powerful enough to fully implement Shor’s algorithm. That said, they appear to be gaining ground and show considerable potential to scale up to the task in the future.
The National Institute of Standards and Technology (NIST) has been monitoring the situation and in 2016 kicked off an effort to develop new public key cryptography algorithms that will be safe against the quantum computing threat. The algorithms are collectively known as post-quantum cryptography, which you can think of as “cryptography that will be safe to use after quantum computers have arrived.” You can take a look at NIST’s activities on its website. Various documents explain which of today’s cryptography algorithms are at risk, which algorithms are being considered as replacements, and the timeline to publish new standards for industry use.
So where are we now? As you can see from all of this, the industry is effectively involved in something of a race: On the one hand, quantum computing, as a technology, is developing in power and robustness as the R&D world incrementally sorts out a large number of technical hurdles to make it work at scale. On the other hand, NIST is actively working to develop new cryptography standards that will be safe against quantum computers of the future, should they reach sufficient size and power to realize their potential threat. Note here that cryptographic readiness is not just about having new algorithms. Part of the challenge will be implementing and deploying them as an industry, which will take time and is considerably more complex than it looks. (Also see Sean Huntley’s blog “It’s Time for Crypto Agility” for a high-level discussion on these topics.)
I look forward to further discussing this issue in subsequent blogs.
