0x00A - Lattice-based Cryptography 🧮
I’m kind of stoked that we got to the 10th issue (0x00A)! You can give unzip a like here.
Disclaimer: I’m not a quantum researcher, nor am I very knowledgeable about this topic. I mainly used other smart people, see the "Thanks" section. If there are still technical issues in this article, don’t hesitate to reply to this email.
Synonyms/Related: Quantum-resistant encryption, Post-quantum cryptography (PQC), Learning with Errors (LWE)
- Problem: Quantum computers will be able to break current cryptography schemes (mainly asymmetric encryption, like RSA) easily.
- Solution: Use Lattice-based (a mathematical concept) Encryption, which is currently believed to be hard for quantum computers to solve efficiently.
- In Sum: Quantum computers are becoming an imminent problem. We as developers need to start thinking about implementing post-quantum cryptography algorithms to protect them now before it’s too late.
The hardness of factoring is what makes RSA so secure, but with a quantum computer that isn’t hard anymore. So, we need to find new hard problems that are easy to construct and hard to crack.
There are a few cryptographic algorithms that are trying to solve PQC, but it seems that lattice-based algorithms are the leading contenders:
“Unlike more widely used and known public-key schemes such as the RSA, Diffie-Hellman or elliptic-curve — which could, theoretically, be defeated using Shor's algorithm on a quantum computer—some lattice-based constructions appear to be resistant to attack by both classical and quantum computers. ... Lattice-based cryptographic constructions are the leading candidates for public-key post-quantum cryptography.”
If you want to learn how the math behind lattices works, check out this (video), this (Medium article), or this (Wikipedia). One of the main problems lattices rely on is Learning with errors which you might also want to check.
Use cases ✅
- Asymmetric encryption reliant systems
- Security critical industries and projects
- Banking, Public Sector, Defence, Healthcare, Telecom & Insurance
- Protocols and projects planned for usage in the next 5-20 years
- Designs of systems that might be prone to quantum attacks in the future, e.g. offline systems.
- Any company that transmits long-term sensitive data
- E.g. health records
- Prepare for the future: Post-quantum cryptography is around the corner (Q-day), and starting to spread awareness and implementing strong encryption mechanisms today is important for that future.
- Hidden advancements: The biggest quantum computer we know about is currently IBM’s Eagle with 127 stable qbits, planning to reach 433 in 2022. The question is, what about bad actors and rogue nation-states working on quantum computers we don’t know about? They might reach quantum supremacy a lot sooner than we anticipate.
- Hack now, decrypt later: There are threat actors that save ciphertexts from hacked targets right now, to later decrypt them with quantum computers. This means that sensitive information sent today is still prone to attack.
- Most promising: At the moment, lattices seem like the best candidates to secure against quantum computers:
Why not? 🙅
- Might not be an imminent problem, yet: Relevant circles talking about quantum computing say that an imminent threat to large RSA keys (>2048bits) will take at least 10 years. So starting to mitigate this threat now in panic might not be needed, but are you willing to take the chance?
- Not fully proven: Like most computational problems in cryptography, lattice problems are conjectured to be hard, but not proved. While experts believe that lattice problems are unsolvable for a quantum computer (as well as for a classical one), nobody knows this for a fact. Despite this, it is highly advised to still check the NIST PQC Standartization efforts.
- Just recently SIKE (not lattice-based) a NIST contender was broken with a single core classical computer.
- Production ready-ness: Most libraries are not production-ready security-wise. There aren’t too many tutorials and options to choose from either.
- Very enterprise-focused: Because PQC is considered a futuristic thing, most companies addressing this issue are targeting large customers, forcing smaller players to implement PQC mechanisms themselves.
- Slow: In their current state, the proposed post-quantum cryptography algorithms are quite slow on a sequential computer, compared to RSA-like schemes.
- However, there are faster parallel algorithms for lattice-based cryptography. So, when lattice crypto is executed properly with multi-threading (or better yet, on the GPU), the speed becomes much more reasonable.
Tools & players 🛠️
- liboqs - liboqs is an open-source C library for quantum-resistant cryptographic algorithms (from Open Quantum Safe). Which also integrates into OpenSSL
- Cloudflare's CIRCL open-source go cryptographic library for PQC
- ISARA - has a Quantom-safe developer toolkit, and a “Quantum-Safe Readiness Program for Enterprise”
- Virgil Security - provide a toolkit that uses their own platform and supposedly is PQC resistant (JS, Swift, Kotlin)
- IBM - has been researching PQC and Quantum in general for quite a while
- Companies working on PQC solutions: QuSecure, Quantropi, Wickr (AWS), Q→NU, IDQ, QuantunXchange, Quintessence Labs
What can I do now? 🧑🏭
A specific section for this issue 🆕
- Start experimenting with PQC algorithms and build proof of concepts.
- Note: The PQC algorithms are still under development. It is probably not the best idea to deploy any of the algorithms in production before they get properly reviewed.
- Use post quantum X.509 certificates - whitepaper.
- See Wultra's (fin-tech security firm) recommendations.
- Check out openquantumsafe.org 🆒
- Awareness: I barely knew about this topic. Only after talking to Omri Shmueli was I introduced to the imminent future of PQC. I suspect that many organizations and developers will not know about these risks. I can see news outlets and dev-communities shining more light on this critical issue. I hope that I’m doing my part here with unzip.
- Regulations: PQC is currently not regulated, so there is no compliance risk. It can be inferred that organizations will need to start acting and being compliant when PQC is more talked about in the near future.
- Symmetric encryption: Most symmetric encryption schemes are considered safe against quantum computers, but it is advised to increase key sizes (see “What can I do now?” section).
- Blockchain: There are a few interesting consequences for the Blockchain, specifically Bitcoin (at the time of writing it is the biggest coin). I suspect that most coins will have to migrate/fork to a safe algorithm. The question of how much panic it will cause is relative to when they start acting.
Some extra information that is related to the subject matter:
- Top applications of quantum computing you should know about
- A great post about the controversy of the Hybrid approach to PQC.
- NIST’s API for PQC (should be abstract to the final winner implementation)
- There are 2 main ways to mitigate PQC:
- Classical post-quantum cryptography (CPQC) - lattice-based encryption is one of the solutions in this space
- Quantum key distribution (QKD) - using secure quantum channels (quantum superpositions or quantum entanglement) 🤯 it is not as feasible as CPQC at this time of writing
Funny things happen when you start writing newsletters.
While I was researching this issue, back home in Tel Aviv, I ran into Omri Shmueli, who is a PhD student for Computer Science in Tel Aviv University. He was working furiously on some presentation in a café, and - shedding my introvertness aside for a moment - I unashamedly asked him what he worked on.
Luckily for me, he was working on something related to quantum computing, and so we met later that week to talk about lattice-based cryptography. That meeting is the main reason this issue even exists in the first place, so thank you Omri for being so generous with your time!
In addition, I wanted to thank Dor Israeli (from Quantum Machines) and Tomer Solomon (from IBM, Cloud Research) for reviewing this issue and giving me great feedback.
(Where I tend to share unrelated things)
My lovely older sister Leeam just started her own newsletter called Digital Fallout ✨ that talks about “the impact of tech on human rights in the global south”. I think that this is a super important topic to cover and I’m glad someone as diligent and rigorous as her is talking about it. Go check it out!
PS, she doesn’t know I’m promoting her here, so let her know you came from here 🤗
Any questions, feedback, or suggestions are welcome 🙏
Simply reply to this e-mail or tweet at me @agammore - I promise to respond!