Welcome to the resource topic for 2024/482
Title:
Single Server PIR via Homomorphic Thorp Shuffles
Authors: Ben Fisch, Arthur Lazzaretti, Zeyu Liu, Charalampos Papamanthou
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.
ePrint: https://eprint.iacr.org/2024/482
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .