COLLOQUIUM: Foundations of Lattice-based Cryptography (November 2017)

Speaker: Divesh Aggarwal, Centre for Quantum Technologies, NUS

Abstract:
Lattice-based cryptosystems are perhaps the most promising candidates for post-quantum cryptography as they have strong security proofs based on worst-case hardness of computational lattice problems and are efficient to implement due to their parallelizable structure. Attempts to solve lattice problems by quantum algorithms have been made since Shor’s discovery of the quantum factoring algorithm in the mid-1990s, but have so far met with little success if any at all. The main difficulty is that the periodicity finding technique, which is used in Shor’s factoring algorithm and related quantum algorithms, does not seem to be applicable to lattice problems.

In this talk, I will survey some of the main developments in lattice cryptography over the last decade or so. The main focus will be on the Learning With Errors (LWE) and the Short Integer Solution (SIS) problems, their ring-based variants, their provable hardness under the intractability assumptions of lattice problems and their cryptographic applications.