SHIELD: Scalable Homomorphic Implementation of Encrypted Data-Classifiers

Alhassan Khedr; Glenn Gulak; Vinod Vaikuntanathan

Paper 2014/838

SHIELD: Scalable Homomorphic Implementation of Encrypted Data-Classifiers

Alhassan Khedr, Glenn Gulak, and Vinod Vaikuntanathan

Abstract

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 Ring Learning With Errors (RLWE) based implementation of a variant of the HE system recently proposed by Gentry, Sahai and Waters (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 CPU platforms) compared to IBM HElib for these applications. Our system is built to be easily portable to GPUs (unlike IBM HElib) which results in an additional speedup of up to a factor of 103.5x to offer an overall speedup of 1035x.

Note: Fixed formatting problems with the \paragragh directive.

Metadata

Available format(s): PDF
Publication info: Published elsewhere. IEEE Transactions on Computers
DOI: 10.1109/TC.2015.2500576
Keywords: Homomorphic Encryption FHE Ring LWE Bayesian Filter Email Spam Filter Spam Filter Secure Search Decision Trees Implementation GPU.
Contact author(s): alhassan f khedr @ gmail com
History: 2016-04-28: last of 6 revisions; 2014-10-20: received; See all versions
Short URL: https://ia.cr/2014/838
License: CC BY

BibTeX

@misc{cryptoeprint:2014/838,
      author = {Alhassan Khedr and Glenn Gulak and Vinod Vaikuntanathan},
      title = {{SHIELD}: Scalable Homomorphic Implementation of Encrypted Data-Classifiers},
      howpublished = {Cryptology {ePrint} Archive, Paper 2014/838},
      year = {2014},
      doi = {10.1109/TC.2015.2500576},
      url = {https://eprint.iacr.org/2014/838}
}