[Resource Topic] 2024/765: Information-Theoretic Multi-Server PIR with Global Preprocessing

Welcome to the resource topic for 2024/765

Information-Theoretic Multi-Server PIR with Global Preprocessing

Authors: Ashrujit Ghoshal, Baitian Li, Yaohua Ma, Chenxin Dai, Elaine Shi


We propose a new unified framework to construct multi-server,
information-theoretic Private Information Retrieval (PIR) schemes
that leverage global preprocesing to achieve sublinear computation per query.
Despite a couple earlier attempts, our understanding of PIR schemes
in the global preprocessing model remains limited, and so far,
we only know a few sparse points in the broad design space.
With our new unified framework, we can
generalize the results of
Beimel, Ishai, and Malkin to broader parameter regimes, thus
enabling a tradeoff between bandwidth and computation.
Specifically, for any constant S > 1,
we can get an S-server scheme whose bandwidth consumption is as small as n^{1/(S+1) + \epsilon} while achieving computation in the n^\delta regime for some constant \delta \in (0, 1).
Moreover, we can get a scheme with polylogarithmic bandwidth and computation, requiring only polylogarithmic number of servers.

ePrint: https://eprint.iacr.org/2024/765

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 .