Researcher works to future-proof the internet
Martin Ekerå has just completed his doctorate at KTH, focusing on quantum computer algorithms for cryptanalysis. His research primarily examines if, and when, quantum computers might one day crack most asymmetric cryptographic algorithms currently used to protect internet privacy.
Quantum computing is still in its infancy, Ekerå says. Today, small quantum computers with up to around 1,000 qubits exist, but they have extremely limited capacity, and errors occur easily when qubits are manipulated. Large-scale, fault-tolerant quantum computers are still a long way off and would be necessary to effectively break current cryptographic algorithms, he says.
"We don’t know with certainty when—or even if—quantum computers relevant for cryptanalysis will be built, but development is moving quickly. I think we might start to see such computers sometime after 2030," Ekerå says.
Two related mathematical problems
Recently completing his doctorate in theoretical computer science at KTH, Ekerå now serves as chief cryptologist in the Cryptology and IT Security Division at MUST.
Ekerå says that almost all asymmetric cryptographic algorithms used commercially to date rely on two closely related mathematical problems: integer factorisation, which is fairly well-known, and the discrete logarithm problem, which is perhaps less familiar.
In 1994, Shor’s groundbreaking quantum algorithms solved both of these problems effectively. They represent the main reason quantum computers pose a threat to most asymmetric cryptographic algorithms used on the internet to date, he says.
"My thesis explores ways to improve and further develop Shor’s algorithms. These improvements could make it possible to run the algorithms sooner, on less capable quantum computers, than would otherwise be feasible."
Outdated cryptology should have been replaced 20 years ago
Ekerå explains that he has collaborated with others, including Craig Gidney at Google, to estimate how powerful quantum computers would need to be to run the new algorithms. The goal is to understand approximately how much time remains before today’s asymmetric cryptographic algorithms could potentially be broken.
While current quantum computers are not yet relevant for cryptanalysis, it is high time to act on protecting privacy, he says. Attackers could store ciphertexts sent today to decrypt them in the future, when more advanced cryptanalysis methods are available. Therefore, cryptographic algorithms need to be replaced well in advance—long before they become practically vulnerable.
“If, for example, we aim to protect privacy for 30 years, and we assume a relevant quantum computer might available by 2035, we should have replaced all vulnerable cryptology roughly 20 years ago. This demands careful consideration when handling sensitive personal data, patient confidentiality, bank privacy, and so on,".
"Cryptologists should be conservative"
According to Ekerå, it is essential for organisations that have not yet implemented protective measures to do so.
"We’ll have to see how quantum computing develops—and to what extent its development continues to receive funding, given there are relatively few known applications for cryptographically relevant quantum computers beyond breaking cryptosystems. But as a cryptologist, one should be conservative and plan for the worst-case scenario,".
He adds that taking protective measures early is a cost-effective insurance policy. He stresses the importance of distinguishing between privacy protection and other uses of cryptology, and that replacing vulnerable cryptography should be done in an organised way, in the correct order of priority.
"I offer some advice on this in the thesis," Ekerå says.
Text: Peter Asplund