0x00A - Lattice-based Cryptography 🧮

August 05, 2022

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.

Lattice-based Cryptography

Synonyms/Related: Quantum-resistant encryption, Post-quantum cryptography (PQC), Learning with Errors (LWE)

TL;DR:

  • 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

Why? 🤔

  • 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:

    • They have been studied for a long time (even by Guass at the 1800s)

    • Have the most publications in the field of PQC (see the finalists to PQC of NIST).

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 🛠️

🤠

My opinion:

I suggest reading about this topic and listening to experts. You might want to still use hybrid cryptography in the meantime “

hybrid cryptography, in which quantum-safe public-key algorithms are used alongside traditional public key algorithms

” (

).

What can I do now? 🧑‍🏭

A specific section for this issue 🆕

Forecast 🧞

  • 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.

Extra ✨

Some extra information that is related to the subject matter:

Thanks 🙏

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.

EOF

(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!