Why we need quantum-resistant cryptography now.

Quantum computers threaten encryption

Quantum computing will change information technology in a way that we have never seen before.

Past research has yielded various quantum algorithms to efficiently solve different problems that are considered too difficult today. Due to that ability quantum computers will bring great enhancements in different areas of information technology.

They do, however, also pose a serious threat to cryptography as the asymmetric cryptosystems that are widely used today (RSA, (EC)DSA and (EC)DH), rely on variants of only two hard mathematical problems that, unfortunately, quantum computers are able to solve significantly faster: the integer factorization problem and the discrete logarithm problem.

With Shor's algorithm (1994) running on a universal quantum computer both problems become solvable in polynomial time.

This means that the respective crptosystems relying on RSA, (EC)DSA and (EC)DH can actually be broken.

How much time this will take for an attacker depends on the capacity of the quantum computer. According to a study by the German Federal Office for Information Security (BSI) about 1 million physical qubits are needed to break 2048-bit RSA in 100 days and about 1 billion qubits to break it within an hour. Advances in algorithm design will further reduce these numbers.

"This means that quantum computers have the potential to eventually break most secure communications on the planet," says cryptographer Rafael Misoczki. The race is on to create new ways to protect data and communications to combat the threat posed by large scale universal quantum computers.

For instance, US federal agencies like the FBI and NSA are already required to adopt post-quantum security, and the private sector is being advised to follow. This requirement is part of the National Cybersecurity Strategy released by the Biden administration in March 2023. It is obvious that policymakers have already understood the threat of quantum computers to confidential and secret communication online.

When will quantum computers become a reality?

To date, no practical quantum computer has been developed. However, quantum computing is a very active research field and fast progress has been made in the past, particularly in most recent years.

Advances in quantum computing are announced regularly by big companies such as IBM, Google and Intel. These computers however operate on only about 50 -70 physical qubits. According to the mentioned BSI study, a quantum computer capable of breaking today's cryptosystems will not become a reality in the short term.

However, the revelations of Edward Snowden made it obvious that encrypted data is stored by different actors already today. It is high time to ensure that these actors will not be able to decrypt it years in the future, when large scale universal quantum computers will have been build.

In addition, quantum computing is no longer a distant possibility, but already a reality. The Riken research institute in Japan has announced it will make the country’s first domestically built quantum computer available online for several businesses and academic institutions. Riken plans to connect this quantum computer prototype to the world’s second-fastest supercomputer, Fugaku, by 2025, in order to expand its real-world use cases, including research related to materials and pharmaceuticals.

This is not an isolated development, but part of what looks like a quantum computing “arms race”. According to Japan's Science and Technology Agency, over the past three decades China has registered the most patents worldwide for quantum computing, approximately 2,700, followed by the U.S. with roughly 2,200 and Japan with 885.

It’s clear that the world is on the verge of a technological revolution with the emergence of quantum computers, which promises unprecedented processing power and the ability to solve complex problems that classical computers cannot.

While this is exciting, it will also pose a threat to current encryption protocols, which could be easily broken by quantum computers, leaving sensitive information exposed to attackers. This is why the U.S. National Cybersecurity Strategy is calling for the transition to post-quantum cryptography, which uses algorithms that are resistant to attacks from quantum computers. The strategy recognizes the need to prepare for the future and ensure that encryption protocols remain secure in the face of evolving threats.

While the possibility of a quantum computer successfully breaking current end-to-end encryption protocols is not expected to become a reality in the immediate future, it is important to work on preventing this type of threat as soon as possible, because efficient solutions take time to develop.

How quantum computers work

Ordinary computers store data as 1s and 0s. Whereas quantum computers use qubits to store data. Each qubit is in a superposition of 1 and 0. Measurements project one of these states with certain possibility. This possibility is changed by the quantum algorithm. Because each qubit represents two states at once, the total number of states doubles with each added qubit.

Thus, one quibit is two possible numbers, two qubits is four possible numbers, three qubits is eight possible numbers. Since the coronavirus pandemic, we all understand exponential numbers. We can get an idea of how powerful a quantum computer with, let's say 100 qubits, could be. A quantum machine with 300 qubits, for instance, could represent more values than there are atoms in the observable universe.

About 20 years ago, researchers in Japan pioneered superconducting qubits: They cooled certain metals to extremely low temperatures to reach a stable working environment for quantum computers.

This method was so promising that it triggered research projects at Google, IBM, and Intel.

The actual quantum computers do not look like ordinary computers at all. Instead, these are large cylinders of metal and twisted wires, which are dropped into large refrigerators. Researchers send information to the machine and receive calculations in return, just like with ordinary computers.

IBM even lets external researchers buy computing power on their Q System One. This enables researchers around the world to use a quantum computer without ever seeing or touching one for real.

Their inherent parallelization of computation on all states simultaneously will enable these powerful computing machines to break currently unbreakable encryption.

Why we need encryption

Encryption is all around us when we use the Internet. It is an integral part for any digital process that needs confidentiality: communication, finance, commerce, critical infrastructure, health care and many more areas of our daily life are protected with strong encryption. When the cryptographic algorithms used in these processes become breakable due to the development of large scale universal quantum computers, attackers with access to such computers can threaten many aspects of our every-day life.

The Internet as we know it only works with unbreakable encryption. Now it the time to ensure that the encryption we are using today remains unbreakable in the future.

Developing post-quantum cryptography

Post-quantum cryptography describes cryptographic algorithms running on conventional computers (as opposed to quantum cryptography running on a quantum computer) but relying on mathematical problems that are believed to be hard for conventional and quantum computers. As long as there is no efficient quantum algorithm that solves exactly these problems more efficiently, we can assume that they cannot be broken by quantum computers.

In 2016, the U.S. National Institute for Standards and Technology (NIST) initialized a process to standardize such quantum computer resistant algorithms. The process is currently in the fourth phase of evaluating standard algorithms for post-quantum secure encryption, with the first four quantum-resistant cryptographic algorithms - CRYSTALS-Kyber for encryption and CRYSTALS-Dilithium, FALCON and SPHINCS+ for digital signatures - already being announced.

Getting ready for the quantum computing revolution

Developing and deploying post-quantum cryptography is quite urgent. Even though quantum computers capable of breaking the cryptosystems we use today might not become reality in short term, experience has shown us that rolling out new cryptographic standards takes a lot of time. New algorithms have to be evaluated carefully, their security has to be proven by intensive cryptanalysis and efficient implementations have to be found. For instance, even though Elliptic Curve Cryptography was first proposed in the late 1980s, it has only been adapted for mass usage some years ago.

Deployment of post-quantum cryptography should happen as soon as possible - not only to be prepared when large scale universal quantum computers become a reality but also to protect the data currently encrypted with standard algorithms from being decrypted in the future.

Many different companies have already started to experiment with post-quantum cryptography in their applications. We at Tutanota are pioneering at using quantum-secure algorithms together with conventional algorithms for our encrypted emails and calendars.

As cryptography expert Lyubashevsky says: "If you really have sensitive data, do it now, migrate yourself."

Development of quantum-resistant cryptography

As quantum resistant algorithms are fairly new and their security has not been sufficiently proven, we cannot just replace our current cryptographic algorithms with them. It might still happen that somebody comes up with an attack running on a conventional or a quantum computer that breaks the algorithm we have chosen. Therefore, post-quantum and conventional algorithms have to be combined in a hybrid approach. This is particularly challenging as Tutanota must still efficiently run on mobile devices, even when having lower computing power.

That's why Tutanota has completed a research project, called PQMail, to implement post-quantum cryptographic algorithms in the encrypted email and calendar application Tutanota. This porejct has led to the publication of a prototype that uses the finalists of the third NIST round. Now this encryption protocol is being added to Tutanota so that soon 10 million users of Tutanota will be automatically upgraded. They will then be able to send and receive post-quantum secure encrypted emails - without having to change their workflow at all.

The world of encryption is changing more quickly than ever, and it has never been more important for everyone depending on that encryption to ensure that we are staying ahead of the game!