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:

Identity-based encryption,
Attribute-based encryption,
Functional encryption,
Deterministic encryption,
Proxy-reencryption,
Fully homomorphic encryption,
Secure multi-party computations.

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

Understand the definitions of advanced cryptographic primitives, their associated security requirements and their limits.
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.

Prerequisites

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.

Evaluation

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.

Identity-Based 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.
Functional Encryption 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.
~~Functional Encryption for Inner Product Predicates from Learning with Errors. Shweta Agrawal, David Mandell Freeman, Vinod Vaikuntanathan. ASIACRYPT 2011: 21-40.~~ Yassine Hamoudi.
Space-Efficient 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: 581-600.
~~Fully Homomorphic 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 helpful.
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é.

Instructors

Benoît Libert and Damien Stehlé.