Multi-Server Private Information Retrieval with Coded Side Information
Multi-Server Private Information Retrieval with Coded Side Information
复制标题
带有编码辅助信息的多服务器私有信息检索
DOI：
10.1109/cwit.2019.8929933
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
A. Sprintson
中科院分区：
文献类型：
--
作者：
Fatemeh Kazemi;Esmaeil Karimi;A. Heidarzadeh;A. Sprintson
In this paper, we study the multi-server setting of the Private Information Retrieval with Coded Side Information (PIR-CSI) problem. In this problem, there are K messages replicated across N servers, and there is a user who wishes to download one message from the servers without revealing any information to any server about the identity of the requested message. The user has a side information which is a linear combination of a subset of M messages in the database. The parameter M is known to all servers in advance, whereas the indices and the coefficients of the messages in the user’s side information are unknown to any server a priori.We focus on a class of PIR-CSI schemes, referred to as server-symmetric schemes, in which the queries/answers to/from different servers are symmetric in structure. We define the rate of a PIR-CSI scheme as its minimum download rate among all problem instances, and define the server-symmetric capacity of the PIR-CSI problem as the supremum of rates over all server-symmetric PIR-CSI schemes. Our main results are as follows: (i) when the side information is not a function of the user’s requested message, the capacity is given by ${\left( {1 + 1/N + \cdots + 1/{N^{\left\lceil {\frac{K}{{M + 1}}} \right\rceil - 1}}} \right)^{ - 1}}$ for any 1 ≤ M ≤ K− 1; and (ii) when the side information is a function of the user’s requested message, the capacity is equal to 1 for M = 2 and M = K, and it is equal to N/(N + 1) for any 3 ≤ M ≤ K− 1. The converse proofs rely on new information-theoretic arguments, and the achievability schemes are inspired by our recently proposed scheme for single-server PIR-CSI as well as the Sun-Jafar scheme for multi-server PIR.
In this paper, we study the multi-server setting of the Private Information Retrieval with Coded Side Information (PIR-CSI) problem. In this problem, there are K messages replicated across N servers, and there is a user who wishes to download one message from the servers without revealing any information to any server about the identity of the requested message. The user has a side information which is a linear combination of a subset of M messages in the database. The parameter M is known to all servers in advance, whereas the indices and the coefficients of the messages in the user’s side information are unknown to any server a priori.We focus on a class of PIR-CSI schemes, referred to as server-symmetric schemes, in which the queries/answers to/from different servers are symmetric in structure. We define the rate of a PIR-CSI scheme as its minimum download rate among all problem instances, and define the server-symmetric capacity of the PIR-CSI problem as the supremum of rates over all server-symmetric PIR-CSI schemes. Our main results are as follows: (i) when the side information is not a function of the user’s requested message, the capacity is given by ${\left( {1 + 1/N + \cdots + 1/{N^{\left\lceil {\frac{K}{{M + 1}}} \right\rceil - 1}}} \right)^{ - 1}}$ for any 1 ≤ M ≤ K− 1; and (ii) when the side information is a function of the user’s requested message, the capacity is equal to 1 for M = 2 and M = K, and it is equal to N/(N + 1) for any 3 ≤ M ≤ K− 1. The converse proofs rely on new information-theoretic arguments, and the achievability schemes are inspired by our recently proposed scheme for single-server PIR-CSI as well as the Sun-Jafar scheme for multi-server PIR.
基于辅助信息的单服务器多消息私密信息检索能力研究
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.8849648
发表时间：
2019
期刊：
2019 IEEE International Symposium on Information Theory (ISIT
影响因子：
--
作者：
Heidarzadeh, Anoosheh;Kazemi, Fatemeh;Sprintson, Alex
通讯作者：
Sprintson, Alex