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

Mingxun Zhou; Andrew Park; Elaine Shi; Wenting Zheng

Paper 2023/452

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

Mingxun Zhou, Carnegie Mellon University

Andrew Park, Carnegie Mellon University

Elaine Shi, Carnegie Mellon University

Wenting Zheng, Carnegie Mellon University

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 online server computation and client computation and online communication per query, and requires 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 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 12ms online computation time on a single core.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. Major revision. IEEE S&P 2024
Keywords: PIR
Contact author(s): mingxunz @ andrew cmu edu
andrewpark @ cmu edu
runting @ cs cmu edu
wenting @ cmu edu
History: 2023-11-12: last of 3 revisions; 2023-03-28: received; See all versions
Short URL: https://ia.cr/2023/452
License: CC BY

BibTeX

@misc{cryptoeprint:2023/452,
      author = {Mingxun Zhou and Andrew Park and Elaine Shi and Wenting Zheng},
      title = {Piano: Extremely Simple, Single-Server {PIR} with Sublinear Server Computation},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/452},
      year = {2023},
      url = {https://eprint.iacr.org/2023/452}
}