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.
- Identity-based encryption,
- Attribute-based encryption,
- Functional encryption,
- Deterministic encryption,
- Fully homomorphic encryption,
- Secure multi-party computations.
- Understand the definitions of advanced cryptographic
primitives, their associated security requirements and their
- Acquire the basics of lattice-based cryptography.
- Acquire the basics of pairing-based cryptography.
- Be able to read state-of-the-art articles on lattice-based and
pairing-based cryptographic constructions.
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.
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
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,
Encryption Gone Wild. Michel Abdalla, Dario Catalano, Alexander
W. Dent, John Malone-Lee, Gregory Neven, Nigel P. Smart. ICALP 2006.
AND Generalized Key
Delegation for Hierarchical Identity-Based Encryption. Michel
Abdalla and Eike Kiltz and Gregory Neven. ESORICS 2007.
for Threshold Functions (or Fuzzy IBE) from Lattices. Shweta
Agrawal, Xavier Boyen, Panagiotis Voulgaris, Vinod Vaikuntanathan,
Hoeteck Wee. Public Key Cryptography 2012: 280-297. Yassine Hamoudi.
Encryption for Inner Product Predicates from Learning with
Errors. Shweta Agrawal, David Mandell Freeman, Vinod
Vaikuntanathan. ASIACRYPT 2011: 21-40. Yassine Hamoudi.
Identity Based Encryption Without Pairings. Dan Boneh, Craig
Gentry, Mike Hamburg. FOCS 2007. AND An
Identity Based Encryption Scheme Based on Quadratic Residues.
Clifford Cock. IMA Int. Conf. 2001.
- Conjunctive, Subset, and Range Queries on Encrypted Data. Dan Boneh, Brent Waters. TCC 2007:535-554.
- Direct chosen
ciphertext security from identity-based techniques. Xavier
Boyen, Qixiang Mei, Brent Waters. ACM Conference on Computer and
Communications Security 2005: 320-329. AND Chosen-Ciphertext
Security from Tag-Based Encryption. Eike Kiltz. TCC 2006:
Encryption over the Integers. Marten van Dijk, Craig Gentry,
Shai Halevi, Vinod Vaikuntanathan. EUROCRYPT 2010: 24-43. Paul Fermé.
- Predicate Encryption
Supporting Disjunctions, Polynomial Equations, and Inner Products.
Jonathan Katz, Amit Sahai, Brent Waters. Eurocrypt 2008.
- Predicate encryption for circuits from LWE. Sergey Gorbunov, Vinod Vaikuntanathan, Hoeteck Wee. CRYPTO 2015.
- New Techniques
for Dual System Encryption and Fully Secure HIBE with Short
Ciphertexts. Allison Lewko, Brent Waters. TCC 2010. Looking at this article may prove
- On-the-Fly Multiparty
Computation on the Cloud via Multikey Fully Homomorphic
Encryption. Adriana López-Alt, Eron Tromer, Vinod
Vaikuntanathan. STOC 2012: 1219-1234.
Fast cryptographic primitives and circular-secure encryption from hard learning problems. Benny Applebaum, David Cash, Chris Peikert, Amit Sahai. CRYPTO 2009. Willy Quach.
Lattice Basis Delegation in Fixed Dimension and
Shorter-Ciphertext Hierarchical IBE. Shweta Agrawal, Dan Boneh and Xavier Boyen. CRYPTO 2010. Willy Quach.
Robustness of the Learning with Errors Assumption. Shafi Golwasser, Yael Kalai, Chris Peikert and Vinod Vaikuntanathan. ICS 2010. Paul Fermé.
Benoît Libert and Damien Stehlé.