TCR (Taurus Cybersecurity Research)

This is the first of the series about post-quantum cryptography (PQC), or more specifically, the migration from conventional cryptographic algorithms to PQC algorithms.

About the security of cryptography

First, there are two distinct categories of cryptographic algorithms (encryption, signature, and key sharing).

• Symmetric cryptography
• Public-key cryptography

Between these two, symmetric cryptography is the more intuitive and has existed well over centuries from the Roman period. In this scheme, the key to encrypt and decrypt messages is the same – just like your house key to lock and unlock your front door – very straightforward. The underlying assumption in communication systems is that both the sender and receiver of the message share this key over some method. The Advanced Encryption Standard (AES) was standardized by the National Institute of Standards and Technology (NIST) in 2001, and is the most widely used symmetric encryption algorithm today.

On the other hand, public-key cryptography is a quite new concept (which emerged only in 1976!) in which different keys are used to encrypt and decrypt messages. In the house key analogy, the key to lock and unlock the door are different. It’s a weird concept to the extent that nobody thought something like that could be possible (until 1976 when the famous Diffie-Hellman paper came out). This involves two keys: a public key and a private key. As the name implies, a public key can be publicly shared with anybody. But the corresponding private key is only kept by its owner and is never shared with anybody. In communication systems, senders encrypt messages using the public key, and the receiver (the owner of the public/private key pair) decrypts them using the private key.

The security of public-key cryptography is hinged on the secrecy of the private key – if it is broken, then anybody can impersonate as the legitimate owner of the key. RSA, Diffie-Hellman key exchange, El Gamal, and Elliptic Curve Cryptography (EEC) are the types of public-key cryptography.

The fundamental characteristic of public key cryptography is that it is based on the difficulties of some mathematical problems. Specifically oneway-ness of certain mathematical operations and the difficulties associated with doing the reverse operations are essential building blocks. The bottom line is that, if it takes an extremely long time to reverse the operation (say, the most powerful computers still require 1000s of years or more to do the necessary calculation), then we consider the algorithm is effectively secure, in practice. This is a relative term – it is still possible in theory, which is safeguarded by the limitations of existing (most powerful) computers. In other words, if this assumption no longer holds, then this security tenet falls apart.

Such mathematical problems are: (1) factorization of large numbers (RSA, Diffie-Hellman), and (2) discrete logarithm problem (Diffie-Hellman, El Gamal, ECC). We will discuss details of these algorithms in a separate blog. For now, we limit our discussion at a very high level.

1. Factoring large numbers

If we have two integers, $p$ and $q$, multiplying them is trivial, i.e.,

We all know how to do it. Even if both of these numbers are large, it is still possible to calculate them, albeit it quickly gets tedious and time-consuming if you do it by hand (but still easy for computers). On the other hand, factoring an integer becomes very time-consuming and “hard” as the number gets bigger. For example, factoring 143 can be done in the head without even using a pen and paper (11 x 13), but factoring 477,568,881,191 is much harder and certainly time-consuming (477,577 x 999,983). We wouldn’t even bother trying if we had only a pen and paper, and doing it in the head is out of the question. Imagine how you’d even consider factoring over 600-digit decimal number (that is the number represented by a 2048-bit binary number).¹ The same thing applies even to a computer – factoring a large number becomes very time-consuming as the number of digits goes up due to the absence of an effective and fast algorithm to factor large numbers.

2. Discrete logarithm problem

Another oneway-ness is what’s called discrete logarithm problem. It’s expressed in the following equation involving modular arithmetic.

where $n$ is a large prime number and $a$ and $x$ are defined in such a way that $a$ is some number less than $n, (i.e.,\, a<n)$ so that the value of $x$ is big. In this equation, if you know $a, x$ and $n$, it’s trivial to calculate $c$. However, it is difficult to calculate $x$ (a large number) given $c, a$ and $n$. A part of the difficulty is due to the modular arithmetic (i.e., $(mod\, n)$ part), which “hides” how many times the value of $a^x$ wraps around $n$. To test all values of $x$ in a brute-force manner becomes a time-consuming task if $x$ is a big number.

Enter quantum computers

Now the bad news is that the assumed security of these 2 “hard” problems is in danger when sufficiently-powerful quantum computers become reality. Quantum computers already exist today. But solving these problems involving very large numbers is expected to take significantly more powerful quantum computers. The size of some of today’s quantum computers is supposedly somewhere up to 10,000 physical qubits. But physical qubits are quite fragile, error-prone, thus unreliable for practical use. So they need to be converted to more stable and reliable logical qubits with error correction in order to be usable in practice. The level of logical qubits today is supposedly around the area of <100.

Shor’s algorithm, published in 1994, has shown that quantum computers can factor large numbers in polynomial time. This effectively means that algorithms that rely on the “hard” problem are no longer secure in the face of quantum computers. This is a big paradigm shift – the tenet of what’s been considered as “extremely time-consuming calculation that can take 1000s of years or more” collapses. Thus, the presumed security no longer holds with the combination of a sufficiently powerful quantum computer running Shor’s algorithm.

“Store now, decrypt later” (SNDL) or “Harvest now, decrypt later” (HNDL) attack is already an immediate concern, especially in communities that handle extremely sensitive information, such as governments, military, intelligence, etc. In this case, the idea is for adversaries to capture and store encrypted data (messages, etc.) even though they cannot decrypt them today, but can decrypt them in the future when such powerful quantum computers become available.

Of course, there is a big question of when such sufficiently powerful quantum computers will be widely available. The answer depends on who you ask, as there is no commonly agreed-upon timeline. But the security community wants to stay ahead of the game, and has been defining new cryptographic algorithms that are secure even when such powerful enough quantum computers become a reality. In fact, in 2016, NIST started a competition-like selection process to select post-quantum cryptography (PQC) algorithms. And they have selected several algorithms in 2022.

What about symmetric cryptography?

As mentioned earlier, both factoring-large-numbers and discrete logirithm problems are used in public-key cryptography algorithms. What about symmetric cryptography? In symmetric cryptography, the security hinges on the difficulty of cracking the encryption key. The simplest approach is to try every single key value until you find the right one – a so-called brute force attack. The average number of trials to find the right key is $n/2$, ($n$ being the key size) i.e., on average, you need to try half of all the possible key values until you hit the right one. On the other hand, the most well-known efficient algorithm to accelerate this search is called Grover’s algorithm, which effectively reduces the time to crack large-size key to $\sqrt[2]{n}$ (instead of $n/2$). This effectively reduces the security level to half of the key length. This implies that you simply need to double the key size to maintain the same level of security even with quantum computers. In other words, to maintain the same security protection by 128-bit AES, you simply need to change the key size to 256 bits. Because of this situation, quantum computers do not pose immediate threats to symmetric cryptography.

In our next blog, we will cover some more background about the details of these mathematical “hard” problems.

1. Incidentally, the number of grain of sands on earth is supposed to be in the order of $7.5×10^{18}$, i.e., only an 18-digit number!