Post-Quantum Cryptography

Quantum computers are like climate change: everyone knows it’s coming, but the world is not prepared for it. Although quantum computers, in contrast to climate change, will be of great benefit because, on the upside, they can solve certain problems far more efficiently than conventional computers, such as combing through vast amounts of data. On the downside, however, they are also able to solve some mathematical problems particularly efficiently that form the basis for modern cryptography. And this is where the world will have a huge problem when the first really “powerful” quantum computer arrives on the scene: nothing on the internet will be secure anymore – not online banking, not shopping websites and not IT systems in ministries, the military, hospitals, power plants or corporations. That is why experts are conducting extensive research into new cryptographic security techniques. It was on this topic that computer science professors Christoph Krauß and Alexander Wiesmaier organised a high-profile workshop at h_da in November. In this interview for impact, they explain where research currently stands.

Interview: Christina Janssen, 16.1.2025

impact: The title of your workshop was: “Securing the Future: NavigatingChallenges and Strategies in Post-Quantum Cryptography Migration”. What exactly was it about?

Professor Christoph Krauß: The problem is that encryption methods, by which I mean cryptographic algorithms, age and weaken over time. This is due, on the one hand, to “normal” progress: computational power continues to increase at a rapid pace, which is why schemes that were still secure 20 years ago are now completely outdated. However, the development of quantum computers also poses a major threat because these facilitate attacks that were not possible before.

impact: Will a sufficiently large quantum computer crack all the security procedures commonly in use today?

Krauß: Yes. All common schemes used for digital signatures, for example, or for generating session keys for online meetings or emails – known as asymmetric schemes – will become insecure. The risk is not quite as great with the symmetric schemes used for the actual encryption of data. In any case, however, we need new schemes based on other mathematical principles.

Professor Alexander Wiesmaier: The problem is that once the quantum computer arrives, we can expect a lot of damage. Most individuals or organisations will continue to have conventional PCs, and only very powerful attackers will have quantum computers. That’s the scenario we’re discussing here. A highly uneven battle.

impact: Who already has such a powerful quantum computer?

Wiesmaier: No one. As far as we know. But big players such as Google or IBM have functioning quantum computers of a size that just a few years ago everyone thought was impossible to achieve so quickly.

Krauß: In December 2024, Google presented its new “Willow” processor with 105 qubits. The number of qubits that the first quantum computers had a few years ago was still in the single-digit range, now we are already at 105.

impact: What does that mean?

Krauß: Google presented a comparison: the best supercomputer that currently exists would need ten quadrillion years to solve a problem that takes Willow only five minutes. This is a bit of an embellishment because Google based its examples on quantum problems with no real practical use. Quantum computers are particularly good at these, while everyday computers are rather poor. But that is basically the order of magnitude.

impact: This means that quantum computers could, for example, conduct cyberattacks on universities, critical infrastructure, government institutions or companies far more effectively?

Krauß: That’s one thing. Another problem is the hacking of encrypted data later on. Take government documents, for example, which are encrypted using conventional methods. The NSA – just as an example – records the entire flow of communication when the data is transmitted. Although it is not yet able to decrypt this data, at some point in the future it will have a quantum computer and be able to crack the key and then access the data. Data that we encrypt today will no longer be secure in a few years’ time.

Wiesmaier: This is an important driver for our research. There are always people telling us to slow down. But we cannot wait until the quantum computer has arrived because then it will be too late.

impact: What is research doing to prevent this?

Krauß: Researchers are currently working on new mathematical methods that the quantum computer cannot crack. And that, of course, a conventional computer cannot crack either. To do this, they are developing new post-quantum algorithms to replace the classic ones. There are, however, disadvantages with the new algorithms: they are not as efficient, and their key lengths are huge. That is why we cannot use them to just replace the old algorithms without further ado. In cars, for example, where IT security today plays an important role in preventing them from being hacked and controlled remotely, the resources are limited. We cannot simply say that the key is now a few megabytes in size instead of a few kilobytes and that it takes three or four seconds instead of a few milliseconds to verify a signal. By then you’ve already driven into the wall. And that’s precisely where our research comes in! We are integrating the new algorithms into practical applications. Together with partners, we are developing, for example, secure processes and methods for post-quantum cryptography and crypto-agility for the automotive sector as part of the PARFAIT project funded by the Federal Ministry of Education and Research. Here, we are working closely with Professor Marc Stöttinger from RheinMain University of Applied Sciences, among others, who took part in the workshop and explained the challenges of putting post-quantum cryptography into practice.

Wiesmaier: It’s not just a matter of the greater consumption of resources but also about fitting in the new algorithms. If you imagine cryptographic building blocks as Lego bricks: there are some with two studs and some with four or six, some have only one row of studs, others have two. But there is no equivalent in the quantum world for every “conventional” Lego brick. It’s like having first a nail and then a screw: I can hammer the screw into the hole made by the nail, but that’s not a good solution.

impact: Could you please explain the mathematics behind the nail-and-screw problem in simple terms?

 Wiesmaier: An example for the nail is the Diffie-Hellmann protocol used to generate session keys between two communication partners. It is based on the “discrete logarithm problem”, which can be imagined as follows: logarithmisation is more difficult than exponentiation. If you take real numbers for the calculation (editor’s note: integers, fractions, decimals, etc.), logarithmisation and exponentiation are both perfectly feasible for an algorithm. But if, instead of real numbers, you take other, mathematically more complex structures, for example “finite bodies”, then logarithmisation becomes very difficult for conventional computers. Presumably. At least so far there is no mathematical proof to the contrary. But we know for sure that sufficiently large quantum computers can do it efficiently. 

impact: And how would the screw look?

Wiesmaier: Examples for screws are what we call lattice-based methods. Here, certain problems are examined in multidimensional coordinate systems with hundreds of irregularly spaced axes. Roughly speaking and in simplified terms, the attacker would have to find a specific point in the system that is not, however, located on one of the axes but somewhere in between. That is very difficult, even for quantum computers. Hopefully. And this is currently one of the methods where the most research is being conducted.

impact: Are such methods already in use?

Wiesmaier: They are already standardised, respectively approved, and lots of experiments are being conducted with them.

Krauß: Our colleague Bo-Yin Yang from Taiwan, who helped us to organise the workshop, is pioneering some of these new methods that are now being standardised. In his talk, he presented ways to programme lattice-based algorithms with mathematical tricks in a way that makes them more efficient and compensates for the disadvantages I described before.

impact: How much of that is trial and error? At the end of the day, will only practice show whether a new algorithm is secure or not?

Wiesmaier: The new algorithms might indeed turn out to be less secure than expected. The standardisation of new security algorithms takes place in the form of global competitions. Various research groups submit their algorithms to a committee. To the National Institute of Standards and Technology (NIST) in the USA, for example, which then selects a handful of “winners” in a multi-stage procedure. On one occasion, it only became apparent very late in the process, shortly before its potential standardisation, that an algorithm was completely insecure.

impact: How much time have we got until the first “super quantum computer” arrives and upsets the apple cart?

Krauß: That is difficult to say. Even quantum computer experts cannot agree – perhaps somewhere between 2033 and 2045. To be prepared, NIST has already published a timeline for the transition to post-quantum cryptography. In it, the algorithms RSA-2048 and ECC-256 are classified as “deprecated” – obsolete – from 2030 onwards and banned altogether as of 2035. If you think about systems or products with long lifetimes, such as cars, there is not much time left. And the problem I mentioned before of “harvest now, decrypt later” also leads to time pressure.

Wiesmaier: For 25 years I’ve been hearing that the quantum computer will be here in 20 years. It is indeed already here, but not yet on a “dangerous scale”. But advances in the field are clear to see. I think 20 years is still a good estimate.