Post-Quantum Cryptography: What and Why Needs to be Changed Soon?

This article was prepared in cooperation with Microsec Ltd. Check out their blog for more interesting readings!

In this post, we explain the impact of prospective quantum computers on current implementations of cryptographic primitives, including digital signatures.

What is Post-Quantum Cryptography?

The goal of cryptography is to make any unwanted action (like reading a secret message or forging a signature) far more expensive than the benefit of such actions. Naturally, the cost of an attack largely depends on the cost of the tools necessary for the attack, meaning that the possible tools of an adversary must be taken into account in the design phase of every cryptosystem. For a long time, attacks that require a quantum computer were considered to have infinite cost since it is still an active research area being far from practical applications (e.g. for attacking cryptosystems ). At the same time, we cannot ignore the advancement of this field, as by the time the cost of using a quantum computer drops (i.e. it will be available and useful), we must be prepared for attacks that utilize this new tool. This is exactly what post-quantum cryptography (PQC) is dealing with. More precisely, the goal of PQC is to design classical cryptographic algorithms (for traditional computers) that resist both traditional and quantum attacks. It is important to note that PQC stands in contrast to the so-called quantum cryptography (e.g. quantum key distribution) that aims to build cryptosystems utilizing the principles of quantum mechanics. As these latter methods themselves require such infrastructure that is not widely available yet, they cannot be alternatives for the current techniques soon.

Next, we explore the challenges posed by the possibility of the two known quantum attacks.

Symmetric key Cryptography and Quantum Database Search

In cryptography, one-way functions (OWF) play a crucial role. Practically, a function is called one-way if it is easy to evaluate, but hard to invert, i.e. given an output of the function to find an input that is mapped to the same output by the function. Obviously, no encryption function can be secure without this property and the level of security is closely connected to the hardness of inversion. More precisely, a crypto primitive, constructed from a OWF, is said to offer $k$ –bit security if inverting the OWF is expected to take $N=2^k$ evaluations of the function. When the structure of a function does not facilitate its inversion, the exhaustive search for the preimage is the best one can do. This is expected to take roughly $N/2$ invocation of the function, where $N$ is the size of the domain.

Perhaps surprisingly, we are not even sure about the existence of OWFs. We only conjecture that several functions have this important property based on the experience that no one could come up with efficient algorithms to invert them (or at least no one has revealed his or her ability to do so). Complexity theorists call “Minicrypt” the imaginary world, where OWFs provably exist; thus a significant portion of cryptography, roughly symmetric key crypto, can be securely realized regardless of the actual state of the art of algorithm design. The question arises: can we still hope that we are living in Minicrypt after the advent of quantum computers?

Fortunately, the answer seems to be positive. According to a lower bound, any generic brute force quantum attack to invert a function needs to evaluate the function at least roughly $\sqrt{N}$ times. This quadratic speedup over classical brute force is achievable. In 1996, Lov Grover proposed a quantum search algorithm that needs around $\sqrt{N}$ steps to find an element in an unordered database. This method naturally translates to a generic function inversion method with roughly $\sqrt{N}$ function evaluations. Regarding the security loss, any OWF based scheme with $k$ bit classical security will have at least ${k/2}$ bit security if we consider the possibility of quantum search. This is the reason why doubling the key length of a symmetric key cipher (like AES, the workhorse of internet security) or the output length of a hash function is considered as a simple but effective defense. However, it is worth noting that even a quadratic speedup of the attack seems to be too pessimistic for some schemes like the SHA3 hash function due to implementation issues. At the same time, it is important to keep in mind that the lower bound holds only for the generic case. So it does not rule out the existence of other quantum algorithms that invert only specific OWFs but faster than Grover’s method by utilizing their inner structure. This leads us to the second quantum algorithm, that turns out to be a more devastating attack for another branch of cryptography.

Public key Cryptography and the Shor Algorithm

For several cryptographic tasks, OWFs provably do not suffice. These include non-interactive key exchange, public key encryption, but currently used digital signatures are also built on stronger assumptions (however, this is not inherent in the last case as in the other cases). These primitives can be realized using a very specially structured subset of OWFs, called trapdoor functions that are also easy to evaluate and hard to invert, but the knowledge of a “trapdoor” (or “backdoor”) makes inversion easy as well. (Of course, the trapdoor must be hard to find knowing the function. Otherwise, the inversion would become easy.) The corresponding imaginary world, where public key cryptography is possible, is called Cryptomania. While quantum computing also does not seem to rule out this much more appealing world, by now, we know that public key crypto must be drastically different in “Post-quantum Cryptomania” than what we use today.

The (oversimplified) recipe for constructing public key cryptosystems is the following. Choose a -preferably long-standing- mathematical problem with sufficiently rich structure (not as easy as it may sound) and build a cryptosystem around it (this is at least as hard as it sounds). Then prove that any adversary, who can break it, must also be able to solve the underlying mathematical problem. This is a win-win situation as either your cryptosystem is secure or the open problem is solved. The only issue that causes concerns is that the mathematical problems we use today are not versatile enough. Namely, all ubiquitously used public key cryptosystems depend on variants of the following two assumptions.

Factorization, i.e. the decomposition of a sufficiently large composite number into a product of primes, is hard. Neither RSA encryption nor the RSA signature are secure if factorization is solvable efficiently.
The computation of the discrete logarithm in several algebraic structures is hard (e.g. finding the exponent $x$ that satisfies $g^x = y\mod p$ for given $g,y$ and certain $p$ ). The Diffie-Hellman key-exchange used, e.g. in TLS, and the entire elliptic curve cryptography, including ElGamal encryption or the ECDSA signature scheme, rely on this assumption.

Moreover, the above two problems are not even independent of each other. Both of them are encompassed by the so-called finite Abelian hidden subgroup problem (FA-HSP). This huge dependence on a single problem causes that cryptography has to fear of any new opportunities in computing. Indeed, in 1994 Peter Shor proposed a fast quantum algorithm for factorization. Furthermore, this can be extended to solve the more general FA-HSP and thus the discrete logarithm problem as well. Accordingly, the first quantum computer capable of running Shor’s algorithm will undermine the security of the whole public key infrastructure.

Fortunately, there is no fundamental reason to stick to these assumptions. The main cause why cryptosystems based on them became so widespread is their outstanding efficiency compared to other solutions. Because other approaches also exist, they were just suppressed by the success of RSA and elliptic curve crypto. But quantum computers will initiate a new race that hopefully leads to more versatile solutions in applied cryptography. If in the meanwhile no one refutes our hope that we are in Cryptomania…

What is Post-Quantum Cryptography?

Symmetric key Cryptography and Quantum Database Search

Public key Cryptography and the Shor Algorithm

Further reading