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 |
| 12-2 | |
| 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 |
| 12:15-2 | |
| 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 |
| 12-2 | |
| 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 |
| 12-2 | |
| 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 |
| 12-2 | |
| 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