Multi-Message Pliable Private Information Retrieval
Sarah A. Obead, Jörg Kliewer · 2022 IEEE Information Theory Workshop (ITW) · 2022
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.