### 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 FHE ciphertexts that may have come from a homomorphic evaluation (e.g., of the Gentry-Sahai-Waters (GSW) scheme), 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 faster than whole-database AES encryption -- specifically under 1.8 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 \secparam + \log \log \log N)$, where $\secparam$ is the security parameter and $N$ is the number of database files, which are assumed to be sufficiently large.

Available format(s)
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in TCC 2019
Keywords
FHEInformation RatePIR
Contact author(s)
shaih @ alum mit edu
craigbgentry @ gmail com
History
2019-10-24: revised
See all versions
Short URL
https://ia.cr/2019/733

CC BY

BibTeX

@misc{cryptoeprint:2019/733,
author = {Craig Gentry and Shai Halevi},
title = {Compressible FHE with Applications to PIR},
howpublished = {Cryptology ePrint Archive, Paper 2019/733},
year = {2019},
note = {\url{https://eprint.iacr.org/2019/733}},
url = {https://eprint.iacr.org/2019/733}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.