Welcome to the resource topic for 2023/452
Title:
Piano: Extremely Simple, Single-Server PIR with Sublinear Server Computation
Authors: Mingxun Zhou, Andrew Park, Elaine Shi, Wenting Zheng
Abstract:We construct a sublinear-time single-server pre-processing Private Information Retrieval
(PIR) scheme with optimal client storage and server computation (up to poly-logarithmic factors), only relying on the assumption of the existence of One Way Functions (OWF). Our scheme achieves amortized \tilde{O}(\sqrt{n}) online server computation and client computation and O(\sqrt{n})
online communication per query, and requires \widetilde{O}_\lambda(\sqrt{n}) client storage. Unlike prior single-server PIR schemes that rely on heavy cryptographic machinery such as Homomorphic Encryption, our scheme only utilizes lightweight cryptography such as PRFs, which is easily instantiated in practice. To our knowledge, this is the first practical implementation of a single-server sublinear-time PIR scheme.
Compared to existing linear time single-server solutions, our schemes are faster by 10-300\times and are comparable to the fastest two-server schemes. In particular, for a 100GB database of 1.6 billion entries, our experiments show that our scheme has less than 40ms online computation time on a single core.
ePrint: https://eprint.iacr.org/2023/452
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 .