Talk Abstracts

Thursday, 6 May

Hendrik Lenstra
Introduction to Lattices and the LLL Algorithm

Oded Regev
The Complexity of Lattice Problems

In this talk I will survey the state-of-the-art regarding the computational complexity of lattice problems. In order to introduce the techniques of Fourier analysis and Gaussian measures on lattices, I will describe in some detail a result of Aharonov and myself, namely, that the "Gap-Closest Vector Problem" (GapCVP) is in the complexity class NP intersect coNP. The ideas used in the proof are heavily used in the construction of lattice-based encryption in general, and public-key cryptography in particular.

Chris Peikert
Lattices: From Worst-Case, to Average-Case, to Cryptography

In this talk I will introduce the core tools and techniques for working with lattices from a cryptographic perspective. With these in hand, I will introduce the two main hard average-case problems used for cryptography, and sketch how they relate to worst-case lattice problems. I will conclude by describing how to combine all these tools to yield crypto schemes ranging from hash functions and public-key encryption, to rich protocols such as identity-based encryption.

Friday, 7 May

Eike Kiltz
Lattice-based Cryptography: Advanced Protocols

This talk describes some recently discovered constructions of advanced cryptographic protocols using lattices. A main focus will be constructions of (hierarchical) identity-based encryption schemes.

Chris Peikert
The Peculiar Properties of Lattice-Based Encryption

Lattice-based encryption schemes can have some surprising and unique security properties. I will discuss two recent examples:

• A "circular-secure" cryptosystem that is essentially as efficient as the "standard" lattice-based construction.
• A "bideniable" scheme that allows a sender and receiver, having already performed some encrypted communication, to produce "fake" (but legitimate-looking) random coins and secret keys that open the ciphertext as any other desired message. This is the first construction a bideniable public-key cryptosystem, and the first "noncommitting" scheme requiring no interaction.

This talk is based on work with colleagues Benny Applebaum, David Cash, and Amit Sahai (CRYPTO 2009), and Adam O'Neill (work in submission).

Oded Regev
On Ideal Lattices and Learning with Errors Over Rings

The "learning with errors" (LWE) problem is to distinguish random linear equations that have been perturbed by a small amount of noise from truly uniform ones. The problem has been shown to be as hard as worst-case lattice problems, and in recent years it has served as the foundation for a plethora of cryptographic applications. Unfortunately, these applications are rather inefficient due to an inherent quadratic overhead in the use of LWE. An important open question was whether LWE and its applications could be made truly efficient by exploiting extra algebraic structure, as was done for lattice-based hash functions (and related primitives).

We resolve this question in the affirmative by introducing an algebraic variant of LWE called \emph{ring-LWE}, and proving that it too enjoys very strong hardness guarantees. Specifically, we show that the ring-LWE distribution is pseudorandom, assuming that worst-case problems on ideal lattices are hard for polynomial-time quantum algorithms. Applications include the first truly practical lattice-based public-key cryptosystem with a supporting security proof; moreover, many of the other applications of LWE can be made much more efficient through the use of ring-LWE. Finally, the algebraic structure of ring-LWE might lead to new cryptographic applications previously not known to be based on LWE.

Joint work with Vadim Lyubashevsky and Chris Peikert

Nigel Smart
Efficient Fully Homomorphic Encryption Without Lattices (Almost²)

I will show how one can construct an (almost) efficient homomorphic encryption scheme which (almost) avoids the complete use of lattices. Indeed the scheme is based purely on polynomial arithmetic and it's security is related to long standing problems in Computational Algebraic Number Theory. The scheme does still have lattices hidden in the background, as it is essentially a specialization of Gentry's scheme, but it can be described without the need for any lattice theory.

Erwin Torreao Dassen
Using Layered Lattices

The concept of a layered lattice is a recently discovered generalization of lattices that is well suited for applications. We give a short introduction to them and their lattice base reduction algorithm, which is based on the classical LLL. We then give examples of their use.