Post-quantum cryptography (PQC)

26 Oct 2023 | Jindřich Zechmeister

Post-quantum cryptography refers to cryptography (encryption) that is resistant to quantum computers. Current cryptography is based on the high complexity of some mathematical problems and the impossibility of solving them using current computers in a reasonably long time (for example, factorization of prime numbers). However, quantum computers break down this assumption and therefore it is necessary to prepare a replacement for the current cryptography in time. One day it will probably be needed. This article will show you how to start preparing for it.

What are quantum computers and how do they work?

It is already clear from the name that quantum computers are a different kind of computer than the ones we use every day. These are referred to as conventional in the context of quantum computers. Quantum computers are the result of shrinking the building blocks of current chips and computers. The typical size of today's transistor, which is the basic building block of computers, is 14nm. This is the size of only a few atoms, and the transistor is thus 500 times smaller than a red blood cell (7 µm). Downsizing is already hitting the current technological limits of production, so scientists are leaning towards quantum computers as a suitable alternative for further development.

Cryptography is based on certain mathematical problems being unsolvable, or more precisely, being unsolvable in a reasonable amount of time. For example, this is how the most widespread RSA algorithm, which relies on the problem of factoring two prime numbers, works. Simply put, when we know the product of two large prime numbers, we are not easily and quickly able to determine the factors, even if we know how to do it.

Current computers know how to break current cryptography, for example using Shor's algorithm to break RSA, but so far there has not been enough computing power available to effectively "break" current ciphers. Therefore, current ciphers are still secure, but this will not last forever. With the advent of large enough power, it will be possible to decipher them in a fraction of the time it takes today.

Simply put, quantum computers are not universal computers as we know them from the home and office, but focus on specific calculations and tasks that they solve using special algorithms. Their basic information unit is qubits, which are particles that can be in multiple physical states at the same time (superposition). For a basic understanding of the principle of quantum computers, I recommend watching the short video below.

 

The video clearly shows that a qubit does not have to be only in the state 0 or 1 as a bit, but with a certain probability is located anywhere between the mentioned states and can even be in both states at the same time. The main advantage of qubits for use in quantum computers is that they can be used to perform calculations in parallel, and this parallelization increases with the square of the number of qubits in a quantum computer. Conventional computers calculate tasks sequentially (step by step) and therefore more slowly. For example, 4 bits can achieve 16 configurations and we can use them to represent just one of them. In contrast, four qubits in superposition can achieve all 16 configurations simultaneously. Twenty qubits can already have a million values simultaneously (2^20). In specific tasks, such as searching in a database, quantum computers are orders of magnitude faster than current ones - thanks to the parallelization of calculations. This difference can be generalized - the time that a quantum computer needs for a calculation corresponds roughly to the square root of the time that a modern computer needs to solve a problem.

A more precise description of the principle and function of a quantum computer is beyond the scope of this article and, given the complexity of the physics used, beyond the capabilities of the author of the article. For more information about quantum computers and their operation, I recommend, for example, the article Quantum computer. For those interested in news and developments in this industry, I recommend the dotquantum.io blog. More on the mathematics behind it can be found for example in Wikipedia..

Cryptography for the future

As already mentioned in the introduction, cryptography resistant to quantum computers is called post-quantum cryptography, and in the English language (and later in the article) the abbreviation PQC (post-quantum cryptography) is used. New algorithms are created with the future in mind, but currently it is still safe to use current algorithms as long as they have an appropriate key length.

The need to address PQC (as a replacement for current encryption) is relevant today with a view to the future - mainly because attackers would want to crack recorded communications in the future, when they have better equipment at their disposal. This is a risk that needs to be treated today, even though quantum computers are not yet in mass use and do not directly threaten current encryption.

A number of encryption algorithms for PQC are known, and of course the best of them have a chance to be used in real life. The standardization of new PQC algorithms has been ongoing since 2016 at the American NIST office, so we already have a choice of quantum-resistant algorithms to use today, and more to come. More information about the first NIST-standardized cryptographic algorithms can be found in the article on the DigiCert blog. These are specifically these:

For general encryption (Public key encryption)
• CRYSTALS-KYBER

For digital signature:
• CRYSTALS-Dilithium
• Falcon
• SPHINCS+

For a complete overview of PQC standardization, see the NIST Post-Quantum Cryptography Standardization Wikipedia article.

Although standardization has begun, the use of PQC is not yet common practice, and current certification authorities do not yet issue production quantum-resistant TLS certificates. Testing using common software versions is not yet possible, as PQC is not extended in them. However, we can provide you with pre-production PQC today thanks to DigiCert.

DigiCert lets you test PQC today

The world's largest commercial CA must constantly think ahead and prepare for the challenges of the coming decades. With DigiCert, you can be sure that you will be ready for the transition to PQC. You can already "touch" PQC within the Secure Site Pro products. It is already possible to create a hybrid RSA/PQC certificate that will combine the current conventional cryptography with the new post-quantum one. Potential interested parties can find more about the PCQ toolkit in the article PQC toolkit setup guide.

Testing consists of patching and compiling a modified version of OpenSSL, generating PQC keys and generating a hybrid certificate and its chain, i.e. intermediate and root PQC CA. The hybrid certificate will use ECC and PQC and you can use OpenSSL to test it on your server using the s_server and s_client utilities (Chrome from version 116 should support PQC as well). Hopefully, it is obvious that this solution is not intended for production.

The sufficient security of current cryptography should be evaluated periodically, and the easiest method is to check experts‘ recommendations. In the USA, follow the official recommendations of the NIST, which periodically issues them and determines both suitable cryptographic means for the present.

Sources and other information:

• DigiCert Blog: DigiCert Announces Post-Quantum Computing Tool Kit. Available at: https://www.digicert.com/blog/digicert-announces-post-Available at: https://cs.wikipedia.org/wiki/Postkvantov%C3%A1_kryptografie.
• Wikipedia: NIST Post-Quantum Cryptography Standardization. Available at: https://en.wikipedia.org/wik/NIST_Post-Quantum_Cryptography_Standardization.
• Wikipedia: Quantum cryptography. Available at: https://en.wikipedia.org/wiki/Quantum_cryptography.

---