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.
IEEE Spectrum: What is the problem that quantum computers pose to our current cryptosystems?
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.