A Tutorial Introduction to Lattice-based Cryptography and Homomorphic Encryption

A few of us have been working with homomorphic encryption for a number of years now, but we never found a paper / book that covers all the foundational mathematical material in one place. So we decided to write one — well my postdoc Kelvin Yang Li decided to write one and Mike Purcell and I assisted — and here it is to make everyone’s life a little bit easier.

https://arxiv.org/abs/2208.08125

At 144 pages, the tutorial is long but hopefully pretty readable, given we made no assumptions on the reader’s background and everything is built up from scratch. For readers that do have some of the technical background, the chapters can be read pretty independently and should serve as useful references. The mind map at the end should also be useful for those who wants to see all the key components of the Ring Learning with Errors problem and how they relate to each other on one page.

With NIST’s recent announcement that Kyber, which is based on the Module Learning with Errors Problem, is the recommended general purpose post-quantum cryptography scheme, I think lattice-based cryptography is about to get a lot more popular than it is.

Enjoy.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s