INNOVATE

Cryptography: Conventional, Quantum, Post-Quantum

Where cryptography is now, and where it is going

During the last few years, news has appeared more and more often around quantum computers that beat the record of qubits held by a previous quantum computer. While classical computers operate with bits which are either 0 or 1, quantum computers use quantum bits (qubits) which can take both values at the same time. This means that n qubits can store more information than n bits and can also process more data since they can consider a large number of combinations simultaneously. Thus, when a certain level of qubits is achieved, some of the current (conventional) cryptographic algorithms that we use today will be able to be broken efficiently by these quantum computers. That is why we have to prepare by designing new cryptographic algorithms that are quantum resistant.

Considering this new era of more and more advanced quantum computers, we can distinguish three types of cryptography: conventional, quantum and post-quantum cryptography.

Conventional cryptography is all classical cryptography that bases security on mathematical problems that are difficult to solve by conventional computers. For example, digital signatures based on the RSA algorithm offer high security strength because of the impracticality for a conventional computer to efficiently factorize very long numbers. Most of the cryptography used in state-of-the-art systems today is still of this type of conventional cryptography.

Unfortunately, the implemented cryptographic primitives (well-established base algorithms) are susceptible to lose their security strength if the mathematical problem on which they are based becomes efficiently solvable with quantum computers. Operations such as digital signing or encryption, which are seamlessly present in most modern information systems, are susceptible to be broken when a quantum computer with enough qubits is implemented (as it is demonstrated by Shor’s quantum algorithm).

It is also worth mentioning, however, that not all conventional cryptographic algorithms can be efficiently broken with quantum computers. For example, symmetric encryption based on the AES encryption algorithm is not expected to be broken because no algorithm has been found that could facilitate such an action in quantum computers. However, the recommendation in these cases is to increase the length of the symmetric key in order to prevent brute force attacks by quantum computers

Quantum cryptography is the cryptography that uses the principles of quantum mechanics to perform cryptographic operations. The most common example is Quantum Key Distribution, which is used to exchange secrets, and which will help in establishing secure communications with conventional cryptographic algorithms, such as AES. The advantage of this mechanism is that, due to the fact that it is not possible to measure the quantum state without disturbing it, any interception of the secrets sent would be automatically detected and the communication cancelled.

There are other examples of quantum cryptography, such as Quantum Commitments and Oblivious Transfer, but they are still under research and beyond the scope of this post. While quantum cryptography is still very limited, it does not cover all the operations that can be done with conventional cryptography, such as digital signatures or public-key encryption, and, in addition, it requires dedicated infrastructure that it is not easy to deploy.

Post-quantum cryptography is cryptography that can be implemented in conventional computers, but that it is designed to provide its security strength based on mathematical problems that are difficult to solve both with conventional and quantum computers. An example of this is the lattice-based cryptography that allows for the building of several cryptosystems such as digital signatures, public-key encryption and zero-knowledge proofs.

This type of cryptography will have to gradually replace the algorithms based in conventional cryptography which can be efficiently solved with quantum computers. In fact, there is an on-going competition lead by NIST in order to standardize one or more quantum-resistant public-key cryptographic algorithms.

These three types of cryptography show how quantum computing is both a challenge and an opportunity for cryptography. It is a challenge because it invalidates some of the most extended conventional cryptography primitives, but at the same time an opportunity for improving them and also for creating new primitives that otherwise would be impossible to have.

This article was written by Jordi Cucurull, Cryptography Researcher at Scytl.