Learning Post Quantum Crypto
Over the past 2 weeks I was on bed rest, which is an interesting forcing function to discover new hobbies. I decided to tick off a couple things on my list:
I will shortly release another article on how I used AI effectively for learning all this and my AI stack! It combines an agentic browser and other prompt tools!
In this article, I write down 9 surprising things I learnt about PQC (I make it as light reading as I could), including what it means for cryptocurrencies and mention if you could only read ONE article on PQC, what would it be.
Surprising thing #1: FHE and PQC have similar fundamentals
Post-Quantum Cryptography and Fully Homomorphic Encryption (FHE) constructions both rely heavily on the same lattice-based mathematical problems! This is also why FHE schemes are inherently quantum-resistant.
What makes lattice problems hard for Quantum computers?
A lattice is simply an arrangement of various geometrical point across several dimensions.
In 2D, it is very easy to figure what point is closest to a line. But if we are in 100+ dimensions, this problem becomes computationally hard even for quantum computers! There are no known efficient algorithms! So all lattice based cryptography depend on the following two problems:
Surprising thing #2: Quantum Computers don't break cryptography simply because they can brute force fast
I thought the quantum "sell" is that n qubits can simulteanously have 2^n states and therefore can brute force exponentially fast. I was so wrong! There are 2 big quantum algorithms that matter for PQC:
Notice neither of the two can solve the above mentioned lattice problems quickly so a cryptographic construction relying on above hardness is fine.
Surprising thing #3: Agencies are harvesting internet data NOW to decrypt it later with quantum computers
There is a very real reason to care about it all NOW - there is a very real threat today, not some prophesied future problem). Sophisticated actors are already collecting today's encrypted internet traffice - they can't decrypt it now of course but when quantum computers eventually become capable, they could decrypt it retroactively. This is appropriately termed "Harvest Now, Decrypt Later"
This is very bad for VPNs, chat and email apps as their promise of e2e encrypted doesn't hold. Within cryptocurrencies, Ethereum, Bitcoin etc are unaffected by this specific attack but privacy chains like ZCash face the problem of already settled private transactions becoming exposed (Be sure to read surprising thing #9).
Surprising Things #4: Service Providers have already migrated or in-process
Per Cloudflare, over 35% of (non automated) HTTPS traffic is already PQ!
Recommended by LinkedIn
Surprising Thing #5: Above services don't just use post quantum protocols but also use classical ones
Since quantum cryptography is much newer to traditional, there is a chance that implementations have bugs that may be broken by today's computers. So above implementations use hybrid encryption—combining classical algorithms (for immediate security) with post-quantum algorithms (for future protection).
## Surprising Thing #6: Physical Qubits vs Logical Qubits
Turns out not all qubits are the same.
Physical qubits are the actual quantum hardware—individual quantum systems that can exist in superposition. However, today, we can't make them reliably. They are incredibly fragile and error-prone.
Logical qubits are an abstraction, formed by encoding information across multiple noisy physical qubits to simulate the fault tolerance required for quantum algorithms.
The ratio of physical to logical qubits is quite high: apparently around 1,000 physical qubits may be needed to form just one well-protected logical qubit.
Breaking RSA requires ~4000 to ~20000 "good" qubits. This means we need to build a qunatum computer with millions of physical qubits with current techniques (Today, at best we have 1000 physical qubit machines)
So yes quantum may not be a threat now, with the exception of the scary Harvest Now, Decrypt Later attacks.
Surprising Thing #7: We have proper PQC Standards
Broader industry and agreed to several PQC standards with NIST! I won't go into them but ML-KEM (formerly Kyber) and ML-DSA (formerly Dilithium) are the ones everyone is using.
Surprising Thing #8: Overhead of 35X in communication of PQC Protocols over the Web
The real engineering challenge is in migrating all of existing internet stack to PQC (e.g. TLS). With Kyber, establishing an encryption key requires 2272 bytes of communication between the client and the server, compared to just 64 bytes for a key exchange using a modern elliptic-curve-based scheme. A 35x overhead.
Surprising Thing #9: Easiest Mitigation against Quantum Computers for Cryptocurrencies
El Salvador recently moved their bitcoin holdings in National Strategic Reserve to multiple new, unused bitcoin addresses to protect against quantum threats. This applies to Ethereum too. Unused addresses haven't revealed their public keys to anyone. So there is nothing for a quantum computer to use to derive your private keys (and break ECC cryptograpy).
Similarly, privacy chains like ZCash and Aztec can fight against Harvest Now Decrypt Latter attacks by having users never publish their public keys (make public keys private!).
Great summary!!