Smoothening Functions and the Homomorphism Learning Problem
Ruiz Lopez, A Luis
Abstract
This thesis is an exploration of certain algebraic and geometrical aspects of the Learning With Errors (LWE) problem introduced in Reg05. \n\tOn 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. \n\tOn the geometric front, we explore the importance of the Gaussian distribution for the existing relationships between LWE and lattice problems. \n\tWe 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.