Lower-Cost epsilon-Private Information Retrieval
This work addresses the problem of making PIR more practical for applications requiring private data queries, though it appears incremental as it builds on existing PIR concepts with relaxations.
The paper tackles the high computational cost and scalability issues of Private Information Retrieval (PIR) by proposing lower-cost relaxations using dummy queries, sparse vectors, and compositions with anonymity systems, proving their security with a differentially private definition and showing that some schemes can be made arbitrarily safe through composition.
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.