Can We Access a Database Both Locally and Privately?
We consider the following strong variant of private information retrieval (PIR). There is a large database x that we want to make publicly available. To this end, we post an encoding X of x together with a short public key \(\mathsf{pk}\) in a publicly ac
- PDF / 463,546 Bytes
- 32 Pages / 439.37 x 666.142 pts Page_size
- 91 Downloads / 170 Views
5
IDC Herzliya, Herzliya, Israel [email protected] 2 Technion, Haifa, Israel [email protected] 3 UCLA, Los Angeles, USA 4 Cornell University, Ithaca, USA [email protected] Stanford University, Stanford, USA [email protected]
Abstract. We consider the following strong variant of private information retrieval (PIR). There is a large database x that we want to make publicly available. To this end, we post an encoding X of x together with a short public key pk in a publicly accessible repository. The goal is to allow any client who comes along to retrieve a chosen bit xi by reading a small number of bits from X, whose positions may be randomly chosen based on i and pk, such that even an adversary who can fully observe the access to X does not learn information about i. Towards solving this problem, we study a weaker secret key variant where the data is encoded and accessed by the same party. This primitive, that we call an oblivious locally decodable code (OLDC), is independently motivated by applications such as searchable symmetric encryption. We reduce the public-key variant of PIR to OLDC using an ideal form of obfuscation that can be instantiated heuristically with existing indistinguishability obfuscation candidates, or alternatively implemented with small and stateless tamper-proof hardware. Finally, a central contribution of our work is the first proposal of an OLDC candidate. Our candidate is based on a secretly permuted ReedMuller code. We analyze the security of this candidate against several natural attacks and leave its further study to future work.
1
Introduction
A private information retrieval (PIR) protocol allows a client to retrieve an item from a remote database while hiding which item is retrieved even from the servers storing the database. PIR has been studied both in a multi-server setting, where security should only hold against non-colluding servers [9,10], and in a singleserver setting [27]. In both settings, the main focus of the large body of work on PIR has been on minimizing the communication complexity. c International Association for Cryptologic Research 2017 Y. Kalai and L. Reyzin (Eds.): TCC 2017, Part II, LNCS 10678, pp. 662–693, 2017. https://doi.org/10.1007/978-3-319-70503-3_22
Can We Access a Database Both Locally and Privately?
663
Improving the computational complexity of PIR turned out to be much more challenging. If no preprocessing of the database is allowed, the computational complexity of the servers must be at least linear in the database size [4]. While preprocessing was shown to be helpful in the multi-server setting [4], the existence of sublinear-time single-server PIR protocols has been a longstanding open question, with no negative results or (even heuristic) candidate solutions. In this work we consider the following strong variant of sublinear-time PIR that we call public-key PIR (pk-PIR). Suppose we want to allow efficient and privacy-preserving access to a large database x ∈ {0, 1}n . To this end, we encode x into a (possibly bigger) datab
Data Loading...
