Paper 2017/567
Can We Access a Database Both Locally and Privately?
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.
Note: Updates reflecting recent developments.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- A minor revision of an IACR publication in TCC 2017
- Keywords
- private information retrievallocally decodable codes
- Contact author(s)
-
eboyle @ alum mit edu
yuvali @ cs technion ac il
rafael pass @ gmail com
marykw @ stanford edu - History
- 2023-01-19: revised
- 2017-06-14: received
- See all versions
- Short URL
- https://ia.cr/2017/567
- License
-
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},
url = {https://eprint.iacr.org/2017/567}
}
