论文标题
可重复使用和一次性侧面信息在私人信息检索中的作用
The Role of Reusable and Single-Use Side Information in Private Information Retrieval
论文作者
论文摘要
本文介绍了可重复使用和一次性侧面信息（PIR-RSSI）的私人信息检索问题。在此问题中，一个或多个远程服务器存储了一组$ K $消息的相同副本，并且有一个用户最初知道这些消息的$ m $，并且希望从$ k $消息集中私下检索其他一条消息。目的是设计一个检索方案，在该方案中，用户从服务器中下载最小信息量，而用户想要的消息的身份以及用户已知的$ m $消息的$ m_1 $ -subset的身份（称为可重复使用的信息）的$ m $消息的确定性，但剩余的$ _-m_2 = m_2 = m-m_1 $ _-m_1 $ _1 $ _-m_1 = m_2受保护。当$ {m_1 = m_2 = 0} $时，PIR-RSSI问题将减少到经典的私人信息检索（PIR）问题，并在$ {m_1 \ geq 1，m_1 \ geq 1，m_2 = 0} $ {m_1} $或$ {m_1 = 0，m_1 = 0，m_2 = geq时，将带有私人信息的PIR或带有侧面信息的PIR减少。在这项工作中，我们专注于PIR-RSSI问题的单人服务器设置。我们在$ {m_1 = 1，m_2 \ geq 1} $和$ {m_1 \ geq 1，m_2 = 1} $的情况下表征了此设置的容量，其中容量定义为所有PIR-RSSI方案的最大可实现下载率。我们的结果表明，对于$ k $的足够小的值，一次性侧面信息消息只有在将其保密时才有助于降低下载成本；对于$ k $的较大值，可重复使用的侧面信息消息无助于降低下载成本。
This paper introduces the problem of Private Information Retrieval with Reusable and Single-use Side Information (PIR-RSSI). In this problem, one or more remote servers store identical copies of a set of $K$ messages, and there is a user that initially knows $M$ of these messages, and wants to privately retrieve one other message from the set of $K$ messages. The objective is to design a retrieval scheme in which the user downloads the minimum amount of information from the server(s) while the identity of the message wanted by the user and the identities of an $M_1$-subset of the $M$ messages known by the user (referred to as reusable side information) are protected, but the identities of the remaining $M_2=M-M_1$ messages known by the user (referred to as single-use side information) do not need to be protected. The PIR-RSSI problem reduces to the classical Private Information Retrieval (PIR) problem when ${M_1=M_2=0}$, and reduces to the problem of PIR with Private Side Information or PIR with Side Information when ${M_1\geq 1,M_2=0}$ or ${M_1=0,M_2\geq 1}$, respectively. In this work, we focus on the single-server setting of the PIR-RSSI problem. We characterize the capacity of this setting for the cases of ${M_1=1,M_2\geq 1}$ and ${M_1\geq 1,M_2=1}$, where the capacity is defined as the maximum achievable download rate over all PIR-RSSI schemes. Our results show that for sufficiently small values of $K$, the single-use side information messages can help in reducing the download cost only if they are kept private; and for larger values of $K$, the reusable side information messages cannot help in reducing the download cost.
