Vadim Lyubashevsky: Lattice-Based Cryptography: From Practice to Theory to Practice

Abstract

Lattice-based cryptography is currently seen as one of the most promising alternatives to cryptography based on number theory. The major advantages of lattice-based protocols is that they are faster than ones based on number theory and they also seem to be resistant against quantum attacks. The origins of lattice-based cryptography, in the mid 90's, can be attributed to the 'practical' NTRU cryptosystem and the 'theoretical' constructions of Ajtai. Initially, these areas developed independently, but work done in the past few years showed surprising connections between the two and there has been a lot of recent success in bridging the gap between the practical and theoretical aspects of lattice-based cryptography. On the one hand, we have used the theoretical ideas to construct new practical, provably-secure schemes, and on the other hand, we have also been able to prove that (with a few modifications) the early practical schemes are actually provably secure. In this talk, I will explain the current hardness assumptions used for constructing efficient lattice-based schemes as well as present some sample constructions.