Lattice-based cryptography: an introduction

Vortrag von Cecilia Boschini

Datum: 08.11.17  Zeit: 15.00 - 16.00  Raum: Y27H12

Lattice-based cryptography is defined by Peikert as the use of conjectured hard problems over point lattices in R^n as the foundation to build cryptographic schemes. In the last 20 years, it has emerged along with code-based and multivariate cryptography as one of the main candidate quantum-secure cryptosystem. Indeed, in addition to the supposed resistance against quantum attacks, lattice problems guarantee security under worst-case hardness assumptions and working over lattices allows to build a wide range of schemes that were hard to construct under factoring or DDH assumptions, like fully homomorphic encryption. Moreover, algorithms built over lattices are asymptotically efficient and highly parallelizable.
In this introductory talk, we aim to give the audience the intuition behind lattice-based cryptography to lay the necessary foundations for further in-depth analysis. After introducing lattices as a mathematical concept, we will focus on how to build preimage sampleable functions, i.e. functions that are easy to compute and hard to invert without knowledge of a trapdoor. Preimage sampleable functions are a fundamental cryptographic primitive, as they can be used to build digital signatures and identity-based encryption.