Homomorphic Encryption from Ring Learning with Errors


January 10, 2012


Michael Naehrig


Cryptography Group at MSR Redmond.


The prospect of outsourcing an increasing amount of data storage and management to cloud services raises many new privacy concerns that can be satisfactorily addressed if users encrypt the data they send to the cloud. If the encryption scheme is homomorphic, the cloud can still perform meaningful computations on the data, even though it is encrypted.

In fact, we now know a number of constructions of fully homomorphic encryption schemes that allow arbitrary computation on encrypted data. In the last two years, solutions for fully homomorphic encryption have been proposed and improved upon, but all currently available options seem to be too inefficient to be used in practice. However, for many applications it is sufficient to implement somewhat homomorphic encryption schemes, which support a limited number of homomorphic operations. They can be much faster, and more compact than fully homomorphic schemes.

This talk will focus on describing the recent somewhat homomor- phic encryption scheme of Brakerski and Vaikuntanathan, whose security relies on the ring learning with errors (RLWE) problem.


Michael Naehrig

Michael Naehrig is a Post Doc Researcher in the Cryptography Group at MSR Redmond. He conducted his undergraduate studies in Mathematics at RWTH Aachen University, Germany, and received his Ph.D. from Eindhoven University of Technology, The Netherlands, under the supervision of Tanja Lange. His main research interests are the construction of pairing-friendly elliptic curves, pairing algorithms and the efficient implementation of cryptographic pairings.