Paper 2024/1845

Single-Server Client Preprocessing PIR with Tight Space-Time Trade-off

Zhikun Wang, University of Illinois Urbana-Champaign
Ling Ren, University of Illinois Urbana-Champaign
Abstract

This paper partly solves the open problem of tight trade-off of client storage and server time in the client preprocessing setting of private information retrieval (PIR). In the client preprocessing setting of PIR, the client is allowed to store some hints generated from the database in a preprocessing phase and use the hints to assist online queries. We construct a new single-server client preprocessing PIR scheme. For a database with $n$ entries of size $w$, our protocol uses $S=O((n/T) \cdot (\log n + w))$ bits of client storage and $T$ amortized server probes over $n/T$ queries, where $T$ is a tunable online time parameter. Our scheme matches (up to constant factors) a $ST = \Omega(nw)$ lower bound generalized from a recent work by Yeo (EUROCRYPT 2023) and a communication barrier generalized from Ishai, Shi, and Wichs (CRYPTO 2024). From a technical standpoint, we present a novel organization of hints where each PIR query consumes a hint, and entries in the consumed hint are relocated to other hints. We then present a new data structure to track the hint relocations and use small-domain pseudorandom permutations to make the hint storage sublinear while maintaining efficient lookups in the hints.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Private Information Retrieval
Contact author(s)
nocrizwang @ gmail com
renling @ illinois edu
History
2024-11-11: approved
2024-11-10: received
See all versions
Short URL
https://ia.cr/2024/1845
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/1845,
      author = {Zhikun Wang and Ling Ren},
      title = {Single-Server Client Preprocessing {PIR} with Tight Space-Time Trade-off},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1845},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1845}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.