Can We Secure Cryptography Against Quantum Attacks?

Key Issue.   Considerable tech depth here by leaders in the field. 

Can We Secure Cryptography Against Quantum Attacks?, By Bennie Mols

Commissioned by CACM Staff, November 10, 2022

The HLF post-quantum cryptography panel.

The Heidelberg Laureate Forum post-quantum cryptography panel. From left, Whitfield Diffie, Vinton G. Cerf, Adi Shamir, Vadim Lyubashevsky, and Gregor Seiler.

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." ...  '