International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Lower Bounds for (Batch) PIR with Private Preprocessing

Authors:
Kevin Yeo , Google and Columbia University
Download:
DOI: 10.1007/978-3-031-30545-0_18 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2023
Abstract: In this paper, we study (batch) private information retrieval with private preprocessing. Private information retrieval (PIR) is the problem where one or more servers hold a database of $n$ bits and a client wishes to retrieve the $i$-th bit in the database from the server(s). In PIR with private preprocessing (also known as offline-online PIR), the client is able to compute a private $r$-bit hint in an offline stage that may be leveraged to perform retrievals accessing at most $t$ entries. For privacy, the client wishes to hide index $i$ from an adversary that has compromised some of the servers. In the batch PIR setting, the client performs queries to retrieve the contents of multiple entries simultaneously. We present a tight characterization for the trade-offs between hint size $r$ and number of accessed entries $t$ during queries. For any PIR scheme that enables clients to perform batch retrievals of $k$ entries, we prove a lower bound of $tr = \Omega(nk)$ when $r \ge k$. When $r < k$, we prove that $t = \Omega(n)$. Our lower bounds hold when the scheme errs with probability at most $1/15$ and against PPT adversaries that only compromise one out of $\ell$ servers for any $\ell = O(1)$. Our work also closes the multiplicative logarithmic gap for the single query setting $(k = 1)$ as our lower bound matches known constructions. Our lower bounds hold in the model where each database entry is stored without modification but each entry may be replicated arbitrarily. Finally, we show connections between PIR and the online matrix-vector (OMV) conjecture from fine-grained complexity. We present barriers for proving lower bounds for two-server PIR schemes in general computational models as they would immediately imply the OMV conjecture.
BibTeX
@inproceedings{eurocrypt-2023-32903,
  title={Lower Bounds for (Batch) PIR with Private Preprocessing},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-031-30545-0_18},
  author={Kevin Yeo},
  year=2023
}