Workshop on Lattices with Symmetry

August 12-16, 2013
at the University of California, Irvine

Workshop Description:
The workshop centered on some ideas and problems that arise in number theory, cryptanalysis, and the study of lattices, number rings, and the ideal lattices that arise in cryptography. For large ranks, there is no good algorithm that decides whether a given lattice has an orthonormal basis. But when the lattice is given with enough "symmetry", one can construct a polynomial time algorithm based on the work of Gentry and Szydlo. The algorithm operates in an "infrastructure"-like group familiar from Arakelov theory. The methods belong to algorithmic algebraic number theory, and the ideas should be applicable to a range of questions in number theory and cryptography. The workshop brought together people interested in cryptography and/or algorithmic number theory, in order to learn the theory and explore applications. Tutorials brought participants up to speed on the background.

We especially wanted to encourage discussion and interaction. To achieve this, only the first day's schedule was set in advance, and the remainder of the schedule was determined a day in advance, based on how things were going and on feedback from the participants, to accommodate the interests and needs of the participants.

Schedule (sorry for the occasional missing or noisy audio):
Monday August 12
9:30-10 Refreshments
10-12 Craig Gentry on the Gentry-Szydlo Algorithm   video   slides
2-3 Mike Szydlo on the Gentry-Szydlo Algorithm   video   slides
3-3:30 Refreshments
3:30-5:30 Hendrik Lenstra on Lattices with Symmetry   video   preprint
6-8:15 Picnic Dinner at Vista Bonita Park (provided by workshop)
Tuesday August 13
9-9:30 Refreshments
9:30-10:30 Daniele Micciancio on Foundations of Lattice Based Crypto   video   slides
11-12 Jeff Hoffstein on NTRU and Lattice-Based Signatures   video
12-12:15 Group Photo
2-3 Shai Halevi on Fully Homomorphic Encryption   video   slides
3-3:30 Refreshments
3:30-4:30 Vadim Lyubashevsky on Ring-LWE   video   slides
4:30-6 Hendrik Lenstra on Lattices with Symmetry   video
Wednesday August 14
9-9:30 Refreshments
9:30-10:30 Sanjam Garg on Multilinear Maps from Ideal Lattices   video   slides
11-12 Daniele Micciancio on Lattice Algorithms   video   related slides
2-3 Sean Hallgren on Quantum Algorithms   video
3-3:25 Refreshments
3:25-4:15 Rene Schoof on Testing Invertibility   video
4:30+ Travel to Balboa Peninsula
5:45-8 Sunset Cruise (with pizza) in Newport Beach
Thursday August 15
9-9:30 Refreshments
9:30-10:30 Hendrik Lenstra on Finding Roots of Unity   video
11-12 Craig Gentry on a Simple (Leveled) Fully Homomorphic Encryption Scheme and Thoughts on Bootstrapping   video   slides
2-3 Vadim Lyubashevsky on Lattice-Based Digital Signatures   video
3-3:30 Refreshments
3:30-4:30 Daniele Micciancio on Decoding Barnes-Wall Lattices in Polynomial Time   video   ref 1   ref 2
5-5:50 Open Problems Session led by Daniele Micciancio
Friday August 16
9-9:30 Refreshments
9:30-10:30 Shai Halevi on Field Switching   video   slides
11-12 Hendrik Lenstra on Lattices over CM-orders   video
2-3 Shai Halevi---Follow-up on Multilinear Maps   video
3 Wrap-up by Alice Silverberg

Location: Natural Sciences II, Room 1201


Sponsors: The workshop was funded by DARPA and by the UCI Edward and Vivian Thorp Chair Endowment.

Program Committee:
Alice Silverberg (Chair)
Craig Gentry
Hendrik W. Lenstra, Jr

Local Organizing Committee:
Karl Rubin
Alice Silverberg