Advanced cryptographic primitives

Foundations of CS Master, ENS de Lyon, Fall 2014.

Traditional cryptography is ill-suited to modern security needs, arising from the outsourced storage and computation possibilities that the "cloud" offers. The course is centered around encryption and its advanced variants that are more suited to the cloud. We will show how to design protocols whose security provably relies on the difficulty of hard problems such as the discrete logarithm problem (and variants involving pairings) and problems related to euclidean lattices. We will start from basic encryption and move up to more and more advanced primitives. Primitives that the course may cover include: Emphasis will be put on properly modeling the primitive functionalities, defining the possible attacks, and proving that such attacks would lead to efficient algorithms for algorithmic problems that are conjectured hard.

Course objectives


It is expected that the students have already followed an introductory course on cryptography. Basic notions in complexity theory, probabilities and algebra will help. J. Katz and Y. Lindell, Introduction to Modern Cryptography: Principles and Protocols.


For one third of the grade: scribe.
For two thirds of the grade: reading an article and giving a summary talk on it. The defence will include course questions.

Course notes

Lecture 1. Lecturer: Benoît Libert; scribe: Benjamin Hadjibeyli. Identity-based encryption and bilinear maps
Lecture 2. Lecturer: Benoît Libert; scribe: Alice Pellet-Mary. Standard model IBE from bilinear maps
Lecture 3. Lecturer: Damien Stehlé; scribe: Mihai-Ioan Popescu. The Learning With Errors Problem
Lecture 4. Lecturer: Damien Stehlé; scribe: Julien Le Maire. Public key encryption from LWE
Lecture 5. Lecturer: Damien Stehlé; scribe: Fabrice Mouhartem. IBE from LWE
Lecture 6. Lecturer: Benoît Libert; scribe: Henri Derycke. Hierarchical IBE and applications
Lecture 7. Lecturer: Benoît Libert; scribe: François Pirot. Fuzzy Identity-Based Encryption and Attribute-Based Encryption
Lecture 8. Lecturer: Benoît Libert; scribe: Florent Bréhard. Attribute-Based Encryption and Searchable Encryption
Lecture 9. Lecturer: Damien Stehlé; scribe: Sebastian Scheibner. Attribute-based encryption for all circuits from LWE
Lecture 10. Lecturer: Damien Stehlé; scribe: Antoine Pouille. Fully homomorphic encryption
Lecture 11. Lecturer: Benoît Libert; scribe: Stéphane Durand. Searchable encryption.
Lecture 12. Lecturer: Damien Stehlé. Functional encryption from LWE.
Lecture 13. Lecturer: Ron Steinfeld. Using fully homomorphic encryption in secure multi-party computations.

List of articles

Each student must choose one item in the list, and prepare an oral presentation. First arrived first served! The defence will consist in 20 minutes of presentation, and 20 minutes of questions. The presentation, relying on transparencies, will summarize the article(s) or a specific aspect of the article(s). It is expected that the technical material is understood, and that the contributions are put in proper context relative to the course material. The examiners will ask questions on: the course contents, the technical contents of the article, the relevance of the article, etc.


Benoît Libert and Damien Stehlé.