The Versatility of Discrete Gaussians over Lattices
Leo Ducas
Abstract:
Discrete Gaussian distributions over Lattices have proved a very powerful tool to establish pure geometric results like Transference Theorems, as well as complexity results like co-NP proofs for GapSVP and the construction of Zero-Knowledge trapdoors for random lattices.
Gaussians are often used in cryptography in an almost black-box way, playing a role similar to the uniform distribution over finite groups. While this allows a convenient abstract presentation for many constructions, exploiting specific properties of gaussian distributions can be useful for certain purposes.
In this talk we will review some of the classic results mentioned above while presenting the fundamental properties of discrete Gaussian. We will also present some new results making specific use of the properties of those distributions, ranging from fine grained optimization for cryptosystems on embedded devices, up to the construction of new lattice based protocols. As an example of the latter, we give a one round Password Authenticated Key Exchange which is based on the notion of Smooth Projective Hash Functions (SPHF), a form of implicit proof system.