Multi-Message Pliable Private Information Retrieval

Sarah A. Obead, Jorg Kliewer

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

We formulate a new variant of the private information retrieval (PIR) problem where the user is pliable, i.e., interested in any message from a desired subset of the available dataset, denoted as pliable private information retrieval (PPIR). We consider the setup where a dataset consisting of f messages is replicated in n noncolluding databases and classified into Γ classes. For this setup, the user wishes to retrieve any λ ≥ 1 messages from multiple desired classes, while revealing no information about the identity of the desired classes to the databases. We term this problem multi-message PPIR (M-PPIR) and introduce the single-message PPIR (PPIR) problem as an elementary special case of M-PPIR. We first derive converse bounds on the M-PPIR download rate, followed by achievable schemes. As a result, we show that the PPIR capacity for f messages and Γ classes matches the PIR capacity with n noncolluding databases and Γ messages. Thus, enabling flexibility, i.e., pliability, where privacy is only guaranteed for classes, but not for messages as in classical PIR, allows to trade-off privacy versus download rate. A similar insight is shown to hold for the general case of M-PPIR.

Original languageEnglish (US)
Title of host publication2022 IEEE Information Theory Workshop, ITW 2022
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages714-719
Number of pages6
ISBN (Electronic)9781665483414
DOIs
StatePublished - 2022
Event2022 IEEE Information Theory Workshop, ITW 2022 - Mumbai, India
Duration: Nov 1 2022Nov 9 2022

Publication series

Name2022 IEEE Information Theory Workshop, ITW 2022

Conference

Conference2022 IEEE Information Theory Workshop, ITW 2022
Country/TerritoryIndia
CityMumbai
Period11/1/2211/9/22

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Artificial Intelligence
  • Computational Theory and Mathematics
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'Multi-Message Pliable Private Information Retrieval'. Together they form a unique fingerprint.

Cite this