Store Now, Decrypt Later and the Quantum Threat to RSA: Veritasium on Quantum Cryptography

Overview

Veritasium introduces Store Now, Decrypt Later (sndl) as a motivation for mass data collection today. Encrypted passwords, bank details and secret documents are being stored because quantum computers in 10 to 20 years could break current encryption in minutes.

He traces the evolution from symmetric key exchange to public key cryptography, highlights the RSA system, and explains why factoring the product of two large primes is classically hard. The video then describes how quantum computers, using qubits and superposition, could dramatically speed up this task with Shor's algorithm, and why a quantum Fourier transform is central to extracting the needed frequency information. Finally, it discusses post-quantum cryptography, lattice-based approaches chosen by NIST, and the race to quantum-safe cryptography.

Introduction: The Quantum Threat to Encryption

The video opens by outlining sndl, the practice of intercepting and storing encrypted data today with the expectation that future quantum computers will decrypt it. The National Security Administration and US policy are cited as recognizing this threat and pushing for a transition to quantum-safe cryptography.

From Symmetric Keys to Public Key Cryptography

Historically private information could be shared with a secret symmetric key that needed to be kept confidential. With the rise of communicating with strangers, public key cryptography emerged, enabling secure communication without sharing a secret key. RSA, based on two large primes, is explained using the idea that a public key is a product of two primes whose factors are kept secret. Factoring this large semiprime is the security backbone of RSA.

Classical Hardness and Quantum Possibility

On classical computers, factoring a 313-digit semiprime would take astronomically long, roughly millions of years with the best-known algorithms. However, a sufficiently large quantum computer could break RSA by exploiting quantum algorithms. The concept of qubits, superposition, and the advantage of processing many states in parallel is introduced, setting the stage for Shor's algorithm.

Shor's Algorithm and the Quantum Fourier Transform

Shor and Koppersmith pioneered a quantum method to factor numbers efficiently by using a quantum Fourier transform to extract the period of a modular function, which directly relates to the factors of N. The video emphasizes that the speedup hinges on transforming a difficult factoring problem into a period-finding problem in a quantum superposition.

A Concrete Example Before the Quantum Leap

To illustrate the idea, a simple classical example is walked through: factoring N = 77 using a guessed G that shares few factors with N. The method shows how one can derive an exponent R such that G^R is 1 modulo N, then construct two numbers that likely share factors with N and obtain the prime factors via Euclid's algorithm. The key takeaway is that the hard step in the quantum version is determining the exponent R efficiently, which Shor's algorithm accomplishes.

How a Quantum Computer Would Factor Large Numbers

The video sketches the quantum factoring process: split qubits into two registers, prepare a random G, raise it to many powers, and compute remainders modulo N. After entangling the qubits, a targeted measurement of the remainder yields a periodic structure. A quantum Fourier transform then reveals 1 over R, allowing extraction of the period and, if R is even, the factors of N via Euclid’s algorithm. The overall result would be breaking RSA encryption and many other public-key schemes.

The Reality of Qubits and Timelines

Despite the theoretical power, real quantum hardware is imperfect. The talk surveys historical estimates of the number of physical qubits needed to break RSA: from a billion in 2012 down to tens of millions in later years, reflecting rapid progress. Today’s IBM devices are not yet close to that scale, but the growth appears exponential, leading to an urgent race to build robust quantum computers or alternative cryptographic schemes.

Post-Quantum Cryptography: A Path Forward

Anticipating the threat, cryptographers pursued quantum-resistant methods. In 2016 the National Institute of Standards and Technology (NIST) launched a competition to find new algorithms that cannot be broken by quantum attacks. After extensive review, four lattice-based algorithms were selected in 2022 as part of the post-quantum cryptographic standard. The video explains lattice cryptography using a 2D plane example and shows how closest-vector problems in high dimensions are exceptionally hard, even for quantum computers, creating a promising route to secure communications in the quantum era.

Lattice Cryptography: How It Works at a Glance

In the lattice approach, a user has a good set of secret vectors that define a lattice. A message point is sent with small random noise added, and the recipient, who has the secret vectors, can correctly decode the lattice point, while an adversary without the vectors finds the closest lattice point to the noisy message computationally intractable. The talk emphasizes that both classical and quantum computers struggle with such high-dimensional closest-vector problems, making lattice cryptography a strong candidate for resisting quantum attacks.

Conclusion: The Future of Trustworthy Encryption

Behind the scenes, a large community of researchers works to ensure data remains secret in the face of quantum advances. The video closes with a reflection on the human side of this technological evolution and the importance of educating the public about the upcoming changes in cryptography and data security, highlighting the dual role of quantum computing and artificial intelligence in shaping the next era of information security.