The Role of Reusable and Single-Use Side Information in Private Information Retrieval
The Role of Reusable and Single-Use Side Information in Private Information Retrieval
复制标题
可重用和一次性辅助信息在私人信息检索中的作用
DOI：
10.1109/isit50566.2022.9834586
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
A. Sprintson
中科院分区：
文献类型：
--
作者：
A. Heidarzadeh;A. Sprintson
本文介绍了可重复使用和单次使用边信息的私有信息检索（PIR-RSSI）问题。在这个问题中，一个或多个远程服务器存储了一组K个消息的相同副本，并且有一个用户最初知道这些消息中的M个，并且想要私下从K个消息中检索另一个消息。目标是设计一种检索方案，其中用户从服务器下载最小量的信息，同时用户想要的消息的身份和用户已知的M个消息的M1子集的身份（称为可重用的边信息）被保护，但是用户已知的剩余M2：= M-M1消息的身份（称为单次使用边信息）不需要被保护。当M1 =M2 = 0时，PIR-RSSI问题归结为经典的私有信息检索（PIR）问题;当M1 ≥ 1，M2 = 0或M1 = 0，M2 ≥ 1时，PIR-RSSI问题分别归结为带私有边信息的PIR问题或带边信息的PIR问题。在这项工作中，我们专注于PIR-RSSI问题的单服务器设置。我们针对M1 = 1，M2 ≥ 1和M1 ≥ 1，M2 = 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 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−M1 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 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.
登录
查看更多内容
基于辅助信息的单服务器多消息私密信息检索能力研究
DOI：
10.1109/allerton.2018.8635969
发表时间：
2018
期刊：
and Computing
影响因子：
--
作者：
Heidarzadeh, Anoosheh;Garcia, Brenden;Kadhe, Swanand;Rouayheb, Salim El;Sprintson, Alex
通讯作者：
Sprintson, Alex
带有辅助信息的单服务器多消息单独私有信息检索
DOI：
10.1109/isit.2019.8849283
发表时间：
2019
期刊：
2019 IEEE International Symposium on Information Theory (ISIT
影响因子：
--
作者：
Heidarzadeh, Anoosheh;Kadhe, Swanand;El Rouayheb, Salim;Sprintson, Alex
通讯作者：
Sprintson, Alex
基于私有编码边信息的单服务器私有信息检索
影响因子：
2.5
作者：
Lu, Yuxiang;Jafar, Syed A.
通讯作者：
Jafar, Syed A.
私有编码边信息的单服务器单消息私有信息检索能力
DOI：
10.1109/isit.2019.8849648
发表时间：
2019
期刊：
2019 IEEE International Symposium on Information Theory (ISIT
影响因子：
--
作者：
Heidarzadeh, Anoosheh;Kazemi, Fatemeh;Sprintson, Alex
通讯作者：
Sprintson, Alex