“Expressive Cryptography”: opening the future of Information Security

Monday, April 2, 2012 - 11:54am


Monday, April 9, 2012
11:00 – 12:00 PM
Computer Science Conference Room, Harold Frank Hall Rm. 1132

HOST: Giovanni Vigna

SPEAKER: Xavier Boyen
Prime Cryptography

Title: “Expressive Cryptography”: opening the future of Information Security


The last decade has seen a wonderful revival of the field of
cryptography, primarily owing to a couple of factors: (1) the discovery
of “new” mathematical tools of unsuspected flexibility; (2) the
construction from same of novel cryptographic schemes with amazing

The “revolution” started in earnest with the invention, circa 2000, of
Identity-Based Encryption from (so-called) Bilinear Pairings: a huge
step forward in “expressivity” compared to the bare public-key systems
of the time. Since then, the revolution has pressed toward even greater
expressivity, ranging from Functional Encryption to Flexible Credentials
and so many other things in between. Most of it, however, still relies
solely on the original tool of Bilinear Pairings on elliptic curves.

Lately, circa 2008, the revolution has branched into a parallel path,
stemming from the realization that likewise “expressive cryptosystems”
could be built on a completely different mathematical foundation,
involving “simple” high-dimensional integer subspaces or Lattices. While
trickier in many ways, lattices have unique advantages such as ease of
implementation and resistance to quantum-computing cryptanalysis.

In this talk, I will review some key milestones of this revolution, and
draw parallels between well-known “ancient” Pairing-based expressive
cryptosystems, and their lesser-known (but by no means lesser)
Lattice-based analogues at the cutting edge of current research. I will
attempt to summarize at a high level the inner working of these
intricate latter systems, by drawing bridges from the more easily
understood principles of the former kind.

These results, taken in their globality, should convince the listener
that there are fantastic further breakthroughs looming around the corner
in this broad area of “expressive crypto”, especially from lattices, but
that the search will be very technically challenging, and may require a
new way of thinking altogether. One unique aspect of the approach I
propose, is not to focus on one particular technique, but rather seek to
gain a global understanding of the strengths and weaknesses,
similarities and differences, between all possible tools, and find ways
to connect them.

The primary motivation for it all, is the wealth of real-world
applications that that all these “expressive cryptosystems” promise to
bring about in so many areas; though many of them are still a distant
dream at this point. Realizing them is a long-term challenge, but one
whose rewards will be well worth the effort.


Xavier Boyen received his Ph.D. from Stanford in 2003. Since then, he
has held a number of positions ranging from begin the “one-man research
lab” at a Silicon Valley start-up, to a professorship in his native
country of Belgium, to being a principal in a couple of joint ventures
of crypto research. Xavier’s interests are broad and multidisciplinary,
with a particular focus on constructive, elegant cryptographic solutions
that address true challenges faced in real-world, whether already
recognized or not.

Xavier’s accomplishments include about 50 research papers having earned
over 5,000 citations, a famous cryptosystem standardized and licensed to
2 million users, a dozed invited conference lectures across 5
continents, and many wonderful memories shared with research partners