Smoothening Functions and the Homomorphism Learning Problem

Abstract

This thesis is an exploration of certain algebraic and geometrical aspects of the Learning With Errors (LWE) problem introduced in Reg05. On the algebraic front, we view it as a Learning Homomorphisms with Noise problem, and provide a generic construction of a public-key cryptosystem based on this generalization. On the geometric front, we explore the importance of the Gaussian distribution for the existing relationships between LWE and lattice problems. We prove that their smoothing properties does not make them special, but rather, the fact that it is infinitely divisible and l2 symmetric are important properties that make the Gaussian unique.