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 hard 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 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 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.
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 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.
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. Thus, 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 enables them 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. 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 second phase and according to NIST's timeline draft standards will be available around 2022-2024.
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 have started a project to use 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 with less computing power.
That's why Tutanota has started a research project, called PQmail, to implement post-quantum cryptographic algorithms in the encrypted email and calendar application Tutanota.
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.