Quantum Computer and Cryptography
Invisibly, like many of the most relevant technologies that drive the world, cryptography permeates through all current communication systems. The ability to always guarantee that our messages are transmitted in an unaltered form to only those recipients of interest to us, without anyone else being able to read or modify the message, is critical for users to have peace of mind when it comes to relying on the communication channels we use.
Many of these cryptographic systems are not even contemporary: after all, these needs for integrity, authentication, and encryption of messages have existed throughout history. What is undeniable, however, is that the advent of computers, first, and digital communication networks, subsequently, has led to an exponential increase in both the number of existing communication flows and the algorithms that these computers must run to guarantee all the aspects mentioned above of secure communications.
Today, we have a whole series of cryptographic primitives that, combined in the right way, present a real challenge for any malicious party when it comes to breaching our communications: from algorithms that encrypt the data we send, through algorithms that verify the integrity of the files received, to key generation algorithms.
However, it seems that the advent of quantum computing has turned this algorithmic zoo upside down, causing institutions such as NIST to recommend, at the earliest possible moment, the replacement of some of the most widely used algorithms, such as those similar to the RSA key generation process.
What is the reason for all these recommendations?
Does quantum computing really pose a problem? And if so, is there any way to fix it?
To explain it adequately, we must begin by making a statement that might seem contrary to the concept of security: that all these algorithms can be broken using a sufficiently powerful computer and a large enough number of operations. A good cryptographer’s challenge is to design a simple cryptographic primitive that is simple to use, but to invert and break it would require a prohibitive number of computational resources (in terms of time, number of operations needed, memory or storage).
Many of these cryptographic algorithms, in particular the RSA mentioned above, are based on problems such as integer factorization, a problem for which there is no known classical algorithm that does not require an exponential execution time. Because of this exponential time, the inversion of the RSA algorithm is prohibitively expensive, and, therefore, the cryptographic system is secure.
However, one of a quantum computer’s potential advantages is solving the factorization problem in polynomial time using the so-called Shor’s algorithm. Thanks to this (or to blame, depending on how you look at it), what is prohibitively expensive with a classical computer is no longer prohibitively expensive if someone has a sufficiently powerful quantum computer in the future.
Unfortunately, although the quantum computer seems to be a futuristic concept, its effects can begin to be felt in the present: an attacker interested and confident in quantum computing developments could store information encrypted with algorithms vulnerable to this kind of improved attack and proceed to decrypt it in the future when he has sufficient computing power. This process, called “store now, decrypt later,” makes the mere possibility of having a quantum computer even 50 years from now a present-day problem.
To avoid these problems, one way available today is adding new algorithms to our zoo based on a series of mathematical problems that are difficult to solve for both a classical computer and a quantum computer. Despite what it might seem, there are a lot of problems in which the existence of a quantum computer does not noticeably affect their inversion difficulty. Some of them are already recommended by institutions such as NIST to be part of the cryptographic solutions of the future.
However, we must not forget that discoveries can occur at any time: the appearance of algorithms that reduce or directly eliminate the complexity of some of these new post-quantum methods is the order of the day. Thus, rather than marrying any of these new algorithms, the best cryptographic solutions of the future should have the possibility of constantly improving their primitives, always counting on the latest cryptographic improvements and allowing an agile and transparent change for the end user.
A device that performs data manipulation following the laws of quantum mechanics, which are pretty different from the standard rules of classical physics.
Quantum computers are quite a promising platform for many problems in areas such as simulation, optimization, machine learning, or database searching.
A quantum computer can be exponentially faster than a classical computer for some specific problems, such as the integer factorization problem.
José Ramon Martínez
Leader of the computing activities
He got his BSc in Physics from the UCM (Madrid); his MSc in Photonics from the UPC-UB-UAB (Barcelona); and his Ph.D. in Photonics from ICFO, where he worked at the Nanophotonics Theory Group. His research focused on Computational Physics in Nanophotonic systems, publishing 10+ articles in high-profile journals and developing various advanced high-performance computing systems.
Want to hear more about the quantum side?