Quantum Impact on Cryptography

When quantum computers were first theorized, they were mainly considered to be an intellectual curiosity. In fact, the entire motivation behind the concept was to enable more accurate physics simulations. At first, the field seemed to be forever destined to remain an academic curiosity.

Shor’s Algorithm

That all changed in 1994, when mathematical physicist Peter Shor showed that a hypothetical quantum computer could be used to solve a math problem that no feasible classical computer ever could. Shor’s algorithm describes a process for factoring large numbers.¹ Leveraging the unique properties of quantum mechanics (entanglement, interference), this algorithm can quickly recover the prime factors of a very large number where a classical computer would take billions of years. To this day, it remains one of the only known quantum algorithms with an exponential advantage over classical computing.

The problem of factoring large numbers, while seemingly also academic, is actually the basis for much of modern cryptography. It underlies our entire modern internet infrastructure, used in everything from banking transactions to military communications systems. Its security depends entirely on the computational difficulty of factoring, which evaporates in the face of Shor’s algorithm.

Primary threat to blockchains

Shor’s algorithm breaks public key cryptography (RSA, ECC), securing digital signatures and key exchange. This would allow private key recovery from a public key and signature forgery [4] — the primary quantum threat to blockchain systems.

Grover’s Algorithm

A short time later, in 1996, computer scientist Lov Grover developed another quantum algorithm with cryptographic implications. Grover’s algorithm provides a quadratic speedup for searching unsorted databases and, more importantly for cryptography, for reversing hash functions and brute-forcing encryption keys. While not as dramatic as Shor’s exponential speedup, Grover’s algorithm is still relevant to certain cryptographic systems.

Grover’s algorithm weakens symmetric cryptography and hash functions, requiring larger key sizes and hash outputs to maintain equivalent security. While less immediately threatening than Shor’s algorithm, at some point it will necessitate adjustments to cryptographic parameters to ensure the same level of security for hash functions and symmetric encryption [5].

Comparative threat to blockchains

Grover’s algorithm weakens symmetric cryptography (AES) and hash functions (SHA-256). This is a secondary threat (manageable by doubling key sizes) unlike the existential threat posed by Shor’s to public key cryptography.

Algorithmic Complexity Comparison: Shor’s vs. Grover’s

Although both algorithms are relevant, the cryptographic relevance of these algorithms (and the threat they pose) depends on how they compare to the best classical alternatives at scale.

For solving the discrete logarithm problem (the basis of elliptic curve cryptography like ECDSA):

Best classical algorithm: Pollard’s rho runs in time exponential to n in an n-element group, which for a 256-bit elliptic curve means approximately 2¹²⁸ (or roughly 340 trillion trillion trillion) operations.
Shor’s algorithm: Runs in polynomial time, providing an exponential speedup, requiring on the order of tens of millions of operations to factor a 256-bit key.

For brute-force search problems (breaking symmetric encryption like AES):

Best classical algorithm: Exhaustive search requires an exponential number of operations for an n-bit key.
Grover’s algorithm: Reduces the classical resources required by a modest quadratic factor.

Asymmetric cryptography (ECDSA) — Shor's algorithm exponential speedup over Pollard's Rho — Figure 5: Relative Advantage of Shor's vs. Grover's Algorithm

Symmetric cryptography (AES/SHA) — Grover's algorithm quadratic speedup over brute force — Figure 5: Relative Advantage of Shor's vs. Grover's Algorithm

Of course, describing an algorithm in theory and running it on a practical device are two different things. As discussed in the prior section, practically implementing a fault-tolerant quantum computer has proved to be a major challenge for the field over the last three decades.

Despite recent progress, current quantum computers are not capable of breaking cryptography with Shor’s, Grover’s, or any other known algorithm. Understanding whether and how that will change requires understanding the underlying challenges of building a fault-tolerant quantum computer.

To assess when that will change, we need to examine the core obstacle in quantum computing: maintaining coherence in the presence of noise while scaling up from proof-of-concept to a practical, fault-tolerant system.