Paper 2017/567

Can We Access a Database Both Locally and Privately?

Elette Boyle, Yuval Ishai, Rafael Pass, and Mary Wootters

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 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.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
private information retrievallocally decodable codes
Contact author(s)
eboyle @ alum mit edu
History
2017-06-14: received
Short URL
https://ia.cr/2017/567
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/567,
      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{https://eprint.iacr.org/2017/567}},
      url = {https://eprint.iacr.org/2017/567}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.