## CryptoDB

### Paper: Compressible FHE with Applications to PIR

Authors: Craig Gentry Shai Halevi DOI: 10.1007/978-3-030-36033-7_17 Search ePrint Search Google 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 2.3 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 \mathsf {\lambda }+ \log \log \log N)$, where $\mathsf {\lambda }$ is the security parameter and N is the number of database files, which are assumed to be sufficiently large.
##### BibTeX
@article{tcc-2019-30003,
title={Compressible FHE with Applications to PIR},
booktitle={Theory of Cryptography},
series={Lecture Notes in Computer Science},
publisher={Springer},
volume={11892},
pages={438-464},
doi={10.1007/978-3-030-36033-7_17},
author={Craig Gentry and Shai Halevi},
year=2019
}