Optimal Single-Server Private Information Retrieval
September 7, 2022 (GHC 8102)

Abstract: In this talk, we present a single-server Private Information Retrieval (PIR) scheme, which allows a client to query the database from the server privately. Our construction achieves optimal client storage and server computation (up to poly-logarithmic factors) tradeoff with polylogarithmic bandwidth, assuming the hardness of the Learning With Errors (LWE) problem.

In the setting of single-server PIR, the server stores an n-bit database, and the client wants to query some bits in the database privately and adaptively so that the server learns nothing about the indices of the queried bits. Our scheme uses $\tilde{O}(\sqrt{n})$ client storage, but it achieves amortized $\tilde{O}(\sqrt{n})$ server and client computation and $\tilde{O}(1)$ bandwidth per query, and completes in a single roundtrip, where the $\tilde{O}$ notation hides a security parameter and poly-logarithmic factor. In particular, we achieve a significant reduction in bandwidth over the state-of-the-art scheme by Corrigan-Gibbs, Henzinger, and Kogan (Eurocrypt’22): their scheme requires as much as $\tilde{O}(\sqrt{n})$ bandwidth per query, with comparable computational and storage cost as ours. Since they proved that their scheme is nearly optimal in terms of server computation and client storage, our scheme is additionally optimal in bandwidth.

This is a joint work with Wei-Kai Lin, Yiannis Tselekounis, and Elaine Shi.