Private information retrieval from Byzantine and colluding databases
Private information retrieval from Byzantine and colluding databases
复制标题
DOI：
10.1109/allerton.2017.8262859
复制
发表时间：
2017-10
期刊：
影响因子：
--
通讯作者：
Karim A. Banawan;S. Ulukus
中科院分区：
文献类型：
--
作者：
Karim A. Banawan;S. Ulukus
研究了N个复制数据库的单轮私有信息检索（PIR）问题。我们考虑B数据库过时（不同步），或者更糟糕的是，敌对（拜占庭），因此可能返回不正确的答案的情况。在拜占庭数据库（BPIR）的PIR问题中，用户希望从一组M条消息中检索一条零错误的特定消息，而不管拜占庭数据库执行了什么操作。本文考虑T-隐私约束，其中任意T数据库可以串通，并交换用户提交的查询。我们确定了该问题的信息论容量，即下载数据的每个符号可以私下检索的正确符号的最大数量为C = N−2B/N·1−T/N−2B / 1−(T/N−2B)M，如果2B + T < N。我们的可实现方案扩展了鲁棒PIR （RPIR）问题的最优可实现方案，以纠正拜占庭数据库引入的错误。我们的逆向证明在对抗节点的网络编码问题中使用了切集界的思想。
We consider the problem of single-round private information retrieval (PIR) from N replicated databases. We consider the case when B databases are outdated (unsynchronized), or even worse, adversarial (Byzantine), and therefore, can return incorrect answers. In the PIR problem with Byzantine databases (BPIR), a user wishes to retrieve a specific message from a set of M messages with zero-error, irrespective of the actions performed by the Byzantine databases. We consider the T-privacy constraint in this paper, where any T databases can collude, and exchange the queries submitted by the user. We determine the information-theoretic capacity of this problem, which is the maximum number of correct symbols that can be retrieved privately for every symbol of the downloaded data to be C = N−2B/N · 1−T/N−2B / 1−(T/N−2B)M, if 2B + T < N. Our achievable scheme extends the optimal achievable scheme for the robust PIR (RPIR) problem to correct the errors introduced by the Byzantine databases. Our converse proof uses the idea of the cut-set bound in the network coding problem against adversarial nodes.