Post quantum cryptography
4.4 min read

Post-quantum cryptography

Mathematical Problems and Cryptography: A Practical Example

There are very few domains in which one looks for the most challenging problems; the harder they are, the better. Cryptography is one of them. More specifically, we refer to the mathematical problems that cryptographers use when constructing cryptographic primitives, which we then use in combination with other algorithms to encrypt data, sign documents, or guarantee the integrity of files.

To do their job, these cryptographic primitives usually base their operation on the existence of specific mathematical problems that, although very difficult to solve, are very easy to verify once a solution to the problem is known. In these cases, “solving the problem” is what a hacker or malicious user would want to do, while “verifying the solution” is what a well-meaning user of the cryptographic primitive needs to do.

An example of this type of problem, which is already quite widespread, is the factorization of a number: Given two numbers, it is straightforward to multiply them to verify that they give a specific result (a×b=c), but if we know the resulting product of the multiplication, c, finding the two original numbers a and b that we have used to calculate it is a highly complex problem to figure out. This particular problem, and others alike, are the ones that form the basis of today’s cryptographic primitives and, with them, one of the fundamental components of today’s cybersecurity.

The Threat of Quantum Computing for Cryptographic Problems

However, the arrival of quantum computers has brought about a real revolution for these problems. Specifically, some problems that are difficult to solve using a classical computing device are instead much easier to solve when using a quantum computer. Among them, for example, is precisely that of factoring a number into its two prime factors, which is an essential part of the RSA encryption algorithm. This conversion to an easy-to-solve problem allows an attacker with a quantum computer to invert the RSA algorithm and thus compromise the security of all communications made using this algorithm as a cryptographic primitive.

Over the last few years, the search for and development of new mathematical problems has been promoted to avoid the harmful effects of this fact. Although it is still easy to verify that the correct solution is known, finding it in the first place is still a computational challenge that is impossible to solve, both for a classical computer and for a quantum computer. Thus, the existence or not of quantum computers in the future becomes irrelevant: since for these, the problem is also computationally difficult, cybersecurity based on these algorithms remains, in principle, guaranteed.

It is this group of cryptographic primitives for which no computationally effective attack (neither classically nor quantum) is known to date that we call post-quantum algorithms, or PQC. In a sense, they are intended for a stage after quantum computers come on the scene.

The Efficient solution: have a crypto-agile, post-quantum cybersecurity architecture

Actually, many algorithms are not easy for a computer to solve, regardless of whether it is a quantum computer or not. However, it is necessary (in addition to providing guarantees that there is no such advantage) to offer a whole series of characteristics that make them optimal for use in cryptographic environments. With this intention, organizations such as NIST have developed and carried out great efforts in recent years to select the optimal algorithms to be integrated into cybersecurity environments, thus providing the additional layer of protection against quantum attacks that any adequate cryptographic infrastructure should have.

However, the existence of these algorithms is not a panacea that guarantees cybersecurity permanently. The fact that there is no efficient algorithm to solve the problem today does not mean that such an algorithm will not be discovered in the future. Any weakness in the algorithm can (and will be) exploited by malicious attackers. It is even possible that new solving methods and attacks will reduce the cryptographic problem to the category of “easy to solve” and thus exclude it from the list of primitives that can provide cryptographic guarantees.

Thus, the only efficient solution for a cybersecurity environment is not so much to just rely on post-quantum algorithms, but to have a crypto-agile cybersecurity architecture. This fact allows for a quick and efficient change of the cryptographic primitives used while always being up-to-date with the latest trends and developments in cybersecurity. This is the only way to guarantee, to the maximum extent possible, the effectiveness and efficiency of communications cybersecurity.

We mean using cryptographic primitives based on post-quantum algorithms to guarantee the confidentiality, authenticity, and integrity of the data.

We refer to those algorithms used in cryptography that are hard to break, both for a classical and a quantum computer.

They are two fundamentally different things. On the one hand, post-quantum cryptography consists of developing algorithms that are resistant to quantum computers, but the algorithms themselves can still be executed by classical devices. On the other hand, quantum cryptography uses purely quantum phenomena to provide cryptographic guarantees and requires a quantum infrastructure in place to be used.

José Ramon Martínez

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?

RELATED POSTS
There are no active related posts to output to this page