AI summary by TwinMind
Exposing Why Quantum Computers Are Already A Threat
Veritasium
24m 28s
Store Now Decrypt Later (SNDL) Threat
- Nation states and individual actors intercepting/storing encrypted data (passwords, bank details, SSN)
- Cannot currently decrypt but expect quantum computers within 10-20 years
- Information valuable for decades: industrial/pharmaceutical research, top secret government intelligence
- NSA: sufficiently large quantum computer would undermine all widely deployed public key algorithms in 5-10 year timeframe
- U.S. Congress passed legislation mandating all agencies transition to quantum-resistant cryptography now
Current Encryption History and Limitations
- Current encryption successful for 40+ years
- Pre-1970s: symmetric key algorithms required in-person key sharing
- Challenge: sending information to unknown parties without secure key exchange
- 1977: Rivest, Shamir, Adelman created RSA breakthrough
RSA Encryption Mechanism
- Each person has two large secret prime numbers
- Multiply primes to create public number
- Sender uses recipient's public number to encrypt message
- Impossible to decrypt without knowing prime factors
- Asymmetric key system (different keys for encrypt/decrypt)
- Modern cryptography uses ~313-digit primes
- Classical factoring with supercomputer: 16 million years using general number field sieve
Quantum Computer Fundamentals
- Classical bits: one state at a time (0 or 1)
- Two bits = 4 possible states (00, 01, 10, 11)
- Qubits: can exist in superposition of 0 and 1 simultaneously
- Two qubits can represent all four states simultaneously
- 3 qubits = 8 states, 20 qubits = >1 million states
- 300 qubits = more states than particles in observable universe
- Major limitation: measurement collapses superposition to single random value
Quantum Fourier Transform and Shore's Algorithm
- 1994: Peter Shore and Don Coppersmith developed quantum Fourier transform
- Works like normal Fourier transform on periodic signals
- Returns frequencies from periodic superposition states
- Key breakthrough for factoring large numbers
Quantum Factoring Method Walkthrough
- Example: factor n=77 (product of primes p and q)
- Pick number g that doesn't share factors with n (e.g., g=8)
- Find exponent R where g^R = multiple of n + 1
- For 8^10 mod 77: remainders cycle every 10 steps (8, 64, 50, 15, 43, 36, 57, 71, 29, 1)
- Rearrange equation: g^(R/2) - 1 × g^(R/2) + 1 = multiple of n
- Use Euclidean algorithm to find greatest common divisor
- Example: gcd(32769, 77) = 11, therefore 77 = 11 × 7
Quantum Implementation Steps
- Split qubits into two sets
- First set: superposition of 0 to 10^1234 (requires ~4100 qubits)
- Second set: initially zero states
- Raise g to power of first set, divide by n, store remainder in second set
- Measure remainder part only → creates periodic superposition
- Apply quantum Fourier transform to extract period R
- Use R for classical factoring steps
Current Quantum Computing Progress
- Perfect qubits needed: several thousand
- Physical qubits needed (accounting for errors):
- 2012: 1 billion physical qubits
- 2017: 230 million physical qubits
- 2019: 20 million physical qubits
- Current IBM quantum computers: nowhere near required numbers
- Progress appears exponential → question of when curves collide
Post-Quantum Cryptography Development
- 2016: NIST launched competition for quantum-resistant algorithms
- 82 proposals submitted globally, rigorously tested
- July 5, 2022: NIST selected 4 algorithms for post-quantum cryptographic standard
- 3 algorithms based on lattice mathematics
Lattice-Based Cryptography
- 2D example: vectors R1, R2 create lattice points through integer combinations
- Task: find lattice point closest to given point C
- Different vector bases (B1, B2) make same problem much harder
- 2D: easy, 3D: harder, 1000D: extremely difficult
- Lattice points in sphere grow exponentially with dimensions (R^d)
- 1000 dimensions: one right step vs 999 potential wrong steps
Lattice Encryption Process
- Each person has good (secret) vectors describing lattice
- Publicly share lattice using hard-to-work-with vectors
- Sender picks lattice point corresponding to message (e.g., point = number 7)
- Add random noise to lattice point before sending
- Recipient uses secret good vectors to find closest lattice point
- Problem extremely difficult for both classical and quantum computers
- Army of researchers/mathematicians/cryptographers ensuring data security
Sponsor Content
- Brilliant.org quantum algorithms course (co-developed with Microsoft, Alphabet X)
- Quantum gate simulation and algorithm execution in lessons
- Data analysis course for statistical reasoning skills
- 30-day free trial, 20% off annual premium subscription for first 200 signups
