Welcome to the resource topic for 2022/830
Title:
Single Server PIR with Sublinear Amortized Time and Polylogarithmic Bandwidth
Authors: Arthur Lazzaretti and Charalampos Papamanthou
Abstract:In Private Information Retrieval (PIR), a client wishes to access an index i from a public n-bit database without revealing any information about this index. Recently, a series of works starting with the seminal paper of Corrigan-Gibbs et al. (Eurocrypt 2020) have introduced offline-online PIR schemes with \tilde{O}(\sqrt{n}) (amortized) server time, \tilde{O}(\sqrt{n}) (amortized) bandwidth and no additional storage at the server, in both the single-server and two-server models. As a followup to this work, Shi et al. (CRYPTO 2021) further decreased the bandwidth to polylogarithmic, but only in the two-server model. In this paper we fill this gap by constructing the first single-server PIR with \tilde{O}(\sqrt{n}) amortized server time and polylogarithmic bandwidth. Central to our approach is a new cryptographic primitive that we call extended puncturable pseudorandomn set: With an extended puncturable pseudorandom set, one can represent a random set succinctly (e.g., with a fixed-size key), and can, at the same time both add and remove elements from the set, by manipulating the key. This extension improves previously-proposed constructions that supported only removal, and could have further applications. We acknowledge our work has limitations; more work is required to bring our ideas closer to practice, due to the use of cryptographic primitives such as FHE (only in the offline phase) and LWE-based privately-puncturable PRFs. However, our protocol yields the best asymptotic complexities in single-server PIR to date and we believe it is an important step towards eventually building a practical PIR scheme.
ePrint: https://eprint.iacr.org/2022/830
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 .