Fully Homomorphic Encryption

A fully homomorphic encryption system enables computations to be performed on encrypted data without needing to first decrypt the data. In this line of work, we develop new implementations of fully homomorphic encryption and leverage FHE to construct new concretely-efficient privacy-preserving protocols.

Spiral: Fast, High-Rate Single-Server PIR via FHE Composition

Contributors: Samir Jordan Menon and David J. Wu

Abstract:

We introduce the Spiral family of single-server private information retrieval (PIR) protocols. Spiral relies on a composition of two lattice-based homomorphic encryption schemes: the Regev encryption scheme and the Gentry-Sahai-Waters encryption scheme. We introduce new ciphertext translation techniques to convert between these two schemes and in doing so, enable new trade-offs in communication and computation. Across a broad range of database configurations, the basic version of Spiral simultaneously achieves at least a 4.5x reduction in query size, 1.5x reduction in response size, and 2x increase in server throughput compared to previous systems. A variant of our scheme, SpiralStreamPack, is optimized for the streaming setting and achieves a server throughput of 1.9 GB/s for databases with over a million records (compared to 200 MB/s for previous protocols) and a rate of 0.81 (compared to 0.24 for previous protocols). For streaming large records (e.g., a private video stream), we estimate the monetary cost of SpiralStreamPack to be only 1.9x greater than that of the no-privacy baseline where the client directly downloads the desired record.

Resources:

BibTeX:
@inproceedings{MW22,
  author     = {Samir Jordan Menon and David J. Wu},
  title      = {\textsc{Spiral}: Fast, High-Rate Single-Server {PIR} via {FHE} Composition},
  booktitle  = {{IEEE} {S\&P}},
  year       = {2022}
}

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: David J. Wu and Jacob Haven

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.

Resources:

BibTeX:
@misc{WH12,
  author = {David J. Wu and Jacob Haven},
  title  = {Using Homomorphic Encryption for Large Scale Statistical Analysis},
  year   = {2012}
}

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}
}