Credit cards and exchange security: towards post-quantum cryptography

Computers are very useful companions: they solve many problems that we face. Fortunately, there are also problems out of reach for them. Let us think of our credit cards: it would be problematic for a computer to be able to find our code… This is precisely the threat now posed by the quantum computer, a new type of computer currently being designed and based on the laws of quantum physics.

Fortunately, this new computer does not mean the end of security related to our credit cards, and more generally digital security. There are indeed difficult problems even for a quantum computer. Post-quantum cryptography precisely proposes to study and exploit them in order to ensure our digital security of tomorrow!

Cup, algorithms and cryptography

Our lives today are punctuated by computers. The reason for the success of these modern machines is quite simple: they help us quickly solve many everyday problems. For example, given a road or geographic map, how do you find the shortest way to get from point A to point B? The answer is ultimately quite simple: let’s ask our smartphone the question! These little computers can calculate “all” possible paths very quickly and therefore respond to us instantly. From then on, it is only a step away from thinking that our companions can solve almost any imaginable problem…

Unfortunately, it is not. Computers are even extremely quickly limited. Take a cup of coffee falling from our hand one morning. Will our smartphone be able to predict how many pieces our favorite cup will break into? The task seems difficult, even with a dedicated application. Indeed, carrying out such a simulation would require far too much time from our telephone and even a supercomputer would not be enough: the number of dimensions involved in this problem is far too high.

Nor is the solution to be sought in technological development. Even if we exceed the expectations of the famous Moore’s Law (which predicts a doubling of our computing power every two years), we would still have to wait hundreds of years before being able to give a satisfactory answer to our problem. Conversely, we have a simple way to answer it without resorting to technology: just bend down and count the pieces. An exercise certainly tedious, but which seems in our cords…

This cup metaphor is inspired by a video by Richard BorcherdsFields Medal, in response to recent announcements of quantum supremacy, that is to say the realization by a quantum computer of a task inaccessible to a classical computer (which we will discuss a little later).

However, the fact that there are problems that a computer, and even all terrestrial computers put together, cannot solve in a reasonable time is the founding principle of much of modern cryptography, science secrecy allowing us digital security. There are plenty of problems that are presumed to fall into this category, the most famous in cryptography being the so-called factorization of integers and discrete logarithm. A whole section of digital security is based on their difficulty, such as credit cards, our software updates, etc.

The Pitfall of Quantum Computers

Unfortunately, advances in quantum physics suggest the arrival of a new tool that could upset the established order: the quantum computer. This “new generation” computer, having little to do with our computers, would work by replacing bits, those 0s and 1s that constitute the universal language of all machines around the globe, by qubitsobjects resulting from the principles of quantum physics and which represent both a 0 and a 1 in “superposition”.

This fundamental difference offers powerful new algorithmic possibilities, as demonstrated by P. Shor in 1994, by proving that a functional quantum computer (i.e. a set of qubits on which one would be able to perform a certain number of predefined operations) was able to solve the problems of factorization and logarithm discrete far more effectively than a conventional computer ever could. Goodbye our credit cards! Since then, other areas where quantum computers could prove revolutionary have been discovered, more positively this time. This is for example the case of chemistry where quantum calculation could make it possible to improve the modeling of the states of a molecule.

Interior of a quantum computer.
IBM Research/Flickr, CC BY-ND

Today, we are still far from having a working quantum computer : these famous qubits are difficult to handle and the road is still long both theoretically and practically. The announcements of quantum supremacy we were talking about earlier, i.e. performing a task with a quantum computer that is beyond the reach of our day-to-day computers, were actually about problems that had been specially designed for the very purpose of being easier for a quantum computer than for a classical computer. The promising applications of quantum computers, for example breaking our digital security, remain for the moment beyond the reach of the most advanced players.

The efforts invested in the pursuit of quantum supremacy are, however, up to the task, and a real race is launched between the big players in the field, such as Google or IBM. The threat is therefore not to be taken lightly for cryptographers: we could well see the arrival of a functional quantum computer within ten years.

Post-quantum cryptography

“So is this the end of cryptography? we might then ask ourselves. Fortunately, the answer to this question is probably no. Because just like classical computers, quantum computers are not all-powerful. This is precisely the postulate on which a new branch of cryptography is based: post-quantum cryptography. This one aims to study new mathematical problems which would be hard at the same time for the classical computers, but also for the quantum computers.

Recently, the NIST, American standardization institute, launched a competition with the aim of identifying and standardize promising candidates. After several successive skimming rounds, the competition will soon come to an end and the announcement of the first solutions subject to standardization should fall in the coming months. From the multitude of initial proposals emerged several large families, the most notable of which are undoubtedly the cryptographies based on Euclidean networks and correcting codescombining efficiency, compactness and good experience of the underlying mathematical problems.

However, in both traditional and post-quantum cryptography, nothing is set in stone. We cannot exclude the possibility of seeing, tomorrow or in six months or a year, a group of individuals arrive with a new algorithm which would make it possible to break a problem on which post-quantum cryptography is based. We had proof of this recently with one of the finalist protocols in the NIST competition, the security of which has just been seriously questioned by a new offensiveproving that the digital security induced by such a system would not be guaranteed.

This is all the more true as post-quantum cryptography must guard against an even more serious threat: quantum computers themselves! But we are far from having understood all the possibilities of these new machines. This justifies the need to have fallback solutions and this is why other families of mathematical objects such as systems multivariate or isogenies are also closely studied.

In summary, establishing our future digital security still raises many questions! As illustrated by the NIST call, scientists are hard at work delivering solutions that are both safe and effective, ready to be deployed on our computers and smartphones within the next few years.

We would like to thank the writer of this short article for this incredible web content

Credit cards and exchange security: towards post-quantum cryptography

You can find our social media profiles here as well as other pages on related topics here.