**Compressible FHE with Applications to PIR**

*Craig Gentry and Shai Halevi*

**Abstract: **Homomorphic encryption (HE) is often viewed as impractical, both in communication and computation. Here we provide an additively homomorphic encryption scheme based on (ring) LWE with nearly optimal rate ($1-\epsilon$ for any $\epsilon>0$). Moreover, we describe how to compress many Gentry-Sahai-Waters (GSW) ciphertexts (e.g., ciphertexts that may have come from a homomorphic evaluation) into (fewer) high-rate ciphertexts.

Using our high-rate HE scheme, we are able for the first time to describe a single-server private information retrieval (PIR) scheme with sufficiently low computational overhead so as to be practical for large databases. Single-server PIR inherently requires the server to perform at least one bit operation per database bit, and we describe a rate-(4/9) scheme with computation which is not so much worse than this inherent lower bound. In fact it is probably less than whole-database AES encryption -- specifically about 1.5 mod-$q$ multiplication per database byte, where $q$ is about 50 to 60 bits. Asymptotically, the computational overhead of our PIR scheme is $\tilde{O}(\log \log \lambda + \log \log \log N)$, where $\lambda$ is the security parameter and $N$ is the number of database files, which are assumed to be sufficiently large.

**Category / Keywords: **public-key cryptography / FHE, Information Rate, PIR

**Date: **received 19 Jun 2019

**Contact author: **shaih at alum mit edu, craigbgentry@gmail com

**Available format(s): **PDF | BibTeX Citation

**Version: **20190620:115402 (All versions of this report)

**Short URL: **ia.cr/2019/733

[ Cryptology ePrint archive ]