Paper 2022/368

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

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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Major revision. IEEE Symposium on Security and Privacy 2022
Keywords
private information retrievalfully homomorphic encryption
Contact author(s)
menon samir @ gmail com
dwu4 @ cs utexas edu
History
2022-03-22: received
Short URL
https://ia.cr/2022/368
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/368,
      author = {Samir Jordan Menon and David J.  Wu},
      title = {Spiral: Fast, High-Rate Single-Server PIR via FHE Composition},
      howpublished = {Cryptology ePrint Archive, Paper 2022/368},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/368}},
      url = {https://eprint.iacr.org/2022/368}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.