Paper 2024/1165
Respire: High-Rate PIR for Databases with Small Records
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
-
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}
}
