论文标题
柔韧的私人信息检索
Pliable Private Information Retrieval
论文作者
论文摘要
我们制定了私人信息检索（PIR）问题的新变体，其中用户是柔韧的，即对可用数据集的所需子集的任何消息感兴趣，并表示为柔韧的私人信息检索（PPIR）。我们考虑一个设置，其中由$ f $消息组成的数据集以$ n $ noncolluding数据库复制并分类为$γ$类。对于此设置，用户希望从多个所需的类（即$η\ geq 1 $）中检索任何$λ\ geq 1 $消息，同时又揭示了有关数据库所需类别的身份的信息。我们将此问题称为多消息PPIR（M-PPIR），并引入单密码PPIR（PPIR）问题是M-PPIR的基本特殊情况。我们首先在M-PPIR速率上得出相反的范围，该速率定义为所需信息量的比率和下载的信息总量，然后是相应的可实现的方案。结果，我们表明，对于$ n $ noncolluding数据库的PPIR容量，即最大可实现的PPIR速率，与PIR的容量与$ N $数据库和$γ$消息相匹配。因此，启用灵活性，即柔韧性，其中仅保证上课的隐私，而不是像经典PIR中的消息一样，可以权衡隐私与下载率。显示了类似的见解，可以为M-PPIR的一般情况提供。
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 a 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 $λ\geq 1$ messages from multiple desired classes, i.e., $η\geq 1$, 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 rate, which is defined as the ratio of the desired amount of information and the total amount of downloaded information, followed by the corresponding achievable schemes. As a result, we show that the PPIR capacity, i.e., the maximum achievable PPIR rate, for $n$ noncolluding databases matches the capacity of PIR with $n$ 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.
