Quantum computers may be the perennial ”computer of the future,” but if (or when) they do become a reality, their sheer power could threaten the security of our information-technology infrastructure. Online shopping, e-mail, and automatic software updates rely on public-key cryptography methods to ensure those transactions are safe. The two main methods of public-key cryptography are RSA, which is based on an algorithm that relies on the difficulty of factoring large numbers, and elliptic-curve cryptography (ECC), which is based on the mathematical structure of elliptical curves. But a quantum computer could quickly crack either cryptosystem. In October, the University of Cincinnati hosted an international cryptography conference with industry and government experts to address this very problem.
IEEE Spectrum’s Monica Heger talked to Jintai Ding, conference cochair and professor of mathematics at the University of Cincinnati, about the possible solutions to the quantum computer problem.
Jintai Ding: If we have a quantum computer powerful enough, theoretically speaking it can break RSA and ECC systems. So if we have a powerful quantum computer, then the public-key system is finished.
The public key is important in our communication system. In my personal opinion, software updates are probably the most important thing. When your computer gets a software update, how does it know it’s from Microsoft and not somebody else who is pretending to be Microsoft? The public key is used to authenticate, so your computer has a way to tell if it’s indeed from Microsoft or not. So if somebody breaks that public system, which is RSA, then they can send you the software telling you that this is a software update from Microsoft, and your computer will think it is true. And then your whole computer can be wiped out.
Spectrum: Did you come away from the conference feeling like there were good solutions to this problem?
JD: I wouldn’t say ”solutions” yet. There are people who are trying to find public-key cryptosystems that have the potential to resist quantum computer attacks. So there are four main areas that are developing. And the difference is that they use different mathematical structures.
One area is code based, which uses the theory of error-correcting code. Another is lattice based, where the problem is finding the shortest vector for a lattice, which means given any point in space, you find the nearest point of the lattice from it.
There’s also the hashbased signature scheme, which is a little bit different. It relies on being able to develop secure hash functions [procedures for producing a single unique number that describes a large data set], but that is tricky.
And the last one is a multivariate public-key system. The security assumption here is that a set of polynomial equations—nonlinear quadratic, for example—is very difficult to solve.
These four types, at least for the moment, could resist quantum computer attacks.
Spectrum: Why can’t a quantum computer crack these four systems?
JD: In the case of multivariate, which is the area of my research, this problem of solving randomly generated polynomial systems is supposed to be NP-complete. It’s difficult to explain what NP-complete means, but it just means very, very difficult. It is exponential, meaning that as the size of a problem increases, the time to solve it increases exponentially. And quantum computers have not yet been able to defeat NP-complete types of problems.
The others are similar. But the hash-based system is a little bit different because designing a hash function is a little bit of an art. We design it, but why is it secure? We believe it is; we feel it. But it’s not based on a single difficult mathematical problem.
Spectrum: Of those four areas, is there one you think is the most promising?
JD: No, I cannot really specify one area. These four systems are all very different, and each has its own advantages and disadvantages.For example, in the case of multivariate systems, we found out that those algorithms are very fast and very efficient compared with RSA.
There is also what Johannes Buchmann, the conference cochair from Germany’s Technische Universität Darmstadt, was talking about in his lecture at the conference. On the one hand, postquantum means what happens after a quantum computer appears. But on the other hand, it can be understood as a metaphor, because maybe we don’t need a quantum computer to break RSA. In either case, we need to be prepared because we use RSA every day.
Spectrum: Is quantum cryptography a possibility?
JD: Oh yes, of course quantum cryptography is a possibility. But in my personal opinion, quantum cryptography is a little bit difficult to use because of the physical demand. It’s quite expensive. And also in quantum cryptography, they use a photon over the optical lines for the key exchange. However, the photons tend to degenerate, so therefore you cannot transmit it very far. So I don’t foresee it being used quickly.
There is also another serious problem with quantum cryptography, and that is authentication. I mean, I am talking to you, and you trust that I am Jintai Ding, but you cannot verify it. A quantum cryptosystem cannot do verification yet—cannot make sure that when you come to me, it’s me.
In the public-key cryptosystems, the public key allows us to do verification. But for sure there is potential for quantum cryptography. There are a lot of people working in this area.
Spectrum: What do you think is a realistic time frame for when we will see quantum computers being used?
JD: There’s a big spectrum of opinions. There are people who believe they will come in 10 to 20 years. There are people who believe they will come in 50 years. There are people who believe they will never come.