Toledo, RR;
Danezis, G;
Goldberg, I;
(2016)
Lower-Cost ∈-Private Information Retrieval.
Proceedings on Privacy Enhancing Technologies
, 2016
(4)
10.1515/popets-2016-0035.
Preview |
Text
Toledo_[] Lower-Cost ∈-Private Information Retrieval.pdf - Published Version Download (666kB) | Preview |
Abstract
Private Information Retrieval (PIR), despite being well studied, is computationally costly and arduous to scale. We explore lower-cost relaxations of information-theoretic PIR, based on dummy queries, sparse vectors, and compositions with an anonymity system. We prove the security of each scheme using a flexible differentially private definition for private queries that can capture notions of imperfect privacy. We show that basic schemes are weak, but some of them can be made arbitrarily safe by composing them with large anonymity systems.
| Type: | Article |
|---|---|
| Title: | Lower-Cost ∈-Private Information Retrieval |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1515/popets-2016-0035 |
| Publisher version: | https://doi.org/10.1515/popets-2016-0035 |
| Language: | English |
| Additional information: | Copyright © 2016. This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License. (CC BY-NC-ND 4.0) (http://creativecommons.org/licenses/by-nc-nd/4.0) |
| Keywords: | Private Information Retrieval; Anonymous communications; Private Queries; Differential Privacy |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery.ucl.ac.uk/id/eprint/1478222 |
Archive Staff Only
 |
View Item |
