We consider the problem of Private Information Retrieval with Private Side Information (PIR-PSI), wherein a user wants to retrieve a file from replication based non-colluding databases by using the prior knowledge of a subset of the files stored on the databases. The PIR-PSI framework ensures that the privacy of the demand and the side information are jointly preserved, thereby finding potential applications when multiple files have to be downloaded spread across different time-instants. Although the capacity of the PIR-PSI setting is known, we observe that the underlying capacity achieving code construction uses Maximum Distance Separable (MDS) codes thereby contributing to high computational complexity when retrieving the demand. Pointing at this drawback of MDS-based PIR-PSI codes, we propose XOR-based PIR-PSI codes for a simple yet non-trivial setting of two non-colluding databases and two side information files at the user. While our codes offer substantial reduction in complexity when compared to MDS based codes, the code-rate marginally falls short of the capacity of the PIR-PSI setting. Nevertheless, we show that our code-rate is strictly higher than that of XOR-based codes for PIR with no side information, thereby implying that our codes can be useful when downloading multiple files in a sequential manner, instead of applying XOR-based PIR codes on each file.


翻译:我们考虑了私隐信息检索私隐侧信息(PIR-PSI)问题,用户希望通过使用数据库中储存的一组文件的先前知识,从基于复制的非污染数据库检索基于非污染数据库的文件。PIR-PSI框架确保联合保存需求隐私和侧面信息,从而在多个文件必须下载在不同时间用户之间时找到潜在的应用程序。虽然PIR-PSI设置的能力是众所周知的,但我们看到,实现代码构建的基本能力使用最大距离代码,从而在检索需求时导致高计算复杂性。指出基于MDS的PIR-PSI代码的这一退出,我们建议以XOR为基础的PIR-PSI代码编码用于简单但非三边设置的两个非循环数据库和用户的两个侧面信息文件。虽然与基于MDS的代码相比,我们的代码的复杂程度大大降低,但代码在重现PIR-PSI文件设定能力方面略短于PIR的计算能力。然而,我们提出,在应用基于MSIR的多级代码时,我们的代码可以严格地将我们的X的代码用于下载。

0
下载
关闭预览

相关内容

《计算机信息》杂志发表高质量的论文,扩大了运筹学和计算的范围,寻求有关理论、方法、实验、系统和应用方面的原创研究论文、新颖的调查和教程论文,以及描述新的和有用的软件工具的论文。官网链接:https://pubsonline.informs.org/journal/ijoc
专知会员服务
39+阅读 · 2020年9月6日
迁移学习简明教程,11页ppt
专知会员服务
107+阅读 · 2020年8月4日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
分布式并行架构Ray介绍
CreateAMind
9+阅读 · 2019年8月9日
CCF推荐 | 国际会议信息10条
Call4Papers
8+阅读 · 2019年5月27日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
计算机 | CCF推荐期刊专刊信息5条
Call4Papers
3+阅读 · 2019年4月10日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
LibRec 精选:推荐系统的论文与源码
LibRec智能推荐
14+阅读 · 2018年11月29日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
LibRec 精选:连通知识图谱与推荐系统
LibRec智能推荐
3+阅读 · 2018年8月9日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
Cryptanalysis of a code-based full-time signature
Arxiv
0+阅读 · 2021年7月6日
Arxiv
0+阅读 · 2021年7月5日
VIP会员
相关VIP内容
专知会员服务
39+阅读 · 2020年9月6日
迁移学习简明教程,11页ppt
专知会员服务
107+阅读 · 2020年8月4日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
相关资讯
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
分布式并行架构Ray介绍
CreateAMind
9+阅读 · 2019年8月9日
CCF推荐 | 国际会议信息10条
Call4Papers
8+阅读 · 2019年5月27日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
计算机 | CCF推荐期刊专刊信息5条
Call4Papers
3+阅读 · 2019年4月10日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
LibRec 精选:推荐系统的论文与源码
LibRec智能推荐
14+阅读 · 2018年11月29日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
LibRec 精选:连通知识图谱与推荐系统
LibRec智能推荐
3+阅读 · 2018年8月9日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
Top
微信扫码咨询专知VIP会员