Paper 2019/733
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.
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- FHEInformation RatePIR
- Contact author(s)
-
shaih @ alum mit edu
craigbgentry @ gmail com - History
- 2019-10-24: revised
- 2019-06-20: received
- See all versions
- Short URL
- https://ia.cr/2019/733
- License
-
CC BY