International Association for Cryptologic Research
The authors describe a comparatively simple Fully Homomorphic Encryption (FHE) scheme based on the Learning With Errors (LWE) problem. In previous LWE-based FHE schemes, multiplication is a complicated and expensive step involving \"Relinearization\". In this paper, they propose a new technique for building FHE schemes that they call the approximate eigenvector method. In their scheme, for the most part, homomorphic addition and multiplication are just matrix addition and multiplication. This makes their scheme both asymptotically faster and (they believe) easier to understand.