Paper 2024/482
Single Server PIR via Homomorphic Thorp Shuffles
Abstract
Private Information Retrieval (PIR) is a two player protocol where the client, given some query $x \in [N]$ interacts with the server, which holds a $N$-bit string $\textsf{DB}$ in order to privately retrieve $\textsf{DB}[x]$. In this work, we focus on the single server client-preprocessing model, initially idealized by Corrigan-Gibbs and Kogan (EUROCRYPT 2020), where the client and server first run some joint preprocessing algorithm, after which the client can retrieve elements of the server's string $\textsf{DB}$ privately in time sublinear in $N$. All known constructions of single server client-preprocessing PIR rely on one of the following two paradigms: (1) a linear-bandwidth offline phase where the client downloads the whole database from the server, or (2) a sublinear-bandwidth offline phase where however the server has to compute a large-depth ($O_\lambda (N)$) circuit under FHE in order to execute the preprocessing phase. In this paper, we construct a single server client-preprocessing PIR scheme which achieves both sublinear offline bandwidth (the client does not have to download the whole database offline) and a low-depth (i.e. $O_\lambda(1)$), highly parallelizable preprocessing circuit. We estimate that on a single thread, our scheme's preprocessing time should be more than 350x times faster than in prior single server client-preprocessing PIR constructions. Moreover, with parallelization, the latency reduction would be even more drastic. In addition, this construction also allows for updates in $O_\lambda (1)$ time, something not achieved before in this model.
Note: Minor editorial changes.
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- Private Information RetrievalThorp Shuffle
- Contact author(s)
-
benjamin fisch @ yale edu
arthur lazzaretti @ yale edu
zeyu liu @ yale edu
charalampos papamanthou @ yale edu - History
- 2024-03-27: revised
- 2024-03-23: received
- See all versions
- Short URL
- https://ia.cr/2024/482
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/482, author = {Ben Fisch and Arthur Lazzaretti and Zeyu Liu and Charalampos Papamanthou}, title = {Single Server PIR via Homomorphic Thorp Shuffles}, howpublished = {Cryptology ePrint Archive, Paper 2024/482}, year = {2024}, note = {\url{https://eprint.iacr.org/2024/482}}, url = {https://eprint.iacr.org/2024/482} }