Paper 2017/567

Can We Access a Database Both Locally and Privately?

Elette Boyle
Yuval Ishai
Rafael Pass
Mary Wootters

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 x_i 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 the above 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 sym- metric 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 Reed-Muller code. We analyze the security of this candidate against several natural attacks and leave its further study to future work.

Note: Updates reflecting recent developments.

Available format(s)
Publication info
A minor revision of an IACR publication in TCC 2017
private information retrievallocally decodable codes
Contact author(s)
eboyle @ alum mit edu
yuvali @ cs technion ac il
rafael pass @ gmail com
marykw @ stanford edu
2023-01-19: revised
2017-06-14: received
See all versions
Short URL
Creative Commons Attribution


      author = {Elette Boyle and Yuval Ishai and Rafael Pass and Mary Wootters},
      title = {Can We Access a Database Both Locally and Privately?},
      howpublished = {Cryptology ePrint Archive, Paper 2017/567},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.