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.