Paper 2024/1165

Respire: High-Rate PIR for Databases with Small Records

Alexander Burton, The University of Texas at Austin
Samir Jordan Menon, Blyss
David J. Wu, The University of Texas at Austin
Abstract

Private information retrieval (PIR) is a key building block in many privacy-preserving systems, and recent works have made significant progress on reducing the concrete computational costs of single-server PIR. However, existing constructions have high communication overhead, especially for databases with small records. In this work, we introduce Respire, a lattice-based PIR scheme tailored for databases of small records. To retrieve a single record from a database with over a million 256-byte records, the Respire protocol requires just 6.1 KB of online communication; this is a 5.9x reduction compared to the best previous lattice-based scheme. Moreover, Respire naturally extends to support batch queries. Compared to previous communication-efficient batch PIR schemes, Respire achieves a 3.4-7.1x reduction in total communication while maintaining comparable throughput (200-400 MB/s). The design of Respire relies on new query compression and response packing techniques based on ring switching in homomorphic encryption.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Major revision. ACM CCS
Keywords
PIRprivate information retrievallatticeshomomorphic encryption
Contact author(s)
amacburton @ gmail com
samir @ blyss dev
dwu4 @ cs utexas edu
History
2024-07-19: approved
2024-07-18: received
See all versions
Short URL
https://ia.cr/2024/1165
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/1165,
      author = {Alexander Burton and Samir Jordan Menon and David J. Wu},
      title = {Respire: High-Rate {PIR} for Databases with Small Records},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1165},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1165}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.