I need a pathway for studying Lattice-Based Cryptography

Question

I realize that I need a study pathway for post-quantum cryptography.

I started to study post-quantum crypto by reading NIST PQC 3rd-round submissions of the lattice-based schemes (let's start with the most popular ones). I understood Kyber and Saber so that I could implement them. However, I want to understand the design rationales behind them. Why these errors have that length, what is the role of these parameters in practice.

Since the first lattice-based encryption schemes, there must be many improvements done considering speed or security. I need to understand these. Then, I started searching for papers about lattice-based algorithms and their attacks over the history of lattices. I found a large list here, but I could not filter these papers.

How should I start? Is there a good survey for me, or a list of readable papers covering the area?

Answer 1

Katz and Lybushavesky just (yesterday) released a book on lattice based cryptography. My particular copy is still shipping, so I can't mention whether it covers what you are in particular interested in, but as:

• Lyubashevesky is a co-author of both the KYBER and DILITHIUM finalists

• Katz's prior book (with Yehuda Lindell) Introduction to Modern Cryptography is widely praised for its excellent writing (and Katz is a co-author of the non-lattice Picnic round 3 alternate signature scheme)

It seems quite possible this could be the "goto" recommendation for learning lattice-based cryptography generically, and potentially even have exposition on the NIST candidates --- I won't know until my copy arrives though.

These slides by Daniel Apon (at NIST) regarding why NIST made the particular round 3 selections may also be useful for discussing the "design space" of lattice-based NIST candidates. You can find this kind of exposition elsewhere, for example in this paper of Dan Bernstein --- although I should mention that Dan often disagrees with certain "consensus" viewpoints within lattice cryptography. The paper is still useful of course, but if I recall Dan in particular has slightly non-consensus views on:

• The underlying choice of ring for RLWE (in particular, the size of its Galois group)
• Particularities of the definition of security often used in lattice cryptography (the "core-SVP" count)
• Certain potential patent issues with various RLWE-type techniques

One can read more about these disagreements on the NIST pqc google group, but I don't know of some short summary of them.

Answer 2

If your goal is to understand the NIST submissions, all of them are required to have a "design rationale" section in their specification documents. These often point to relevant papers as well. In addition, their presentations (see this and this and this) are often helpful in explaining intuitively the underlying principles.

If your focus is lattices, I recommend having a look at this series of workshops. There are many introductory talks, and since it was organized last spring, it is pretty much the state of the art.

Answer 3

Apologies for the belated reply.

I've found that the Simons Institute seminar on "Lattices: Algorithms, Complexity, and Cryptography Boot Camp" was pretty good as a generic intro to lattice crypto. [Thomas mentioned something close to this, but I wanted to be more specific.] This event happened Jan. 21 – Jan. 24, 2020 (just a month or so before COVID-19 hit the U.S.), so the content is fairly current.

The talks' videos can be found at: https://simons.berkeley.edu/workshops/schedule/10563

Cheers