Piano: Extremely Simple, Single-Server PIR with Sublinear Server Computation

ePrint Report: Piano: Extremely Simple, Single-Server PIR with Sublinear Server Computation

Mingxun Zhou, Andrew Park, Elaine Shi, Wenting Zheng

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 …

client communication computation encryption eprint report functions homomorphic encryption information lambda poly private query report server shi simple single storage