Post-quantum cryptography: protecting today's secrets against tomorrow's attacks

September 22, 2020

Quantum computers present a major potential threat to our data. How can post-quantum cryptography come to the rescue?

Source: Shutterstock
Source: Shutterstock

Researchers around the world, including here at TU/e, are working hard to build a quantum computer. It promises extremely speedy computing, enabling fast solutions for problems that would literally take ages for a supercomputer. Quantum computing is however a double-edged sword: it threatens to break all cryptographic security mechanisms that currently protect our sensitive communications and data. Researchers at TU/e are working hard to come up with smart solutions for this urgent problem. Post-quantum cryptography is one of them. In this Q&A we explain this exciting research in five questions and answers.

why are quantum computers a problem for the security of our data?

The security of our digital communications and data depends on the use of cryptography. Quantum computers threaten especially public-key cryptosystems, such as RSA, DSA, and elliptic curve cryptosystems. These cryptosystems are used to implement public-key encryption and digital signatures.

Although these cryptosystems work fine for much of our digital communications, they are vulnerable. They rely on hard mathematical problems, such as integer factorization, which are virtually impossible to crack for conventional computers, but which can easily be solved on a powerful quantum computer, as they can do multiple calculations at the same time (see info box on quantum computers below).  Current quantum computers still lack the processing power to accomplish this task, but this may change anytime soon.

What makes matters worse is that encrypted text intercepted today, can be decrypted by an attacker once they have a large quantum computer. According to Tanja Lange, researcher at TU/e and a leading authority on post-quantum cryptography, this means that any data that needs to remain confidential after the arrival of quantum computers should already be encrypted in a way that quantum computers cannot crack. “In other words: we need to protect today's secrets against tomorrow's quantum attackers,” says Lange.

 

About quantum computers

A conventional computer performs operations using bits, which can be either zero or one. A quantum computer uses quantum bits or qubits. Qubits can be photons, or electrons, or any system that can exist in so-called quantum states. What is cool about quantum physics is that these states can co-exist at the same time.

This so-called ‘superposition’ allows you to hold much more information in comparison to the bits in conventional computers. Whereas two classical bits can exist in one of four possible combinations (22), qubits can exist in all these combinations simultaneously. This number grows exponentially with each additional qubit. Twenty qubits can already store over a million values in parallel (220), and 300 qubits can store as many particles as there are in the universe (2300).

Despite this immense computing power, it is unlikely that quantum computers will ever fully replace conventional computers. This is due to the peculiar effect of measurement on qubits: once they output an answer, all other information associated with their superposition is lost. Still, quantum computers excel in operations where there is a need to do many calculations concurrently, such as for simulations to develop new drugs and better car batteries and for financial modelling. They are also very good at breaking cryptographic codes, which is a major and urgent problem for the security of our data.

More about quantum computers in this videoclip from researchers at Google.

Information about current research on quantum technology at TU/e can be found on the website of the Center for Quantum Materials and Technology Eindhoven.


What is post-quantum cryptography, and how can it help?

One way of making our current computers and data ‘quantum-proof’ is with so-called post-quantum cryptography. Researchers at TU/e and at other universities and companies around the world develop algorithms that can withstand attacks by hackers equipped with a quantum computer and are usable for today’s devices, like smartphones, laptops and bank cards.

At present there are four established possible solutions: code-based, hash-based, lattice-based and multivariate-system based algorithms. All involve hard mathematical problems that, in contrast to the factoring-based and other algorithms currently used in public-key systems, cannot be solved efficiently by a quantum computer.

Lattice-based solutions are seen as one of the most promising, and also form the basis of the NTRU algorithm co-developed here at TU/e and field-tested last year by Google and Cloudflare. Among others, NTRU was selected by Google because of its provable security guarantees. This proof was co-authored at TU/e by assistant professor Andreas Hülsing. It is no co-incidence that Hülsing is also the author of another promising solution called SPHINCS+ which is consistently praised for its reliable security guarantees. 

The basic concepts for these systems date back to the last century, but over the last 5 to 10 years, professor Lange, Hülsing and others at TU/e have analyzed these concepts and turned them into practical cryptographic solutions. An important aspect of this work is proving the security of these cryptographic systems, to ensure that they can resist quantum computer based attacks.

 

When will we have a definite standard for post-quantum cryptography?

NIST, the US National Institute of Standards and Technology, launched in 2017 a multi-year competition to select the best solutions for post-quantum encryption and signatures. The winners will become the new standards, and will be adopted by governments and industry across the world. In the summer of 2020, the competition, which began with 69 entries, entered its third round. For this round, NIST selected seven finalists, including two from TU/e researchers.

In addition, NIST has selected eight so-called alternate candidates, again including two from TU/e. These solutions are considered as potential candidates for standardization, potentially after a fourth round.

The finalists will now undergo a final evaluation round, in the run-up to which the participants have the opportunity to further ‘tweak’ their algorithms. NIST expects that the whole process will be concluded within the next two to four years.

So, What can i do about it?

In 2019, researchers at Google managed to make a quantum computer with 53 qubits that was able to do an extremely difficult mathematical calculation in an amazing 3 minutes and 20 seconds. They estimated that IBM’s Summit, the largest supercomputer, would need more than 10,000 years to accomplish the same task.

An impressive (and contested) feat, but observers agree that a quantum computer that can do useful stuff in the real world, is still some years off, mainly because of the fragility of qubits (see info box). So far, quantum computers are also very expensive, limiting their practical use.

“Still, the switch to post-quantum cryptography is very urgent,” says Lange, “especially for data that needs to remain confidential after the arrival of quantum computers. So, if an attacker could gain access to your encrypted data, and that information needs to remain secret for the next 10 years, you should upgrade your encryption systems now with the most secure system. You don’t need to wait for the conclusion of the NIST competition. Start preparing now. You can always re-encrypt it with a more efficient system once that has received enough scrutiny, but you can never undo leaking weakly encrypted secrets.”

The most practical solution, according to Lange, is a hybrid one. “This combines a post-quantum system with one of the currently common public-key systems in a way that is as strong as the strongest of the two. This makes the transition and possible auditing easier.”

Where can I find more information?

For more information about the work of Tanja Lange, Andreas Hülsing and their colleagues, check out the page of their research group Coding Theory and Cryptology.

For general background on post-quantum cryptography, http://pqcrypto.eu.org/ is a good place to go. Detailed information on the TU/e NIST submissions can be found here:

TU/e has also organized several trainings on post-quantum cryptography at various levels, see https://pqcschool.org/ and https://2017.pqcrypto.org/school/index.html.

Media contact

Henk van Appeven
(Communications Adviser)