The Role of Reusable and Single-Use Side Information in Private Information Retrieval
share
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≥ 1,M_2=0 or M_1=0,M_2≥ 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≥ 1 and M_1≥ 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.
READ FULL TEXT