Nmedia - Fotolia
Quantum computers mean cryptography needs to change, and soon
As quantum computing gains momentum with practical quantum computers due to come online as early as next year, concerns about post-quantum cryptography are pushed to the forefront.
Quantum computers, cryptography and encryption are a potent mix, especially because quantum computers could eventually give attackers a practical method for decrypting almost all traditionally encrypted data.
Although the potential for quantum computing was first posited in 1982 by physicist Richard Feynman, and the MIT mathematician Peter Shor reported an algorithm that would enable quantum computers to defeat most types of cryptography in common use in 1994, it's long been assumed practical quantum computing was out of reach for the foreseeable future.
But the days of kicking the potential for quantum computers' cryptography threat down the road may soon be at an end, according to Tim Hollebeek, industry and standards technical strategist at DigiCert Inc., a digital security company headquartered in Lehi, Utah. Cryptographically relevant quantum computers capable of solving the type of problems that enable classical cryptography are around the corner as quantum computers keep getting better.
Find out about the latest developments that will enable quantum computers to defeat classical encryption, and what organizations using encryption can do to prepare.
Editor's note: This interview was edited for clarity and length.
Where are we currently in the development of quantum computers, as compared with traditional computers?
Tim Hollebeek
Tim Hollebeek: One of the things that's different this time is that we actually have classical computers. The first time, we were trying to build calculators and computers and anything like that; it didn't even have to be better than a human at any problem -- it just had to be helpful.
That goes for very early things like ENIACs that were just doing repetitive math functions. That was very helpful because a person didn't have to do that, so there was a very low bar for them to jump. This time, the fact that we have classical computers means the bar is raised: When can a quantum computer do something that a classical computer can't? Especially since quantum computers are very large and expensive, there's no point in using one if the same problem can be solved more cheaply just using a classical computer.
We're right on the edge of that boundary right now. Current quantum computers aren't quite powerful enough to do things that classical computers can't, but that will probably change within about the next year. If you read a lot of articles about quantum supremacy, it's about that boundary, when a quantum computer will be able to solve a problem that a classical computer can't.
The important thing about quantum computers is that they're only better than classical computers at certain specialized problems. They're not general purpose computing machines that will eventually do everything that classical computers do. But for a limited set of problems, they can solve things that normal computers can't.
What types of things can quantum computers do better than classical computers?
Hollebeek: Unfortunately, and this is where the computer security benefits and drawbacks come in: One of them is factoring large numbers and solving elliptic curve problems.
Now, that's economically useful and a lot of what is going to drive quantum computing is economically useful problems. It's a long way from the point when you can solve a problem that a classic computer can solve to the point where you can factor numbers that are large enough to cause security problems. So, how fast we get from where we are today to where we have security problems is going to depend on how useful the economically useful problems are.
They tend to be problems related to optimization and searching through large sets of data and things like that. There are a lot of things around simulation of large systems of equations. One of the things they're really good at -- because they are actually quantum systems themselves -- they are extremely good at simulating other quantum systems. So, certain chemistry problems, how to design materials, how to optimize a superconductor or another material for better quantum properties, that's the sort of thing they're really good at.
When will practical quantum computers be ready to 'change everything'?
Hollebeek: There's a gap between 'economically important' and 'change everything.' Economically important quantum computers will arrive within the next year or two. That seems a relatively safe bet just based on the fact that for a long time there wasn't that much progress. But in the last year or two, we've gone from computers that had just a couple of qbits to computers that had 50 to 70, and the quality seems to be getting better. There are a lot of research dollars being dumped into it -- literally billions of dollars by several foreign governments.
The economically relevant ones will arrive relatively soon, and they won't be able to do things that normal computers can't do, but they'll be relatively specialized problems, and the computers will be large and expensive and be sitting in million-dollar research labs. Large companies like IBM might give you access to them, but that's where we'll be in the near future. Those computers will be able to do interesting things, but they won't be a threat; they're too small and the circuits are too noisy.
Ten to 20 years is a good timeframe for a guess about when we get to the point where RSA and ECC [elliptic curve cryptography] are threatened because the computers are sufficiently large and they have enough stable qbits.
Quantum computers, cryptography and the future of encryption
We've been told that practical quantum computers, when available, will be capable of decrypting just about anything that's been encrypted in the past 30 years or so. Is that an accurate depiction?
Hollebeek: It's slightly more subtle, but it's not entirely inaccurate. There are a couple of caveats. One is the fact that quantum computers are good at factoring large numbers was one of the earliest discoveries that actually motivated thinking about them. This goes back to Shor's algorithm in 1994 when Peter Shor showed that a quantum computer could factor large numbers and everybody was like, 'Well, that's nice, but we won't have quantum for years, and it's not quite clear how we would build them.' All that has changed in the meantime.
What is vulnerable? Well, there are a couple of points: What is vulnerable is asymmetric cryptography like RSA and elliptic curve. In theory, symmetric cryptography -- like AES [Advanced Encryption Standard] -- is vulnerable as well but that uses a different algorithm called Grover's algorithm, and that algorithm is much less powerful, so it probably won't be in the near future that symmetric algorithms are vulnerable.
Shor's algorithm is the one for asymmetric cryptography; Grover's is the one for symmetric cryptography. Shor's algorithm works really, really well.
The trick though, is that almost all encryption -- especially for communication -- starts out with an asymmetric algorithm for the two sides to agree on what symmetric key they're going to use. So, if you have access to a quantum computer and a recording of one of those conversations, you can go back and figure out what the symmetric key was, then decrypt all the traffic.
How do Shor's algorithm and Grover's algorithm enable quantum computers' cryptography attacks?
Hollebeek: Shor's algorithm is the one that does factoring, and a slight variant of it also works against the hard problems that underlie elliptic curve cryptography. Those are the two algorithms that underlie all of the TLS [Transport Layer Security] and digital signatures we use today, so all of those are vulnerable to Shor's algorithm.
Grover's algorithm allows you to search large spaces very, very quickly, so sometimes you'll see references to it being used to search large databases. But one of the things it allows you to do is search for the key that encrypted a particular piece of data much more quickly than you can do it on a classical computer.
You've stated in the past there are plenty of public key algorithms, it's just that the two we've chosen -- the products of large primes and elliptical curve algorithms -- are most susceptible to being defeated using quantum computing. What other types of public key algorithm are there, and could they displace the ones we are using now?
Hollebeek: There are five main math areas -- lattices, codes, hashing, multivariate equations and zero-knowledge proofs. NIST is having a competition where they're in the process of selecting multiple different algorithms from multiples of these different mathematical problems in order to find one or more successors to RSA and ECC.
What else should people be doing about the imminent advent of quantum computing?
Hollebeek: The answer depends a lot on where you are. Some people say it's relatively low value, and if your data only has to be secret for five years or so, you don't have to do anything today. If, on the other hand, you are in a situation where the data you're protecting has to be secret for 30 years or more, then you potentially face some problems if you're trying to go along with business as usual.
The most useful thing for people to be doing right now is to be doing research on this and finding out, first of all, where is cryptography used in their systems, what it protects, and what are the data protection lifetimes associated with that? You should start coming up with an inventory of what your cryptography is and what you're going to have to do over the next 10 or 20 years to protect it, and when.
It's time for people to start having a plan. There's also some technology available today that can solve some of these really hard problems, like if you're shipping a car that will be around 15 years from now or another long-lived industrial control device. Some techniques like hash-based signatures can be used for code signing that are known to be resistant to quantum computers. Especially in very high-assurance industries, people need to be talking right now about what needs to be done in order to protect data and devices that have very long protection lifetimes.
