9 May 2022

# Post Quantum Cryptography - Hard-to-Solve Number Theory Problems

Many of the crucial communication protocols rely on three core cryptographic mechanisms: public-key encryption, digital signatures, and key exchange. These functionalities are primarily implemented using the Diffie-Hellman (DH) key exchange, the RSA cryptosystem, and the Elliptic Curve cryptosystems. Their security depends on the difficulty of two Number Theory problems – *Integer Factorization* and the *Discrete Logarithm Problem* over various groups.

** Integer factorization** (given with , find and ) lays the foundation of many public-key cryptographic systems. It is computationally infeasible with an ordinary computer for large integers if they are the product of large prime numbers. As of 2020, the largest publicly known factored RSA number had 829 bits or 250 decimal digits (i.e., RSA-250). In practice, RSA keys () are typically 1024 to 4096 bits long, but the minimum recommendations have moved to at least 2048 bits.

** Discrete Logarithm Problem (DLP)** (given in a group and , find ) is another pillar of public-key cryptosystems like the DH key exchange, the El-Gamal encryption, the Digital Signature Algorithm (DSA) or similar ones based on Elliptic Curve (EC) Cryptography. The naïve algorithm (

*trial multiplication*) for solving DLP requires running time linear in the size of the group , and thus exponential in the number of digits in the size of the group. Therefore, it is practical only for small groups . More sophisticated algorithms exist (e.g., Baby-step giant-step, Index calculus, Pohlig-Hellman, Pollard's rho). Some of these algorithms run in time proportional to the square root of the size of the group (i.e., exponential in half the number of digits in the size of the group). However, none of them runs in polynomial time.

The above two problems are hard to solve with a classical computer, but easy to be solved in polynomial time running ** Shor's algorithm** [1] on a sufficiently powerful quantum computer. This would break many of the popular cryptographic systems in use today that rely on RSA, DSA, DH, and ECDH & ECDSA algorithms. The end result would be losing the protection currently provided to secure Web pages, encrypted email, and other types of data with significant ramifications for electronic privacy and security.

The most important usage of the public-key cryptography is for *digital signatures* and *crypto key establishment*. When it comes to encryption, symmetric-key algorithms are much faster. To break symmetric-key systems and find out the secret key, it requires a search of the key space. The good news is that ** Grover's probabilistic quantum algorithm** [2] provides only a

*quadratic speedup*in brute force search comparing with search algorithms implemented on classical computers. In other words, if the average-case sorting of an unsorted database takes steps on a classical computer, it will need only steps for this task using Grover's algorithm on a quantum computer. Moreover, it has been shown that an exponential speedup for search algorithms is impossible. This means that the cryptographic symmetric primitives (e.g., hash functions, message authentication codes, block or stream ciphers) need to double the key length to maintain the same level of security against a quantum computer. As an example, Grover's algorithm would find a 256-bit AES key in quantum operations given a few known plaintexts encrypted under that key.

The blog provided short descriptions of two Number Theory problems (i.e., integer factorization and discrete log problem) that ensure the security of current public-key cryptosystems. These problems are computationally infeasible on classical computers, but Shor's algorithm is expected to solve them on a powerful enough quantum computer.

Next blog will be more specific about the impact of quantum computing to current cryptographic algorithms.

**Bibliography**

[1] P. W. Shor, "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer," in *Proceedings of the 35th Annual Symposium on Foundations of Computer Science*, Santa Fe, NM, 1994.

[2] L. K. Grover, "A fast quantum mechanical algorithm for database search," in *Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (STOC)*, Philadelphia, PA, 1996.