There’s a race going on right now between the quantum computing and public key encryption. Before long, quantum computers will make routine work of cracking RSA and Elliptic Curve Cryptography (ECC) schemes. The question, then: will crypto researchers and standards bodies get quantum-proof encryption algorithms into the field before all the world’s secrets get leaked?
If that sounds vaguely like a plot from the Marvel multiverse, that’s because it nearly is. The stakes are genuinely high, even if the math is genuinely over most of our heads.
As you know, there are two basic kinds of cryptography in the modern world: symmetric key and public key. What we’re talking about here only affects public key. But the sticky thing is that even when symmetric keys are used, there is often some portion of the overall arrangement that uses public key encryption, if only briefly to exchange a key for the symmetric algorithm to use. So, break public key and you’ve—roughly speaking–broken the ability of the world as we know it to store and exchange secrets.
Kinds of public key
The status quo–which simply cannot hold—is that there are two forms of public key cryptography that are generally used: RSA and ECC. Both are useful to cryptographers because they are so-called “trap door” functions. You can work the math going forward with no difficulty, winding up with an answer. But taking the “answer” and running the process in reverse turns out to be a huge guessing game that takes more time than is remotely practical to play out.
That’s how it is right now, anyway, because computers (and conventional computation) aren’t good at brute forcing (or otherwise solving) the underlying trapdoor functions. In the case of RSA encryption, classical computers and current algorithms aren’t good enough that taking the product of two large prime numbers and finding the two prime factors doesn’t take more time than the sun’s going to be lit up. In the case of ECC, the problem lies in the difficulty of working backwards from an elliptic point multiplication, given the result and one point, to find the original point–and the same time-constraint impossibilities obtain.
Enter the qubit
Not every computationally difficult problem gets easier with quantum computing, but some do. The arrival of a sufficiently capable quantum computer will, it seems, spell the end or RSA and ECC encryption. By way of oversimplification, a quantum computer uses units of computation called quantum bits (qubits) and if you can assemble enough working qubits (a tall order, but not an impossible one), you’ve got computational ability sufficient to break things like RSA.
Much has been made of the rate at which research groups have been able to build machines that have more and more qubits, but researchers I’ve spoken with have said that the press has made too much of the raw count (which has, however, marched steadily upward). There’s also a dimension of the problem that has to do with how stable a given qubit is (there are different physical approaches to making a cubit and some are easier to build but not nearly as stable). Even with the stability factor added in, though, more cubits—and stable ones—will eventually be practical.
Educated guesses converge on our being about 10 years away from a quantum computer that can deliver the code-breaking capabilities we’re talking about. To put this in other and only slightly overstated words, we’re about 10 years from having all the current secrets in the world revealed. Tim Hollebeek, industry and standards technical strategist at DigiCert, recently put it this way in the conversation we had: “the significance of this is hard to overstate.”
So there are two timelines here, either of which could be condensed or lengthened by developments as yet unknown, but if quantum computing manages to make it practical to break public key encryption based on RSA and ECC before these schemes have been replaced by something that doesn’t readily yield to quantum computers, all sorts of vital things are going to be broken.
The good news here is that there are several sorts of algorithms that can be used for public key cryptography that don’t appear to become significantly easier to solve in a post-quantum world. For instance, lattice mathematics–which is probably not something you encountered in college math classes in less you’re a mathematician—poses some problems that work as trapdoor functions and therefore it can be used for encryption and certificate creation. There are some other approaches as well and in fact someone in the crypto community has tended to propose a new approach every few years since the 1970’s. These alternatives were, at the time, of academic interest, but in no position to compete with the already well established RSA and ECC algorithms. These various “quantum-proof” algorithms are being gussied up by a number of different teams worldwide for examination by NIST, with a first round of submissions having just been pared down for the second round of consideration.
At a recent conference DigiCert held for its customers in Las Vegas, I sat down with key players from DigiCert and Microsoft to talk through their early observations of round two. One interesting point is that there are submissions that use several different approaches to creating a problem that quantum computing will find either infeasible or nearly so. So there’s a lot of different possibilities. What’s a little daunting, though, is that none of the options currently provides the same results in terms of execution speed in a given key length that classical approaches provide. So it would appear that failing improvements in the current systems, either we’re going to have much longer keys or we’re going to have much slower key exchanges than we currently enjoy.
NIST has taken a wait and see attitude about how many rounds there might be before winning algorithms are selected, according to Brian LaMacchia, a distinguished engineer in cryptography at Microsoft. But it wouldn’t be more than one or two further rounds, presumably, meaning there will be candidates for standards within a couple of years.
While this might seem to suggest that the need for post-quantum crypto will be solved years in advance of quantum’s arriving at the necessary code-breaking capabilities, remember that having the right algorithm is a long way from having the algorithm distributed and then used in the field.
Consider the certificate used for securing website communications using the TLS (SSL) protocol, for example. Every website will need to be updated to process TLS handshakes in the new algorithm and, further, will need certificates that have been signed using post-quantum algorithms and keys signed by certificate authority that is geared up to produce quantum-proof certificates.
With all that in place, nothing about TLS works unless all the world’s browsers have been updated to support the new algorithm and certificates.
So there’s a lot of work to be done, though where certificates are concerned it’s fairly clear what the tasks at hand are and how to carry them out. It’s bound to take several years, though, and meanwhile the speed of advancement in post quantum computing is considerably harder to predict. Experts have tended to guess that it’s at least 10 years out, but they are the first to admit that the schedule could change considerably if an unexpected technological breakthrough makes it substantially easier to build and replicate stable cubits.
There is also a moment when, since all the world certificates and all the world’s encryption need to be migrated to new standards, perhaps the world of certificate authorities will be shaken up in the process. The lion’s share of the business for most CA’s is website SSL certificates and, truth is, SSL hasn’t exactly been problem free. One could imagine the way that trusted roots are embedded in browsers (rather than being expressly chosen and installed by users) could change. Who pays whom to sign what could well be re-examined. All that said, there’s always plenty of resting inertia around these sorts of standards. Maybe there will just be a whole lot (billions?) of re-issues of certificates that offer both classical and post quantum signatures.
At this point it’s too early to say how it will play out, but there’s certainly room for upheaval–either in how new certificates and encryption are delivered or in the potential exposure of classically protected data and assets should quantum code breaking arrive in full force ahead of schedule.
Related article (on TechTarget.com): DigiCert, Gemalto and ISARA to provide quantum-proof certificates
# # #