Post Quantum Cryptography: Why We Need Resistant Encryption NOW.

Quantum-resistant or post-quantum cryptography is our best bet against attacks from upcoming quantum computers to increase security and privacy.

2024-02-09
Now is the time to switch to post-quantum cryptography to keep your data safe from prying eyes.
The rise of quantum computers brings great advantages to our online word, but also great risks to our security and privacy. As the quantum revolution inches closer, the introduction of robust post-quantum cryptography becomes paramount: The new algorithms must be implemented now to safeguard our data from future attacks by quantum computers. In this post we explain the purpose of post quantum cryptography, how post-quantum encryption works and why we need quantum-resistant cryptography already today - and not once the era of quantum computers has started.

The Internet as we know it depends on encryption: confidential communication, secure emails, financial transactions, critical infrastructure - all of these are at risk if encryption can be broken. Today all sorts of players heavily invest in developing quantum computers - for manifold reasons.

These computers promise to bring great advantages to information technology, particularly in combination with artificial intelligence (AI). But quantum computers can also be turned into unprecedented surveillance machines and threaten our cybersecurity: The race is on between quantum computers and post-quantum cryptography!

Quantum computers threaten encryption

Quantum computing and quantum-resistant cryptography 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 computing will bring great enhancements in different areas of information technology.

They do, however, also pose a serious threat to encryption as the asymmetric cryptosystems that are widely used today (RSA, ECC, (EC)DSA and (EC)DH), rely on variants of only two hard mathematical problems that, unfortunately, quantum computing is 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.

Is Elliptic Curve Cryptography quantum resistant?

This means that the respective cryptosystems relying on RSA and ECC can actually be broken.

Popular cryptographic algorithms such as Elliptic Curve Cryptography (ECC) is not quantum-resistant and can be easily broken by quantum computing. It's important to note that ECC as well as PGP encryption based on AES and RSA will be obsoleted in the coming years when NIST's post-quantum cryptography competition has been completed. At best these traditional algorithms will be used in hybrid protocols, combined with quantum secure algorithms.

How much time it will take for an attacker to break RSA and ECC encryption 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.

The race for quantum-safe solutions

"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 cybersecurity threat of quantum computers to confidential and secret communication online.

When will quantum computing 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 is the time to prepare for the quantum revolution with the introduction of post-quantum cryptography.

What is post quantum cryptography?

Quantum-resistant encryption is what we need to develop now! Quantum-resistant encryption can protect your data from the looking threat of quantum computers.

Post-quantum cryptography describes cryptographic algorithms running on conventional computers but relying on mathematical problems that are believed to be too hard for conventional and quantum computers to break them. 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 response to the quantum threat, the global cybersecurity community is actively engaged in a race to develop post-quantum cryptographic algorithms. These algorithms are designed to withstand attacks from both classical and quantum computers, ensuring the longevity of secure communication.

In 2016, the U.S. National Institute for Standards and Technology (NIST) initialized a process to standardize such quantum-safe algorithms. The final result of this NIST post quantum cryptography standard is being awaited eagerly by the crypto community. The process is currently in the fourth - and almost final - 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 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.

Harvest now, decrypt later

The 'harvest now, decrypt later'-strategy threatens all data secured with asymmetric encryption. Sauron's eye will be able to see everything once quantum computers can decrypt your communication.

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. The difference between the current cryptography and post-quantum cryptography is that the new quantum resistant algorithms will be able to fend off attacks from quantum computers - while data encrypted with currently used algorithms will not have the power to resist such attacks.

The threat here is called the harvest now, decrypt later strategy: Data that travels the internet is being collected now, for instance by secret services such as the NSA or other five eye countries, for later decryption.

This threat makes it obvious that waiting whether - or when - quantum computers will be released is no longer an option.

What's the purpose of it all?

The purpose of of post quantum cryptography is to make sure the encrypted data stay secure in the future. As the US government and the NIST have explained: all data encrypted with standard algorithms fall short of achieving this new level of security requirement and post quantum crytopgraphy algorithms must be implemented now. Fortunately, some data can be secured with post-quantum encryption relatively easy as AES 256 (symmetric encryption) is already considered quantum resistant.

This means that any data that is stored on your computer or on a company's system like documents and files can be easily secured with the proven algorithm AES 256. As part of our post quantum cryptography project at Tuta Mail, we have recently updated our encryption algorithms to AES 256, an essential step in offering quantum-safe encryption.

The challenge of asymmetric encryption

It gets more tricky though when you want to encrypt data asymmetrically in a quantum-resistant manner, for instance for encrypted file sharing or for sending and receiving encrypted emails. New post-quantum algorithms for asymmetric encryption and public key cryptography are being researched and tested as you read this.

Many different companies have already started to experiment with quantum resistant asymmetric cryptography in their applications. We at Tuta Mail are pioneering at using quantum-resistant algorithms together with conventional algorithms (Kyber and Dilithium in combination with AES 256 and RSA 2048 in a hybrid protocol) for our asymmetric public key encryption of emails, but also for calendar sharing, sharing of contact lists and future file sharing services.

You can read more on our post quantum secure file sharing project PQDrive here.

In doing so we are following the advice of NIST, the US government as well as renowned cryptography experts such as Lyubashevsky: "If you really have sensitive data, do it now, migrate yourself."

Hybrid protocol to achieve maximum security

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. A hybrid approach is a core requirement as the new algorithms have not been tested in battle yet. Even if the mathematical conclusion that makes these algorithms quantum safe is correct, there could be mistakes in the implementation which can undermine the security.

Therefore, post quantum cryptography algorithms and conventional algorithms have to be combined in a hybrid approach. This is particularly challenging as Tuta Mail must still run efficiently on mobile devices, even when having lower computing power.

We at Tuta (formerly Tutanota) have already completed a research project, called PQMail, to implement post quantum cryptography algorithms in our encrypted email and calendar application in a hybrid protocol. This project has led to the publication of a quantum resistant public key cryptography prototype that uses the finalists of the third NIST round to encrypt emails securely. Now this encryption protocol is being added to Tuta Mail so that soon 10 million users will be automatically upgraded to benefit from the high level of security with post quantum cryptography. They will then be able to send and receive encrypted emails with quantum resistant algorithms - without having to change their workflow at all.

If you want to be among the first to use quantum-resistant encryption for your emails, sign up now for Tuta Mail!

As quantum computers are about to become a reality, we must be one step ahead with post quantum cryptography to keep all data secure - now and in the future!