Can We Secure Cryptography Against Quantum Attacks?

While a useful quantum computer is still under development, it already is known that when adversaries will start to use it, today's public-key cryptography will be broken. To protect digital information and services against attacks with a quantum computer, a new type of cryptography is needed: post-quantum cryptography.

The 9th Heidelberg Laureate Forum organized a panel discussion on post-quantum cryptography that included three Turing Award recipients: Adi Shamir (the S in RSA), Whitfield Diffie (of the Diffie-Hellman key exchange protocol), and Vint Cerf (co-developer of the TCP/IP Internet protocol suite). They were accompanied by two research scientists at IBM Research Europe in Zürich, Switzerland, from a younger generation: Vadim Lyubashevsky and Gregor Seiler, who contributed to the design and implementation of some of the cryptographic schemes selected by the U.S. National Institute of Standards and Technology (NIST) in July 2022 as upcoming standards for public-key encryption and digital signatures.

In the six years since NIST first called upon cryptographers for ways to protect information from quantum computing, they have come up with what they refer to as quantum-resistant algorithms. How can we know for certain that quantum computers are unable to break those algorithms?

The panelists agreed there is no mathematical proof that demonstrates the new algorithms can't be broken by a quantum computer; it is just that cryptographers can make that claim plausibly because it would be extremely hard to accomplish, said Lyubashevsky, "We base a cryptographic standard on a mathematical problem, and we have a lot of people working to solve that problem. If they can't solve it, we think it is secure. One can't expect anything more."

Shamir agreed, adding that he was a bit concerned that the new schemes chosen by NIST are all based on the same type of mathematics, called lattices. "In some sense, we are putting all eggs in the same basket, but that is the best we have."

Diffie pointed out that "So far, we have failed to develop a complexity theory that gives us real confidence in cryptography. But if you look at the history of the field, you have lifetimes for crypto systems that run into decades."

While a practical quantum computer still does not exist, and it looks like it might take another 20 to 30 years to achieve one, then how quickly do we need to implement post-quantum cryptographic standards?

"The real danger is that somebody is going to record the encrypted texts which are being used today," said Shamir. "But in 20 years' time, they will be able to use their future quantum computers in order to look back and decipher messages from the past. So, anyone who has long-term, high-level secrets, like governments, should be worried. They should not use RSA any more, but one of the new standards."

"There is another good reason to make the switch now," said Seiler, "even if someone doesn't need data to be secure for a very long time. That is because it takes a long time to deploy cryptography in large systems, like the Internet. Standards have to be changed and implemented; people have to be trained. So, even if we still have to wait a while for the quantum computer, it might be too late if we wait on switching to more secure cryptography."

The fact that computing is becoming more distributed, and thus more complicated, is another argument for not delaying the switching of standards, said Lyubashevsky. "With distributed computing, everyone has to go in it by themselves and do this switch, and if they don't, it all collapses.

"We are moving in a direction where more people will be responsible for their own data because they don't trust anybody else with it. But if we want to do distributed computing combined with cryptography in the future, we have to hurry up."

Cryptography has always been a battle between codemakers and codebreakers. While NIST is starting to introduce post-quantum cryptographic standards, cryptographers are already thinking about completely new mathematical designs. There are plenty of lightly explored areas young researchers could go into, the panelists said. According to Seiler, "We have pretty good schemes for basic tasks like encryption and digital signatures, but when it comes to more advanced cryptography, the post-quantum research is very much behind what can be done in the pre-quantum world."

"The best advice for young researchers is to stay away from lattice-based post-quantum crypto," said Shamir. "What we really lack are entirely different ideas which will turn out to be secure. So any great idea for a new basis for public-key cryptography which is not using lattices will be greatly appreciated.

"Another big open problem, although not directly related to cryptography and cryptanalysis, is developing completely new types of algorithms for quantum computers. We basically only have two: Shor's algorithm (for finding the prime factors of an integer) and Grover's algorithm (a quantum algorithm for unstructured search). Coming up with something else which would give a huge advance when run on a quantum computer as compared to a classical computer, will be a major breakthrough."

 

Bennie Mols is a science and technology writer based in Amsterdam, the Netherlands.