RISC Seminars (Research on Information Security and Cryptology)
Archives: [2024] [2023] [2022] [2021] [2020] [2019] [2018] [2017] [2016] [2015] [2014] [2013] [2012] [2011] [2010] [2009] [2008] [2007] [2006] [2005] [2004] [List of Speakers](To receive information about upcoming seminars, register for the RISC mailing list.)
[print]
Workshop Public Key Cryptography and the Geometry of Numbers
A two-day workshop on the use of lattices in the construction of public-key cryptographic protocols. The first day will provide an introduction to the subject, and the second day will focus on recent research results.
Further information about the venue and program can be found on the
workshop website.
Date: | May 6-7 |
Location: | KNAW Trippenhuis, Tinbergenzaal, Amsterdam |
Schedule: | |
Thursday, May 6 | |
13:30 | Hendrik Lenstra (Universiteit Leiden): Introduction to Lattices and the LLL Algorithm |
15:00 | Oded Regev (Tel-Aviv University, Israel): The Complexity of Lattice Problems Abstract: 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.
|
16:30 | Chris Peikert (Georgia Institute of Technology, USA): From Worst-Case, to Average-Case, to Cryptography Abstract: 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.
|
18:00 | Cocktail reception |
Friday, May 7 | |
9:30 | Eike Kiltz (CWI): Lattice-based Cryptography: Advanced Protocols Abstract: 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.
|
11:00 | Chris Peikert (Georgia Institute of Technology, USA): The Peculiar Properties of Lattice-Based Encryption Abstract: Lattice-based encryption schemes can have some surprising and unique
security properties. I will discuss two recent examples:
|
12:15 | Lunch |
13:30 | Oded Regev (Tel-Aviv University, Israel): On Ideal Lattices and Learning with Errors Over Rings Abstract: 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 |
15:00 | Nigel Smart (University of Bristol, UK): Efficient Fully Homomorphic Encryption Without Lattices (Almost2) Abstract: 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.
|
16:30 | Erwin Torreao Dassen (Universiteit Leiden): Using Layered Lattices Abstract: 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.
|
0.01318s c