TY - GEN
T1 - Multi-Message Pliable Private Information Retrieval
AU - Obead, Sarah A.
AU - Kliewer, Jorg
N1 - Publisher Copyright:
© 2022 IEEE.
PY - 2022
Y1 - 2022
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85144593653&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85144593653&partnerID=8YFLogxK
U2 - 10.1109/ITW54588.2022.9965759
DO - 10.1109/ITW54588.2022.9965759
M3 - Conference contribution
AN - SCOPUS:85144593653
T3 - 2022 IEEE Information Theory Workshop, ITW 2022
SP - 714
EP - 719
BT - 2022 IEEE Information Theory Workshop, ITW 2022
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2022 IEEE Information Theory Workshop, ITW 2022
Y2 - 1 November 2022 through 9 November 2022
ER -