Single-Server Single-Message Online Private Information Retrieval with Side Information
Single-Server Single-Message Online Private Information Retrieval with Side Information
复制标题
带辅助信息的单服务器单消息在线隐私信息检索
DOI：
10.1109/isit.2019.8849842
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
A. Sprintson
中科院分区：
文献类型：
--
作者：
Fatemeh Kazemi;Esmaeil Karimi;A. Heidarzadeh;A. Sprintson
在许多实际设置中，用户需要在多轮通信中以周期性方式从服务器检索信息消息。每次检索一条消息，并且服务器不知道未来请求的身份。在本文中，我们关注的是私有信息检索协议，它确保从服务器检索的所有消息的身份都得到保护。这种情况可能发生在实际环境中，例如定期从文本和多媒体存储库下载内容。我们将这个最小化数据下载率的问题称为在线私人信息检索问题。我们假设用户知道数据库中M条消息的子集作为辅助信息。这M条消息的身份最初对服务器是未知的。针对标量线性设置，我们描述了每轮的容量，即每轮可达到的最大下载速率。特别地，我们证明了对于K个消息存储在服务器上的设置，标量线性设置的每轮容量对于I轮=1是c1=(M+1)/K，对于I轮−2是Ci=(2i≥1(M+1))/Km，假设K/(M+1)是2的幂。我们的可达成性方案的关键思想是将本轮和前几轮下载的数据与原始边信息消息相结合，并将得到的数据用作后续轮的边信息。
In many practical settings, the user needs to retrieve information messages from a server in a periodic manner, over multiple rounds of communication. The messages are retrieved one at a time and the identity of future requests are not known to the server. In this paper, we focus on the private information retrieval protocols that ensure that the identities of all the messages retrieved from the server are protected. This scenario can occur in practical settings such as periodic content download from text and multimedia repositories. We refer to this problem of minimizing the rate of data download as online private information retrieval problem.Following the previous line of work by Kadhe et al. we assume that the user knows a subset of M messages in the database as side information. The identities of these M messages are initially unknown to the server. Focusing on scalar-linear settings, we characterize the per-round capacity, i.e., the maximum achievable download rate at each round. In particular, we show that for the setting with K messages stored at the server, the per-round capacity of the scalar-linear setting is C1 = (M + 1)/K for round i = 1 and Ci = (2i −1(M + 1))/KM for round i ≥ 2, provided that K/(M + 1) is a power of 2. The key idea≥of our achievability scheme is to combine the data downloaded during the current round and the previous rounds with the original side information messages and use the resulting data as side information for the subsequent rounds.
基于辅助信息的单服务器多消息私密信息检索能力研究
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
私有编码边信息的单服务器单消息私有信息检索能力
DOI：
10.1109/isit.2019.8849648
发表时间：
2019
期刊：
2019 IEEE International Symposium on Information Theory (ISIT
影响因子：
--
作者：
Heidarzadeh, Anoosheh;Kazemi, Fatemeh;Sprintson, Alex
通讯作者：
Sprintson, Alex