Welcome to the resource topic for 2024/829
Title:
Multi-Server Doubly Efficient PIR
Authors: Arthur Lazzaretti, Zeyu Liu, Ben Fisch, Charalampos Papamanthou
Abstract:Doubly Efficient Private Information Retrieval (DEPIR) pertains to a Private Information Retrieval (PIR) scheme with both near-linear server-side preprocessing time and sublinear query time. Very recently, Lin et al. (STOC '23) devised the first single-server DEPIR scheme from standard assumptions. However, their work left one major question open: can we build a DEPIR scheme in the multi-server setting, without relying on heavy cryptographic machinery?
In this work, we propose the first doubly efficient information-theoretic PIR scheme, in the multi-server setting. For a database of size N, our scheme allows servers to answer an infinite number of client queries in N^{o(1)} time, after a single preprocessing phase which takes N^{1+o(1)} time. Our result is only a N^{o(1)} factor from the lower bound proven by Persiano and Yeo (SODA '22) for this setting.
In addition, we devise a second information-theoretic PIR scheme which pushes the state of the art for the setting where the number of servers is more constrained. It achieves equally fast query times as our first scheme above, and a preprocessing time of N^{2+o(1)}.
ePrint: https://eprint.iacr.org/2024/829
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 .