The Role of Reusable and Single-Use Side Information in Private Information Retrieval
Anoosheh Heidarzadeh, Alex Sprintson · 2022 IEEE International Symposium on Information Theory (ISIT) · 2022
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 M1-subset of the M messages known by the user (referred to as reusable side information) are protected, but the identities of the remaining M2:=M−M1messages 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 M1=M2= 0, and reduces to the problem of PIR with Private Side Information or PIR with Side Information when M1≥ 1, M2= 0 or M1= 0, M2≥ 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 M1= 1, M2≥ 1 and M1≥ 1, M2= 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, both the single-use and reusable side information messages can help in reducing the download cost; and for larger values of K, only the single-use side information messages can help in reducing the download cost.