Post Quantum Cryptography and the Approaching Storm

There is no shortage of excitement surrounding recent advancements in quantum computing! Whether it’s company press releases on new prototypes and products (e.g., IBM Q System One, IonQ), academic research on quantum applications or the physics of qubits (e.g. molecular simulation, single-photon emitters), or government-related announcements on new research initiatives (e.g., National Quantum Initiative, Stanford Q-FARM), a steady flow of developments has kept us on the edge of our seats. The science behind it all has provided a heady list of technical issues to follow.

Left: IBM Q System One from IBM Research. Right: “Is the US Lagging in the Quest for Quantum Computing?” Scientific American, Dec. 6, 2018.

What many people don’t realize, however, is that as the prospects for scaled quantum computing steadily improve, a disruptive security threat simultaneously comes closer and closer to realization.  In the early 1990s, before quantum computer prototypes even existed, Bell Labs researcher Peter Shor showed that if scaled quantum computers were to exist, they could be used to efficiently reverse engineer private keys in our widely used public key cryptosystems.  To be a little more precise, his quantum algorithm demonstrated that the problem of integer factorization could be solved by a quantum computer in polynomial time – in other words, with dramatically more efficiency than algorithms running on conventional computers today.  Shor’s algorithm, furthermore, can be generalized to solve both discrete logarithm and elliptic curve discrete logarithm problems. In case you don’t recognize them, each of these is a cornerstone hard problem underlying our current public key cryptography!

This surprising result implies that the public key cryptography standards widely implemented and deployed across the Internet today (RSA, ECDSA, ECDH, and DSA) will be vulnerable to attack if and when scaled quantum computing becomes available.  It’s little surprise, then, that the National Institute of Standards and Technology (NIST) published a report in 2016 articulating the problem and pointing out that, “a sufficiently powerful quantum computer will put many forms of modern communication—from key exchange to encryption to digital authentication—in peril.”

Impact of QC on Common Crypto Algorithms. From NISTIR 8105: Report on Post-Quantum Cryptography, 2016.

This scope and significance of this is even bigger than it looks. The exploding digitization of each and every industry across our global society — finance, energy, retail, health, government, entertainment, social media, and more — has been enabled by and relies upon security and privacy technologies built on public key cryptography.  At the time of this writing and according to hostingfacts.com, more than four billion Internet users interact with nearly two billion web sites and generate more than three trillion dollars of Internet retail activity, all of which uses public key cryptography.  Public key cryptography ensures that our communication exchanges using myriad devices are secure and private, that we can verify the identity of parties before private data is transferred, that users are authenticated before accessing confidential accounts, and much more.

To address the situation, NIST embarked on a multi-year initiative starting in 2016 to select new public key cryptography algorithms to replace those that are vulnerable.  These new algorithms are collectively referred to as Post Quantum Cryptography, or PQC.  You can think of PQC as cryptography that is quantum resistant or quantum safe in addition to resistance against attack by conventional computers; in other words, cryptography that is intended to remain secure once scaled quantum computing has arrived.  While a full description of proposed PQC algorithms is a long and technical story, the quick version is that algorithms fall into roughly five categories: hash-based cryptography, code-based cryptography, lattice-based cryptography, multivariate cryptography, and cryptography based on the problem of supersingular elliptic curve isogeny.  These five approaches make use of alternative mathematical frameworks and hard problems with no known mapping to quantum algorithms, and they collectively provide a new basis for the basic primitives of public key cryptography (encryption, key encapsulation, and digital signatures).

VMware has been following the evolution of PQC carefully, including advancements in quantum computing which ultimately drive the timeline for readiness. An important consideration, we believe, is the need for our industry to prepare itself with cryptographic agility.  That is, migration to new cryptographic algorithms will require schemes which enable transition from one cryptographic standard to another, something that will likely happen more than once in the likely post-quantum future that we face as an industry.  While existing cryptography implementations offer some solutions (e.g., cipher suite negotiations in TLS), VMware has worked with the Computing Community Consortium and other partners in the industry to think more deeply about how agility mechanisms should work at a variety of levels and within diverse systems contexts.

There is much to say about this emerging technical sphere and the massive transition that lies before us as an industry.  I invite you to attend my VMworld 2019 session, OCTO2501BU — Post-Quantum Cryptography: What Every Security Professional Should Know, on August 29 where I will discuss PQC and the migration path before us. The session will include some basics of PQC, how early deployments are likely to work, notable standards efforts, and the activities of other key organizations including VMware.

In the meantime, you can check out the VMware CTO Perspective paper, Quantum Computing and Cryptography: Why You Need to Pay Attention, which discusses the broader issue, including some basics on quantum computing and how it is linked to the cryptography threat described.  Notice, BTW, that symmetric key cryptography will also be impacted though less severely, something I haven’t touched upon here. A list of early recommendations for organizations like yours is also included.

As I sign off, I wonder what your organization is thinking about with respect to quantum readiness and PQC? Share your thoughts below. I hope to meet some of you at VMworld US next week.