Testing the Chinese satellite Micius before it was sent into space in 2016 to carry out experiments in quantum cryptography. | Image: IMAGO/Xinhua

“It’s time for harvesting”, says Vadim Lyubashevsky. But he’s no farmer: he’s a cryptographer at IBM Research in Rüschlikon just outside Zurich. Right now, huge silos are being packed full of data – data that can’t be read because they have been encrypted and made inaccessible. Nevertheless, they’re still being stored, because it is possible that they could become readable in the near future, thanks to quantum computing. “Government intelligence agencies in particular started collecting encrypted data a long time ago”, says Lyubashevsky. “I’m 99.9% sure of it”. In short: things are serious.

As soon as quantum computers really get going, most IT security systems will collapse. Almost any encryption that is currently in use could then be cracked. “Our privacy is under threat”, says Serge Vaudenay, a cryptography expert at EPFL. “If we do not replace current cryptographic systems, the consequences will be catastrophic”.

All encrypted messages, personal health data, confidential documents from both companies and public authorities, as-yet unpublished patent applications from industry, reports by the military and by intelligence agencies – all of them would be more or less freely readable. Even bitcoins could be stolen. “It’s actually already too late to protect information that was encrypted and sent yesterday”, says Nicolas Gisin, a physicist at the Schaffhausen Institute of Technology SIT and a cryptography expert. It’s a ticking time-bomb. This is why researchers have been working on post-quantum cryptography for several years.

Almost all the important information that we exchange on the Internet and using our smartphones is encrypted so that it can’t be read by anyone who is unauthorised. Hackers and intelligence services try to circumvent this protection by using malware, for example. Until now, those of us who are cautious enough have remained well protected. But as soon as intelligence agencies like the NSA in America are able to crack these codes with innovative computers, they will be able to read everything that is stored in their huge data silos.

Difficult math

IT security systems that are based on so-called asymmetric cryptography are particularly susceptible to being cracked by quantum computers. In this form of cryptography, encryption is carried out by means of a publicly accessible key. A secret key is only required for decrypting the data. This means that a message can only be read by those people who have the necessary key. The underlying algorithms are based on mathematical problems that cannot be solved in a reasonable amount of time by conventional computing systems, not even if an enormous amount of computing power is employed for it. The so-called ‘RSA method’ is the one most commonly used at present, and it’s currently employed to ensure the security of electronic commerce, for example. But it is particularly susceptible to being cracked by quantum computers.

The RSA method was developed by the researchers Leonard Adleman and Ronald Rivest from the USA in collaboration with the Israeli cryptographer Adi Shamir. Their algorithm is based on breaking down large numbers into their prime factors. At present, they have as many as 700 digits. “These numbers are not a secret”, says Gisin. “But a spy or hacker can’t find their factors so easily because no classical method is known yet that could solve the task efficiently”. It would take several thousand computer years.

But they are easy to crack with quantum computers. Ever since the American mathematician Peter Shor demonstrated a method for quantum computers to carry out factorisation very quickly, it has become obvious that the most important mathematical operations on which today’s asymmetric cryptographic methods are based will in future be able to be solved in real time.

From prime numbers to multidimensional lattices

In 2016, the US National Institute of Standards and Technology (NIST) launched a competition for standardising quantum-computer-resistant cryptographic methods. Researchers from Switzerland also took part, including Vaudenay and Lyubashevsky. In July 2022, NIST selected four out of the roughly 80 methods that had been submitted.

One method is used for encryption, while three are used for generating digital signatures for authentication purposes. The technology of three of these four new standards is based on so-called lattice encryption. Mathematicians have been working on this for centuries. In two-dimensional terms, one might imagine them as a kind of fence with cross slats; in higher dimensions they become complex grids that can only be described properly using mathematics. Cryptographers are currently working in more than 500 dimensions. Their task now is to find the grid point in a high-dimensional lattice that is closest to the zero point. “This problem is extremely difficult to solve”, says Lyubashevsky. So it’s a perfect task for cryptographers.

The biggest challenge these researchers face is translating such a problem into an algorithm that can both encrypt information quickly and not be very prone to error. For years now, Lyubashevsky has been successfully developing such lattice solutions in his research projects ‘Felicity’ and ‘Plaza’. “We’ve been using the new algorithms for protection on the IBM servers for a year now, in parallel with traditional encryption techniques”, he says.

Large tech companies such as Amazon, Paypal and Google have also been adopting these standards because they provide better protection for digital communication. Companies like these with their trade secrets are very much at risk. Experts believe it will become absolutely necessary to change the algorithms for all data by around 2030. Lyubashevsky is convinced that the speed of this switch to post-quantum cryptography technologies will be driven primarily by commercial needs. “We tend to concentrate resources where the economic threat is greatest”, he says. In any case, these new standards from the USA will become a core aspect of IT security, also in Europe. China is said to have copied these standards already.

Encryption with quantum technology

But no one can be absolutely sure that these methods will really do what people hope. This is why some researchers, including the Geneva-based Gisin, believe that a different approach is more sensible. For him, quantum cryptography is the thing. The idea is that if quantum technology can crack encrypted data, then perhaps it could also be part of the solution.

Immense progress is being made in this field, especially in generating and securing the exchange of quantum keys. In countries such as China and Korea, researchers are working on the infrastructure of a quantum Internet. Soon, Europe will be joining them. Quantum cryptography would also mean the end of the current strategy of ‘harvest data now, decrypt it later’. This is because quantum information cannot be copied and stored unnoticed. If a hacker tries to do that, the information will be destroyed.

But this method has two disadvantages according to experts like Vaudenay. First, the maximum range for the exchange of quantum keys is currently limited to about 100 kilometres. Beyond this, repeaters would have to be used that would become a weak point in the system. Secondly, this technology cannot be used for authentication purposes – e.g., logging on to make payment transactions or accessing databases or e‑mails. So it will remain a niche application.

When asked if this constant race between encryption and decryption isn’t a kind of vicious circle, Vaudenay says: “No”, and points out that, “we have been able to use asymmetric cryptography securely for 50 years, based on factoring and on discrete algorithms. This is something from which our generation was able to benefit. Perhaps our children will just have to come up with something else”. And Lyubashevsky adds: “I wouldn’t describe it as a race. Cryptography was secure for a long time, and no one could have guessed that quantum computing would bring about a completely new way of doing things”.