Quantum Computing and Cryptography: How Shor's Algorithm Could Break RSA and the Move to Post-Quantum Cryptography

Veritasium explains a looming threat to encryption: state and non state actors are storing encrypted passwords and data today in the hope that a future quantum computer can decrypt them quickly. The sndl concept is the core idea driving urgency even though powerful quantum machines are years away. The video then unpacks how RSA public key cryptography can be broken by Shor's algorithm and the quantum Fourier transform, and why large primes and factoring matter. It also surveys the move toward post quantum cryptography, highlighted by NIST's lattice based algorithms, and what lattice based cryptography could mean for keeping communications secure in a quantum future.

Introduction

Veritasium introduces a quantum threat to encryption and the sndl concept, store now, decrypt later. The idea is that adversaries intercept and archive encrypted data knowing that future quantum computers could crack it.

Core Concepts in Cryptography

The video revisits symmetric and asymmetric cryptography, focusing on public key cryptography and RSA. It explains how public keys are built from the product of two large primes and why factoring such numbers is central to breaking the scheme.

Quantum Computing Basics

The explanation covers qubits, superposition, and the counterintuitive readout problem: measuring a quantum state collapses it to a single result, so clever methods are needed to extract useful information from a quantum computation.

Shor’s Algorithm and the Quantum Fourier Transform

The heart of the quantum speedup is Shor’s algorithm, which uses a quantum Fourier transform to extract the period of a modular exponentiation superposition. This period finding is what allows factoring large integers much faster than classical methods.

A Simple Classical Illustration

The transcript walks through a didactic example with N as a product of two primes and a bad guess G. It shows how raising G to various powers and applying Euclid’s algorithm can yield the factors, illustrating why quantum speedups target the exponent finding step rather than the rest of the factoring process.

Hardware Realities

Even if a quantum algorithm exists in theory, building a large, reliable quantum computer is hard. The talk notes decades of progress and the accelerating pace of qubit counts, yet emphasizes the gap to practical breakage of RSA today.

Post-Quantum Cryptography

With RSA potentially vulnerable, researchers pursue post-quantum cryptography that remains secure against quantum attacks. In 2016 the NIST competition began, evaluating hundreds of proposals. By mid 2022 NIST selected four algorithms to form the basis of post quantum cryptographic standards, three of which are lattice based. The video explains lattice based cryptography with a two dimensional lattice intuition and shows how higher dimensional lattices make the closest vector problem extremely hard to solve. This section emphasizes that the shift to quantum resistant schemes is not merely theoretical but a practical race against quantum progress.

What Lattice Based Cryptography Does

In the lattice based approach, a message is encoded as a lattice point with small noise added. The recipient who possesses a trapdoor set of vectors can efficiently recover the original lattice point, while an attacker without the secret vectors faces a hard closest vector problem, which remains difficult for both classical and quantum computers.

Outlook

The video closes with a broader reflection on the ongoing collaboration between cryptographers and mathematicians, the role of standards bodies in vetting algorithms, and the looming transition that will reshape how we secure digital communications into the quantum era.