Paper 2024/318

Plinko: Single-Server PIR with Efficient Updates via Invertible PRFs

Alexander Hoover, University of Chicago, Google (United States)
Sarvar Patel, Google (United States)
Giuseppe Persiano, Università di Salerno, Google (United States)
Kevin Yeo, Google (United States), Columbia University

We study single-server private information retrieval (PIR) where a client wishes to privately retrieve the $x$-th entry from a database held by a server without revealing the index $x$. In our work, we focus on PIR with client pre-processing where the client may compute hints during an offline phase. The hints are then leveraged during queries to obtain sub-linear online time. We present Plinko that is the first single-server PIR with client pre-processing that obtains optimal trade-offs between client storage and total (client and server) query time for all parameters. Our scheme uses $t = \tilde{O}(n/r)$ query time for any client storage size $r$. This matches known lower bounds of $r \cdot t = \Omega(n)$ up to logarithmic factors for all parameterizations whereas prior works could only match the lower bound when $r = \tilde{O}(\sqrt{n})$. Moreover, Plinko is also the first updateable PIR scheme where an entry can be updated in worst-case $\tilde{O}(1)$ time. As our main technical tool, we define the notion of an invertible pseudorandom function (iPRF) that generalizes standard PRFs to be equipped with an efficient inversion algorithm. We present a construction of an iPRF from one-way functions where forward evaluation runs in $\tilde{O}(1)$ time and inversion runs in time linear in the inverse set (output) size. Furthermore, our iPRF construction is the first that remains efficient and secure for arbitrary domain and range sizes (including small domains and ranges). In the context of single-server PIR, we show that iPRFs may be used to construct the first hint set representation where finding a hint containing an entry $x$ may be done in $\tilde{O}(1)$ time.

Available format(s)
Cryptographic protocols
Publication info
Private Information Retrieval
Contact author(s)
alexhoover @ uchicago edu
sarvar @ google com
giuper @ gmail com
kwlyeo @ google com
2024-05-14: revised
2024-02-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Alexander Hoover and Sarvar Patel and Giuseppe Persiano and Kevin Yeo},
      title = {Plinko: Single-Server {PIR} with Efficient Updates via Invertible {PRFs}},
      howpublished = {Cryptology ePrint Archive, Paper 2024/318},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.