Welcome to the resource topic for 2022/828
Title:
Batch Private Information Retrieval with Private Preprocessing
Authors: Kevin Yeo
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 in t online time. For privacy, the client wishes to hide index i from an adversary that has compromised some of the servers. We will focus on the batch PIR setting where the client performs queries to retrieve the contents of multiple entries simultaneously. We present a tight characterization for the trade-offs between hint size and online query time. For any \ell = O(1) and \ell-server 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 server. Our results also improve the best known lower bounds for the single query setting by a logarithmic factor. On the positive side, we show there exists a construction with a single-round query algorithm such that tr = \tilde{O}(nk) that matches our lower bound up to logarithmic factors.
ePrint: https://eprint.iacr.org/2022/828
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .