Expressive Cryptography

By Xavier Boyen.

Special Seminar Sequence on Cryptography organized by SKLOIS and sponsored by CACR, Beijing, China, December 2012.

Featured course (4 lectures).


The invention of public keys, in the seventies, was a conceptual leap in the expressive power of encryption schemes. For the first time, it allowed the sender of a message to express, cryptographically, who its intended recipient was, by means of a name embodied by the public key that was separate from the ability to decrypt. This made large-scale encryption a practical possibility, and eventually led to the advent of electronic commerce as we know it.
An equally significant transition is currently underway. Just like public keys gave us the first non-trivial cryptographic naming scheme (in the form of a random-looking public dictionary mapping recipients to their keys), more recently a number of spectacular advances has expanded this metaphor with a pronounceable vocabulary, a working grammar, and even some semantic inference abilities, to express who is authorized to decrypt and who is not.

In this course, consisting of four lectures of three hours each, we shall take a detailed look at the ongoing development of this fascninating branch of cryptography.

Lecture 1. From Public-Key to Functional Encryption
In this lecture, we shall introduce, both informally and in a more model-oriented way, the many flavors of expressive encryption, from identity-based and its many variants, to the most general forms of attribute-based and functional encryption. Our focus for this lecture shall be on the definition of the various notions, and the study of potential applications that motivate them.

Lecture 2. Bilinear Maps under the Hood
In this lecture, we take a closer look at the actual realizations of the cryptographic notions introduced earlier, with a particular focus on constructions based on bilinear maps. We shall begin with a primer on this curious mathematical object, with simple properties that are at once powerful and easy to abstract. We shall then study, at a mostly intuitive level, some of the most insightful ways in which this simple mathematical abstraction has been put to use in sometimes very sophisticated and expressive encryption schemes.

Lecture 3. Expressive Signatures and Authentication
In this lecture, we turn our attention to the other pillars of cryptography, besides encryption: authentication and zero knowledge. While encryption is the art of securing confidentiality, signatures and authentication are the art of establishing provenance, and zero knowledge is that of convincing without revealing. Authentication, not encryption, is actually the primary use of crypto in real applications; and a recent trend, especially in the context of large groups and organizations, has seen a real need for expressive signatures, that allow one or multiple signers to delineate very carefully what aspects of their signing authority is to be revealed or concealed. We shall review a number of such constructions.

Lecture 4. Post-Quantum Cryptography from Lattices
While the main thrust of research in expressive cryptography remains based on bilinear maps, recent advances in euclidean lattice-based cryptography has shown completely new ways of achieving comparable results---plus the unique advantage of conjectured resistance to quantum-computer cryptanalysis. In this lecture, we shall give an introduction to this hot new area of cryptographic research, with an emphasis on what unites and divides lattice-based and non-lattice constructions.


- Lecture 1 (Intro & Basic Notions) : presentation slides (HTML)
- Lectures 2–3 (Pairing Systems) : presentation slides (HTML)
- Lectures 3–4 (Lattice Systems) : presentation slides (HTML)

Unless indicated otherwise, these documents are Copyright © Xavier Boyen; all rights reserved in all countries.
Back to Xavier's homepage