Summer 2025: Lattice-Based Cryptography Seminar

Seminar Description

Prerequisite: Linear Algebra, Abstract Algebra (including groups, rings, modules), Basic Number Theory, and basic familiarity with complexity theory and cryptography (e.g., one-way functions, public-key encryption).

This seminar offers a rigorous introduction to lattice-based cryptography, one of the most promising directions in post-quantum cryptography. Topics include lattice trapdoors, digital signatures, (hierarchical) identity-based encryption, attribute-based encryption, and functional encryption, as well as advanced constructions such as zero-knowledge proofs.

By the end of the seminar, everyone is expected to be equipped to read cutting-edge research papers and conduct independent work in lattice-based cryptography or related fields in post-quantum cryptography.

Seminar Information

Lecturer: Liu Jiaqi
Lecture Time: 18:30 - 21:30 (GTM+8h)
Location: Online, by Feishu Meeting. Link Released in the morning.
Textbook: A decade of lattice cryptography by Christ Peikert (used as a primary reference, though the seminar will not strictly follow its structure; additional papers and lecture notes will be incorporated).

Lectures

Date Lecture Topic Reading Materials
June 27 Lecture 01 Lattice trapdoors (short bases), discrete Gaussian sampling, digital signature Reading:
  • Textbook Chapters 5.4.1–5.4.2
  • [GPV08] by Gentry, Peikert, and Vaikuntanathan
Supplement:
  • The first half part Video by Chris Peikert (no Chinese captions) (The video also covers the procedure of discrete Gaussian sampling and explains the intuition behind why the GGH scheme is not secure. These topics were not discussed in detail during the lecture.)
July 02 Lecture 02 Preimage sampleable function (PSF) from SIS, digital signature scheme Reading:
  • Textbook Chapters 5.4.2, 5.5.1
  • [GPV08] — the PSF part and digital signature part.
    • (The "hash-and-sign" paradigm is an important way to construct digital signature schemes).
Supplement:
  • Chapter 13 in [BS] is helpful if you want to study the rigorous description of digital signature.
July 06 Lecture 03 Identity-based encryption (IBE) Reading:
  • Textbook Chapter 5.5.2
  • [GPV08] — the IBE part
    • (The scheme in [GPV08] also meets the anonymous property, i.e., the ciphertext also hides the identity to which it was encrypted). It is better if you have reviewed the dual cryptosystem.
Supplement:
  • Section 15.6.1, 15.6.2 in [BS] is helpful if you want to understand the background and the rigorous description of IBE. It also includes how to a selectively secure IBE to an adaptively one.
July 23 Lecture 04 Gadget Trapdoors Reading:
  • Textbook Chapter 5.4.3
  • [MP12] on gadget trapdoors
Supplement:
  • The latter half of Video by Chris Peikert (The "P" in [GPV08] and [MP12]). It is an excellent lattice-related lecture that I have personally found highly insightful, having watched it multiple times.:)
July 27 Lecture 05 (Hierarchical) IBE without random oracle model Reading:
  • Textbook Chapter 5.5.3
  • [CHKP10] on (Hierarchical) IBE from LWE (This paper also proposed a scheme of "hash-and-sign'' digital signature scheme which is secure in the "standard model''!)
Supplement:
  • [CHKP10] has many useful tools not covered in the lecture, such as Bonsai trees (a mathematical object which is developed independently of crypto), extending and randomizing a trapdoor (short basis rather than gadget trapdoors) at a cost of a small loss in trapdoor quality. Additionally, the scheme mentioned in the lecture is also adaptively secure in the standard model (not trivially using the generic transformation from a selectively secure one).
July 31 Lecture 06 Trapdoor puncturing and compact (hierarchical) IBE without random oracle model Reading:
  • Textbook Chapter 5.5.4
  • [ABB10a] on efficient (Hierarchical) IBE from LWE (This paper uses the idea of gadget trapdoor implicitly. You may notice the paper was presented ahead of the gadget paper [MP12].)
Supplement:
  • Video by Shweta Agrawal (The "A" from [ABB10]). You may find this video useful if you would like to run through the "trapdoor".
  • There is another "ABB" paper [ABB10b] It gives another HIBE scheme with the advantage of keeping the lattice dimension unchanged upon delegation. (If someone is interested in this, I am glad to discuss it with you.)
Aug 4 Lecture 07 Summary and applications of (hierarchical) IBE and Attribute-based Encryption (ABE) Review: Read:
  • [BS] 15.7.1.2.
Supplement:
  • [BS] 15.6.4 about the applications of IBE.
  • Lecture note about IBE and ABE from Vinod Vaikuntanathan.
  • Papers related to register-based encryption: [GHMR18],[GHM+19] .

Announcements

Additional Materials

Please check the list below for useful references and let me know if you have suggestions!

  • Erratas and updates will be posted regularly.

    • Books

  • [BS] A Graduate Course in Applied Cryptography by Dan Boneh and Victor Shoup. My favourite crypto book.

    • Lecture Notes

    Videos