Lower-Cost -Private Information Retrieval
Authors: Raphael R. Toledo (University College London), George Danezis (University College London), Ian Goldberg (University of Waterloo)
Volume: 2016
Issue: 4
Pages: 184–201
DOI: https://doi.org/10.1515/popets-2016-0035
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.
Keywords: Private Information Retrieval, Anonymous communications, Private Queries, Differential Privacy
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 license.
