Store Now Decrypt Later SNDL

From: veritasium

Store Now, Decrypt Later (SNDL) is a procedure where nation-states and individual actors intercept and store large amounts of encrypted data, such as passwords, bank details, and social security numbers, even though they cannot currently open these files [00:00:00]. This strategy is based on the belief that within the next 10 to 20 years, they will have access to a quantum computer capable of breaking the encryption in minutes [00:00:15].

SNDL is effective because information stored today, like industrial and pharmaceutical research or top-secret government intelligence, will still be valuable in a decade [00:00:29]. This threat is widely recognized; the National Security Administration (NSA) states that a sufficiently large quantum computer, if built, would be capable of undermining all widely deployed public key algorithms [00:00:42]. Despite powerful quantum computers being years away, they are already a threat due to SNDL, prompting the US Congress to pass legislation mandating all agencies to begin transitioning to new methods of cryptography that are resistant to quantum computers [00:00:58].

Current Encryption Schemes and Their Vulnerability

Current encryption schemes, such as RSA, have been remarkably successful for over 40 years [00:01:17]. Before the 1970s, private information exchange required an in-person meeting to share a secret, symmetric key used for both encryption and decryption [00:01:23]. However, sharing a key over unsecured channels like phone lines or mail risked interception [00:01:53].

In 1977, scientists Rivest, Shamir, and Adelman developed RSA, an asymmetric key system [00:02:00]. RSA relies on each person having two secret large prime numbers that are multiplied to create an even larger public number [00:02:14]. To send a private message, the sender uses the recipient’s public number to “garble” the message in a way that makes it impossible to ungarble without knowing the two prime factors [00:02:27]. While the intended recipient can easily decode it with their private keys, others cannot, unless they can factor the large public number [00:02:49].

Modern cryptography uses prime numbers around 313 digits long [00:03:06]. Factoring a product of two such large primes, even with the best-known factoring algorithm (the General Number Field Sieve) on a supercomputer, would take approximately 16 million years [00:03:02]. However, this is not the case for a quantum computer [00:03:17].

How Quantum Computers Break RSA (Shor’s Algorithm)

Quantum computers utilize qubits, which, unlike classical bits (0 or 1 at a time), can exist in an arbitrary combination of states—a “superposition” of 0 and 1 [00:03:53]. This allows a quantum computer to perform calculations for multiple numbers simultaneously [00:04:20]. For example, 20 qubits can represent over a million different states, enabling simultaneous computation of over a million different answers [00:04:46]. With 300 qubits, a quantum computer could represent more states than there are particles in the observable universe [00:04:57].

The challenge lies in extracting the desired information from this superposition, as measuring it yields only a single random value, losing other information [00:05:11]. However, specific problems have been identified where this can be done, and these problems form the foundation of most public key cryptography used today [00:05:27].

In 1994, Peter Shor and Don Coppersmith devised a method to take a quantum Fourier transform [00:05:56]. This allows the extraction of frequency information from a periodic superposition [00:06:30]. This capability is crucial for factoring large numbers.

Shor’s Algorithm for Factoring (Simplified Example): To factor a number N (product of two primes, e.g., N=77), the process is as follows [00:07:00]:

1. Guess G: Pick a random number g that does not share any factors with N (e.g., g=8 for N=77) [00:07:23].
2. Find Period R: Find the exponent r such that g^r is one more than a multiple of N (i.e., g^r mod N = 1) [00:07:38]. The remainders of g^x mod N will cycle periodically, and r is the period [00:12:05]. This is the step significantly sped up by a quantum computer [00:11:49].
   • A quantum computer can prepare a superposition of all possible exponents [00:13:54].
   • It then computes g^x mod N for all these exponents simultaneously, storing the remainders in a second set of qubits, entangling the two sets [00:14:31].
   • By measuring only the remainder part, a random remainder is obtained. This measurement collapses the first set of qubits into a superposition of only the exponents that produce that specific remainder [00:15:06].
   • Since these exponents are all separated by the period r, the resulting superposition is periodic [00:15:59].
   • Applying the quantum Fourier transform to this periodic superposition yields states containing 1/r [00:16:18]. A final measurement and inversion then reveal r [00:16:28].
3. Calculate New Numbers: If r is even, use it to calculate two new numbers: (g^(r/2) + 1) and (g^(r/2) - 1) [00:09:11]. These numbers will likely share factors with N [00:09:40].
4. Find Shared Factors: Use Euclid’s algorithm to find the greatest common divisor between these new numbers and N, which will yield the prime factors p and q [00:10:09].

While Shor’s algorithm needs several thousand “perfect” qubits, imperfect qubits require additional redundant information [00:16:51]. Estimates for the number of physical qubits needed to break RSA encryption have significantly dropped: from a billion in 2012 to 230 million by 2017, and further to just 20 million in 2019 due to technological breakthroughs [00:17:02]. Progress in quantum computing capacity appears to be exponential [00:17:29].

Post-Quantum Cryptography

To counter the looming threat from quantum computers, scientists have been developing new encryption methods resistant to both classical and quantum computers [00:17:42]. In 2016, the National Institute of Standards and Technology (NIST) launched a competition to find such algorithms [00:17:51]. Out of 82 proposals, four algorithms were selected in July 2022 to be part of their post-quantum cryptographic standard [00:18:00].

Lattice-Based Encryption

Three of the selected algorithms are based on the mathematics of lattices [00:18:17]. A lattice is formed by adding together different integer combinations of basis vectors (e.g., r1 and r2 in 2D) [00:18:24].

The security of lattice-based encryption relies on the Closest Vector Problem (CVP): given a set of vectors that define a lattice, and a point C, find the lattice point closest to C [00:18:42]. This problem is easy if you have a “good” set of basis vectors (e.g., orthogonal or nearly orthogonal), but becomes extremely difficult with a “bad” or highly skewed set of vectors [00:19:01].

The difficulty of CVP increases dramatically with the number of dimensions. While manageable in a few dimensions (e.g., 3 or 100), proposed future encryption schemes will use around a thousand dimensions [00:19:55]. In such high dimensions, finding the closest point is computationally intractable for even the most powerful conventional and quantum computers, unless one possesses the “good” set of basis vectors [00:21:01].

Encryption using Lattices:

1. Each person generates a “good” (secret) set of vectors that describe a lattice [00:21:16].
2. They derive and publicly share a “bad” (hard-to-work-with) set of vectors that define the exact same lattice [00:21:22].
3. To send a message (e.g., a number), the sender picks a lattice point corresponding to the message and adds some random “noise” to it [00:21:27]. The transmitted message is a point close to, but not exactly on, a lattice point [00:21:42].
4. To decode, the recipient uses their secret “good” set of vectors to easily find the closest lattice point to the received noisy message, thereby recovering the original message [00:21:47].

This approach ensures that decoding is easy for the recipient with the secret “good” vectors, but nearly impossible for anyone else, as the CVP is extremely difficult to solve for both classical and quantum computers given only the “bad” public vectors [00:22:02]. Researchers, mathematicians, and cryptographers are working to ensure data remains secret, protecting against mass surveillance and securing critical infrastructure [00:22:15].