Towards Doubly Efficient Private Information Retrieval
Private Information Retrieval (PIR) allows a client to obtain data from a public database without disclosing the locations accessed. Traditionally, the stress is on preserving sublinear work for the client, while the server’s work is taken to inevitably b
- PDF / 469,338 Bytes
- 33 Pages / 439.37 x 666.142 pts Page_size
- 57 Downloads / 184 Views
Boston University, Boston, USA Tel-Aviv University, Tel Aviv, Israel Massachusetts Institute of Technology, Cambridge, USA [email protected] 4 University of California Riverside, Riverside, USA [email protected] 2
3
Abstract. Private Information Retrieval (PIR) allows a client to obtain data from a public database without disclosing the locations accessed. Traditionally, the stress is on preserving sublinear work for the client, while the server’s work is taken to inevitably be at least linear in the database size. Beimel, Ishai and Malkin (JoC 2004) show PIR schemes where, following a linear-work preprocessing stage, the server’s work per query is sublinear in the database size. However, that work only addresses the case of multiple non-colluding servers; the existence of single-server PIR with sublinear server work remained unaddressed. We consider single-server PIR schemes where, following a preprocessing stage in which the server obtains an encoded version of the database and the client obtains a short key, the per-query work of both server and client is polylogarithmic in the database size. Concentrating on the case where the client’s key is secret, we show: – A scheme, based on one-way functions, that works for a bounded number of queries, and where the server storage is linear in the number of queries plus the database size. – A family of schemes for an unbounded number of queries, whose security follows from a corresponding family of new hardness assumption that are related to the hardness of solving a system of noisy linear equations. We also show the insufficiency of a natural approach for obtaining doubly efficient PIR in the setting where the preprocessing is public.
1
Introduction
Enabling clients to query remote databases while preserving privacy of the queries is a basic challenge in cryptography. With the proliferation of huge dataWork supported by the NSF MACS project. R. Canetti—Member of CPIIS. Supported in addition by ISF Grant 1523/14. J. Holmgren—Supported in addition by DARPA IBM-W911NF-15C0236 and SIMONS Investigator Award. S. Richelson—Work done while at MIT and Boston University. c International Association for Cryptologic Research 2017 Y. Kalai and L. Reyzin (Eds.): TCC 2017, Part II, LNCS 10678, pp. 694–726, 2017. https://doi.org/10.1007/978-3-319-70503-3_23
Towards Doubly Efficient Private Information Retrieval
695
bases stored and managed by powerful third parties, this challenge becomes ever more relevant. One of the more basic formulations of this multi-faceted problem is the concept of Private Information Retrieval (PIR) [CKGS98]. Here the client is interested in learning the contents of specific addresses in the database, while preventing the server controlling the database (or, simply, the database) from learning these addresses. The goal here is to minimize communication and work for the client. There are two general types of PIR schemes: Multi-server schemes whose security relies on the assumption that servers do not collude, but are otherwise information theoretic (see
Data Loading...
