Fully Homomorphic Encryption

A fully homomorphic encryption system enables computations to be performed on encrypted data without needing to first decrypt the data. Such cryptosystems have natural applications in secure, privacy-preserving computation as well as many other areas. Since Gentry's breakthrough work on fully homomorphic encryption (FHE) [Gen09], there has been much excitement and attention devoted towards developing practical FHE systems. In this project, we provide an implementation of Brakerski's scale-invariant somewhat homomorphic encryption (SWHE) system [Bra12]. In addition, we examine several candidate applications of FHE and SWHE systems, such as performing statistical analysis on encrypted data or evaluating private database queries over an encrypted database.

Fully Homomorphic Encryption: Cryptography's Holy Grail

Contributors: David J. Wu

Abstract:

For over 30 years, cryptographers have embarked on a quest to construct an encryption scheme that would enable arbitrary computation on encrypted data. Conceptually simple, yet notoriously difficult to achieve, cryptography’s holy grail opens the door to many new capabilities in our cloud-centric, data-driven world.

Resources:

BibTeX:
@article{Wu15,
  author    = {David J. Wu},
  title     = {Fully Homomorphic Encryption: Cryptography's Holy Grail},
  journal   = {{ACM} Crossroads},
  volume    = {21},
  number    = {3},
  pages     = {24--29},
  year      = {2015}
}

Using Homomorphic Encryption for Large Scale Statistical Analysis

Contributors: Dan Boneh, Jacob Haven, and David J. Wu

Abstract:

The development of fully homomorphic encryption schemes in recent years has generated considerable interest in the field of secure computing. In this paper, we consider the problem of performing statistical analysis on encrypted data. Specifically, we focus on two tasks: computing the mean and variance of univariate and multivariate data as well as performing linear regression on a multidimensional, encrypted corpus. Due to the high overhead of homomorphic computation, previous implementations of similar methods have been restricted to small datasets (on the order of a few hundred to a thousand elements) or data with low dimension (generally 1-4). In this paper, we first construct a working implementation of the scale-invariant leveled homomorphic encryption system in [Bra12]. Then, by taking advantage of batched computation as well as a message encoding technique based on the Chinese Remainder Theorem, we show that it becomes not only possible, but computationally feasible, to perform statistical analysis on encrypted datasets with over four million elements and dimension as high as 24. By using these methods along with some additional optimizations, we demonstrate the viability of using leveled homomorphic encryption for large scale statistical analysis.

Implementation Notes:

Our implementation is in C++ and uses the NTL number theory library. Much of the design and underlying algebraic primitives are derived from HElib. The codebase is freely distributed under the GNU General Public License (GPL).

Resources:

Private Database Queries using Somewhat Homomorphic Encryption

Contributors: Dan Boneh, Craig Gentry, Shai Halevi, Frank Wang, and David J. Wu

Abstract:

In a private database query system, a client issues queries to a database and obtains the results without learning anything else about the database and without the server learning the query. While previous work has yielded systems that can efficiently support disjunction queries, performing conjunction queries privately remains an open problem. In this work, we show that using a polynomial encoding of the database enables efficient implementations of conjunction queries using somewhat homomorphic encryption. We describe a three-party protocol that supports efficient evaluation of conjunction queries. Then, we present two implementations of our protocol using Paillier's additively homomorphic system as well as Brakerski's somewhat homomorphic cryptosystem. Finally, we show that the additional homomorphic properties of the Brakerski cryptosystem allow us to handle queries involving several thousand elements over a million-record database in just a few minutes, far outperforming the implementation using the additively homomorphic system.

Resources:

BibTeX:
@inproceedings{BGHWW13,
  author    = {Dan Boneh and Craig Gentry and Shai Halevi and Frank Wang and
               David J. Wu},
  title     = {Private Database Queries Using Somewhat Homomorphic Encryption},
  booktitle = {Applied Cryptography and Network Security ({ACNS})},
  year      = {2013}
}