International Association
for Cryptologic Research

Homomorphic encryption (HE) systems enable computations on encrypted data, without decrypting and without knowledge of the secret key. In this work, we describe an optimized RLWE-based implementation of a variant of the HE system recently proposed by Gentry, Sahai and Waters (henceforth called GSW). Although this system was widely believed to be less efficient than its contemporaries, we demonstrate quite the opposite behavior for a large class of applications.

We first highlight and carefully exploit the algebraic features of the system to achieve significant speedup over the state-of-the-art HE implementation, namely the IBM homomorphic encryption library (HElib). We introduce several optimizations on top of our HE implementation, and use the resulting scheme to construct a homomorphic Bayesian spam filter, secure multiple keyword search, and a homomorphic evaluator for binary decision trees.

Our results show a factor of 10x improvement in performance (under the same security settings and platforms) compared to HElib for these applications. Our system is built to be easily portable to GPUs (unlike HElib) which results in an additional speedup of up to a factor of 10x to offer an overall speedup of 100x.